COMPUTING SCIENCE
Connecting the Dots
Can the tools of graph theory and social-network studies unravel the next big plot?
Brian Hayes
Ties That Bind
Digging into the call graph is a form of data mining—and the
process could not be more aptly named. Heaving aside hundreds of
terabytes of extraneous data is the digital equivalent of a major
earthmoving project. Before firing up the steam shovels, it would be
helpful to know what we're looking for. What are the communications
patterns characteristic of dangerous plotters and connivers?
A good place to turn for an answer to this question is the community
of scholars who study social networks: the structures of groups of
people as defined by the connections between them. (Of course the
community of social-network scholars is itself a social network,
held together by many interpersonal connections.)
A seminal paper in this literature, "The strength of weak
ties," was published in 1973 by Mark S. Granovetter, now of
Stanford University. Granovetter observed that when people are
strongly connected—when they are close friends, say, or family
members, or working colleagues—the ties between them are
usually symmetrical and also obey a rule that might be called
triangularity. Symmetry implies that if A is a friend of B,
then B is also a friend of A. Triangularity says that if A is
friendly with both B and C, then B and C should also be
friends with each other. Of course these are merely tendencies, and
anyone can cite exceptions (unrequited love, pathological
triangles), but for purposes of analysis it's useful to ask what a
society would look like if symmetry and triangularity were strictly
enforced rules. The answer is that the social structure would
consist entirely of perfect cliques—groups in which
every person is linked to every other person.
Strong bonds between individuals would seem to be the very stuff of
social cohesion, but Granovetter's theory suggests a paradoxical
effect. Locally, strong ties create highly robust structures, but on
a larger scale they also isolate one group from another. Because of
the all-or-nothing nature of strong ties, distinct cliques become
island universes that cannot communicate with one another. What
really holds the world together, Granovetter argues, are weak
ties between casual acquaintances. These relationships are
often symmetrical but seldom tri-angular: You can chat with a bank
teller every week without getting to know all of the teller's other
customers. Such weak ties, which at first seem socially
insignificant, provide vital cross-links between cliques. The
prevailing network structure, according to Granovetter, consists of
clusters tightly bound internally by strong ties and loosely linked
to other clusters by weak ties.
Social-network theory has obvious affinities with mathematical graph
theory—even though people who work in the two fields tend to
form distinct clusters linked only by weak ties. Graph theory brings
its own vocabulary, as well as a more abstract view of the subject
matter: Formally, a graph is a set of vertices together with a set
of edges, where each edge connects a pair of vertices. This rather
opaque definition can be interpreted in various ways, but in
practice graph theorists, like social networkers, draw lots of
diagrams with dots and lines.
» Post Comment