[Computational Complexity] Graph Theory and the NSA
How could I not blog about Jonathan Farley's op-ed piece The NSA's Math Problem? Farley looks at the NSA's use of phone data as and argues that using graph theory to analyze the calls won't help find terrorists. But Farley doesn't do a particularly good job making his case.
First, the "central player" the person with the most spokes might not be as important as the hub metaphor suggests. For example, Jafar Adibi, an information scientist at the University of Southern California, analyzed e-mail traffic among Enron employees before the company collapsed. He found that if you naively analyzed the resulting graph, you could conclude that one of the "central" players was Ken Lay's…secretary.Somehow if we find the "secretary" of a central US terrorist that should be considered a major success. But more importantly if we know just a little about some terrorist activities the graph can give us a great advantage in finding important sites. Google's PageRank primarily uses graph theory very successfully to rank order search results and there is no reason similar ideas won't work on phone data as well.
By no means should we accuse someone of being a terrorist solely because of their calling pattern. Will all terrorists be found on phone data alone? Of course not. But using graph information can give us important information as to where to look and narrow the search.
The main objection to the NSA's work is not that the phone data has little value but that it is too valuable. You can use the data to find out much more about Americans than who is a terrorist. We lose our freedom against government intrusion when the NSA has this data and that's what we need to argue against, not some fake argument that the NSA's algorithms won't work.
Posted by Lance to Computational Complexity at 5/16/2006 04:40:00 PM