COMPUTING SCIENCE

# Connecting the Dots

Can the tools of graph theory and social-network studies unravel the next big plot?

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.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Spotlight**: Briefings

**Computing Science**: Belles lettres Meets Big Data

**Technologue**: Quantum Randomness