COMPUTING SCIENCE
Connecting the Dots
Can the tools of graph theory and social-network studies unravel the next big plot?
Brian Hayes
Inner Circles and Outer Rings
The social networks described above were constructed
retrospectively. The starting point was a complete list of the known
members of the group, along with enough biographical information to
fill in the links. Discerning the same structure in
advance—when an attack is still in the planning stage and most
of the plotters are unknown—would be much harder, especially
when working from impersonal data such as logs of phone calls or e-mails.
Sketching out such networks surely falls within the NSA's mandate,
which might explain the agency's interest in the call graph. One
scenario is easy to imagine. Someone has come under suspicion, based
on information from other sources, and by consulting the call graph
the NSA learns whom that person has been talking with in recent
weeks or months. The result is a "ring" of contacts
surrounding the subject. Then each of the contacts is investigated
in the same way, producing a second ring of contacts-of-contacts.
This process could be continued further, although the exponential
growth of the graph will soon take in most of the population
(especially if the subject has answered a call from a telemarketer
or has ordered a pizza). Of more interest are instances where the
subject's contacts are also contacts of one another, since such
triangular links suggest strong ties.
The tricky part of this network analysis is not finding the links
but knowing which of them are significant. It may well be true that
if intelligence agencies had "connected the dots," all of
the September 11 hijackers could have been linked to the two who
were spotted in January of 2000. But thousands of other people would
have been linked to those individuals as well. Showing the network
of conspirators in isolation is misleading; the graph is actually
embedded in a vastly larger structure.
Direct access to the call graph would be a convenience in tracing
the associations of known suspects, but it is not necessary. For any
named individual, the same records could be obtained under court
order, as they are by law-enforcement agencies during criminal
investigations. Indeed, if the call graph is used only for such
purposes, it seems like quite an extravagance—sifting through
1012 records for the few hundred or few thousand calls
that might be of interest.
But news reports hint at a more ambitious function for the call
graph: not merely tracking down the associates of a known malefactor
but rather discovering a plot without any prior guidance, merely by
searching the archive for "patterns that might point to
suspects." This sounds like magic: You cast your gaze over the
vast and intricate web of the call graph, and without even knowing
the names behind the phone numbers, you perceive some pattern of
linkages that's a danger sign. Can this trick be transferred from
the world of magic to the world of algorithms?
If such a signature pattern exists, the findings of social-network
theory suggest it should involve some distinctive combination of
strong and weak ties. A terrorist cell, seen from the point of view
of telephone traffic, might be a set of people who talk among
themselves a lot but have little to say to the rest of the world.
Thus the pattern that rings the alarm bells would be a dense
subgraph in comparative isolation from its surroundings.
» Post Comment