COMPUTING SCIENCE
Connecting the Dots
Can the tools of graph theory and social-network studies unravel the next big plot?
Brian Hayes
The 411 on Telephone Snooping
The newly revealed surveillance programs seem to include several
distinct activities. Some involve eavesdropping—listening in
on telephone conversations or recording the content of Internet
messages. A follow-the-money program gathers information from a
banking clearinghouse. But the reports I find most intriguing
mention efforts to analyze a database of telephone calls with the
aim of tracing links among conspirators. The database includes no
sound recordings or any other hints about what might have been said
in a conversation; it merely lists the telephone numbers at the two
ends of each call and gives the date and time when a call began and ended.
This "call detail" database sounded very familiar. Several
years ago I had read of experiments done with a similar
database—almost surely an earlier version of the one that is
now said to be under government scrutiny. The experiments were tests
of algorithms in the mathematical field known as graph theory, which
studies network-like structures. The phone-call database was a
useful test bed because it can be viewed as an enormous mathematical
graph. I wrote about this work in an earlier column in American
Scientist (January-February 2000).
Vague allusions to the database, or "call graph," appeared
in the first public accounts of the new surveillance programs.
Writing in The New York Times last December, Eric
Licht-blau and James Risen noted, "[National Security Agency]
technicians, besides actually eavesdropping on specific
conversations, have combed through large volumes of phone and
Internet traffic in search of patterns that might point to terrorism
suspects." The nature of the operation became clearer in May
when Leslie Cauley wrote in USA Today that at least three
telephone companies are voluntarily supplying call-detail records to
the NSA. Two of those companies later denied that they participate
in the program, and USA Today retracted that part of the
story. The third company, AT&T, has declined to comment on the
substance of the report, and so has the NSA. When AT&T was sued
for allegedly violating privacy statutes, the Bush administration
moved to suppress the suits on the grounds that litigating the
matter would reveal state secrets. As this issue of American
Scientist goes to press, the facts remain murky.
» Post Comment