Graph Theory & Civil Liberties

The NSA's Math Problem
courtesy Information Agers - Bentley

NY Times Op-Ed by Jonathan David Farley,
science fellow at the Stanford Center for International Security and Cooperation

If the program is along the lines described by USA Today -- with the security agency receiving complete lists of who called whom from each of the phone companies -- the object is probably to collect data and draw a chart, with dots or 'nodes' representing individuals and lines between nodes if one person has called another.

Mathematicians who work with pictures like this are called graph theorists, and there is an entire academic field, social network analysis, that tries to determine information about a group from such a chart, like who the key players are or who the cell leaders might be. [See, e.g., here and here (from Orgnet.com).]

But without additional data, its reach is limited: as any mathematician will admit, even when you know everyone in the graph is a terrorist, it doesn't directly portray information about the order or hierarchy of the cell. Social network researchers look instead for graph features like centrality: they try to identify nodes that are connected to a lot of other nodes, like spokes around the hub of a bicycle wheel.

But this isn't as helpful as you might imagine. 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 [Information Sciences Institute] University of Southern California, analyzed e-mail traffic among Enron employees before the company collapsed [see also here]. He found that if you naively analyzed the resulting graph, you could conclude that one of the "central" players was Ken Lay's ... secretary. [Note: While I have no trouble believing the assertion about the secretary, I did not see it mentioned in Abidi's papers. Also, the op-ed did not mention Abidi's co-author, Jitesh Shetty.]

And even if you manage to eliminate all the "central players," you may well still leave enough lesser players that the cell retains a complete chain of command capable of carrying out a devastating terrorist attack.

In addition, the National Security Agency's entire spying program seems to be based on a false assumption: that you can work out who might be a terrorist based on calling patterns.... Guilt by association is not just bad law, it's bad mathematics...

... read the whole article