• Think of an actor or actress.
• If they have ever been in a film with Kevin Bacon, then they have a "Bacon Number" of one.
• If they have never been in a film with Kevin Bacon but have been in a film with somebody else who has, then they have a Bacon Number of two, and so on.

The claim is that no one who has been in an American film, ever has a Bacon Number of greater than four. Elvis Presley, for example, has a Bacon Number of two. For real enthusiasts, Tjaden created a web site that provides the Bacon Number and shortest path to the great man for the most obscure of choices. In fact, Tjaden later fireproofed his claim by conducting an exhaustive survey of the Internet Movie Database, and determined that the highest finite Bacon Number (for any nationality) is eight. This may seem nothing more than a quirky fact about an already bizarre industry, but in fact it is a particularly clear example of a phenomenon that increasingly pervades our day-to-day existence: something known as the "small-world phenomenon."

The small-world phenomenon formalizes the anecdotal notion that "you are only ever six ‘degrees of separation' away from anybody else on the planet." Almost everyone is familiar with the sensation of running into a complete stranger at a party or in some public arena and, after a short conversation, discovering that they know somebody unexpected in common. "Well, it's a small-world!" they exclaim. The small-world phenomenon is a generalized version of this experience, the claim being that even when two people do not have a friend in common, only a short chain of intermediaries separates them. Stanley Milgram made the first experimental assault on the problem (confined to the United States) by sending a series of traceable letters from originating points in Kansas and Nebraska to one of two destinations in Boston. The letters could be sent only to someone whom the current holder knew by first name and who was presumably more likely than the holder to know the person to whom the letter was ultimately addressed. By requiring each intermediary to report their receipt of the letter, Milgram kept track of the letters and the demographic characteristics of their handlers. His results indicated a median chain length of about six, thus supporting the notion of "six degrees of separation," after which both a play and its movie adaptation have since been named.

This result was both striking and surprising and continues to be so today, because the conscious construction of such chains of intermediaries is very difficult to do. Ordinarily, our perception of the social world is confined to our group of immediate acquaintances, and within this group there is a great deal of redundancy; that is, within any one circle of acquaintances, most of them know each other. Furthermore, our average number of acquaintances is very much less than the size of the global population (at most thousands, compared with billions). So the claim that some very short chain of acquaintances exists that links us to any other person, anywhere in the world, does seem unlikely.

From Small-Worlds by Duncan Watts, Princeton University Press, 1999

Close Connections

Networks are ubiquitous. The brain is a network of neurons. Organizations are networks of people. The global economy is a network of national economies, which are networks of markets, which in turn are networks of producers and consumers. Diseases and rumors both transmit themselves through social networks, and computer viruses propagate via the Internet.

Any kind of network can be represented abstractly by a graph, composed of nodes (or vertices) and a set of lines, edges, joining the nodes. The nodes represent, say, members of a population, and the edges, their interpersonal ties, business ties, friendships, etc. . . . Traditionally, however, networks have been modeled as either completely ordered or completely random. In an ordered network, like a crystal lattice, each node has the same number of edges that join a small number of neighboring nodes in a tightly clustered pattern. In a random network, each node is arbitrarily connected to nodes that can lie anywhere. Although ordered and random networks are in one sense extreme opposites, they share the common feature of uniformity; that is, locally each network "looks" the same everywhere, and this simplifies their analysis.

Do we live in a small world? Under what conditions can any network, social or otherwise, be deemed "small"? And if small-world networks can be shown to exist, what does this imply about the behavior of systems that are connected up that way? These questions, among others, have been the research focus of SFI Postdoctoral Fellow Duncan Watts and his collaborators. This illustrates the random rewiring procedure for interpolating between a regular ring lattice and a random network, without altering the vertices in the graph. Three realizations of this process are shown, for different values of p. For p=0 the original ring is unchanged; as p increases the graph becomes increasingly disordered until for p=1, all edges are rewired randomly. For intermediate values of p, the graph is a small-world network—highly clustered like a regular graph, yet with small characteristic path length, like a random graph.

However, most real-world networks appear to fall somewhere in between the ordered and random extremes. Friendship networks are a good example of this in-between state. Since people meet most new friends through existing friends, the networks are locally ordered. (Here order means that if A knows B and B knows C, then A is more likely to know C than some other random element.) The outcome of local ordering in such a network is that one individual's friends are more likely than not to know one another: a characteristic that is called "clustering." Many real-world networks, including friendship networks, tend to be highly clustered, but they are not entirely so. If a person joins a club and meets new people or moves to a different city to take a job, new connections can form that are not ordered by the existing network.

In order to simulate this kind of intermediate system one might take an ordered network and deliberately introduce increasing amounts of randomness into it. Watts and Steven Strogatz, Watts' thesis advisor at Cornell University, took this approach, called "random rewiring" in order to explore more deeply what would happen to the properties of initially-ordered networks. For example, beginning with the graph of a 1D lattice (simply a ring of nodes, each connected only to its nearest neighbors within a specified radius) they began replacing near-neighbor edges with edges to randomly selected nodes chosen uniformly throughout the network.

To understand the resulting networks, Watts and Strogatz computed two statistics. The first—the characteristic path length—is defined as the length of the shortest path (i.e., smallest number of edges) required to connect one node to another, averaged over all pairs of nodes. The second parameter—the clustering coefficient—measures the average probability that two nodes with a mutual "friend" will be connected, or in other words, the average cliquishness of local neighborhoods. According to these measures, lattice-like networks have long characteristic path lengths and large clustering coefficients, whereas random networks are "small" and exhibit very little clustering at all.

Studying intermediate kinds of networks led to the discovery that when just a few long-range, random connections replace the local edges of a lattice-like network, the characteristic path length decreases dramatically; a "shortcut" occurs. And while the first random rewiring has a great impact on path length, the clustering changes very little. Even when the separation of elements in a network is very small the clustering can remain almost as high as possible. This result is what Watts and Strogatz call a "small-world network." The name derives from the fact that it exhibits the short global separations that are typified (anecdotally) by social interactions while maintaining the high degree of clustering exhibited in most social networks.

Real-world Networks, Small-world Networks

Idealized models like the one just described suggest that the small-world phenomenon might be common in sparse networks with many vertices, as even a tiny fraction of long-range shortcuts would suffice to make the world "small." But does it arise in the real world? Watts and Strogatz set out to check this, selecting three different real-world networks, for which all the data necessary to compute characteristic path length and clustering coefficient was available. The first system was a database of feature-film actors ordered by their appearance in different films; the second was the electric power grid of the Western United States; and the third was the neural network of the nematode worm C. elegans. As Watts and Strogatz wrote in a letter in Nature, "All three graphs are of scientific interest. The graph of film actors is a surrogate for a social network, with the advantage of being much more easily specified. It is also akin to the graph of mathematical collaborations centered, traditionally, on P. Erdos. The graph of the power grid is relevant to the efficiency and robustness of power networks, and C. elegans is the sole example of a completely mapped neural network."

Each of the three graphs turned out to be a small-world network. The scientists were careful to note that these examples were not handpicked. They were chosen for their inherent scientific interest and completeness of available data. What this research suggests is that the small-world phenomenon may be common for many large networks found in nature; it is not merely an artifact of an idealized model.

Network Structure and the Behavior of Dynamical Systems

An obvious question that arises from these conclusions is: What impact might this phenomenon have on the dynamical behavior of a distributed system? Say we're looking at social structure: What is its role in generating globally observable, dynamical features in a social system? In general, if a set of relatively small changes to the edge set of a graph can have a dramatic impact on its global structural properties, might the same changes affect the behavior of dynamical systems that are coupled according to such a graph?

Empirical examples of small-world networks   Lactual Lrandom Cactual Crandom Film actors 3.65 2.99 0.79 0.00027 Power grid 18.7 12.4 0.080 0.005 C. elegans 2.65 2.25 0.28 0.05 Characteristic path length L and clustering coefficient C for three real networks, compared to random graphs with the same number of vertices (n) and average number of edges per vertex (k). All three networks show the small-world phenomenon L ≥ L random but C >> Crandom.

The question is far from straight forward. Even in idealized systems whose behavior offers a relatively clear interpretation, the relationship between structure and dynamics builds on more than one factor. One must consider network structure, as well as a whole literature of distributed dynamical systems, which again traditionally assumes that the relevant coupling topology is either completely ordered or completely random. However, Watts and Strogatz's work suggests that real-world networks may combine significant elements of order and randomness with resultant properties (like small-world connectivity), that cannot be captured by either traditional approach. Thus a realization about network structure suggests a new question for distributed dynamical systems: Do significant new dynamical phenomena emerge when the corresponding network is a small world?

Spread of Infectious Disease

A very simple kind of distributed dynamical system is that of a disease spreading from a small seed of initiators into a much larger population, whose structure is described by some underlying graph. Typically, work on the spread of diseases focuses on populations in which complete mixing is assumed between elements. With this assumption, subsequent analysis of population structure can be ignored and only the relevant sizes of healthy, infected, and immune populations along with the rate of infectiousness need to be known.

Watts and Strogatz took a different approach, simulating the spread of an infectious disease on a simple small-world network model. At time t=0 a single infective is introduced into an otherwise healthy population. After one unit of time, the infective is "removed" (either because it dies or becomes immune) but in that interval it can infect (with some probability) each of its healthy neighbors. The process is then repeated until it reaches a steady state.

Their findings show three distinct regimes of behavior. In the first (for diseases with low infectiousness), the disease infects little of the population before dying out. In the second, a highly infectious disease infects the entire population regardless of its connective topology, but the time taken to reach this steady state varies dramatically as a function of characteristic path length of the network. (Shorter path length implies faster spreading of the disease.) For intermediate levels of infectiousness, there is some complicated relationship between structure and dynamics, which has not yet been completely characterized. Nevertheless, there is a clear correlation between critical infectiousness—the point at which the disease infects a macroscopic fraction of the population—and the amount of randomness in the network. Beyond those conclusions, not much more can be said. However, it is clear that for this dynamical system the attractor for the global dynamics does depend on the coupling topology.

In epidemiological terms, small-world networks imply that the level of infectiousness required for a disease to grow to epidemic proportions can be highly sensitive to the connective topology of the population. This may change our way of looking at social diseases, which are often perceived as confined to isolated subgroups of a population. The highly clustered nature of small-world graphs can lead one to believe that a given disease is "far away" when in fact it is very close. In other words, when looked at on a local level, the change in structure that causes the disease to spread much further and faster may not be observable by an individual who has access only to local information.

Games on Graphs

While the spread of disease presents a relatively simple dynamical system, the question of cooperative behavior emerging among competitive agents playing a many-player game is significantly more complicated. Since disease is involuntary and mechanical, it is only on the edge of truly social behavior. However, human behavior as measured through games can bring up more complex behavior.

One such game is the Prisoner's Dilemma, which models a situation of two partners in crime who are captured and locked in separate cells between which they are unable to communicate. The dilemma concerns whether each prisoner ought to "cooperate" by remaining silent or "defect" by selling out their partner in order to reap a reward. This game acts as a model for many kinds of interactions (from common pool resource problems to international arms negotiations). The main focus is that essentially competitive agents need to overcome the temptation to exploit each other if they are to reap the rewards of reciprocal cooperation.

C D C (3,3) (0,5) D (5,0) (1,1) Prisoner's Dilemma The conundrum of the Prisoner's Dilemma is captured in the chart above. Defection (D) yields either 5 or 1, and cooperation yields either 3 or 0. The rational decision is to defect. If both prisoners are rational, since they both have the same information, both defect, yielding a payoff of 1 each. If both prisoners cooperate—if both remain silent—both will earn a 3, a considerably better outcome than that generated by the rational action.

Some early and influential research on the subject was done by Robert Axelrod at the University of Michigan, who devised a computer tournament in which players (computer programs) using different strategies competed against each other. Axelrod found that the strategies that performed best did so not by exploiting the weaknesses of others, but by eliciting cooperation, thus allowing both sides to do well. A strategy known as "Tit-for-Tat" devised by Anatol Rapoport (on the basis of his observations of human behavior two decades earlier) emerged as the most effective. Its rules are simple: "Cooperate at first and then, on succeeding turns, do whatever the other player did on the previous turn." The trademarks of TFT—being "nice," "forgiving," "retaliatory" and "transparent"—emerged as generic markers for any strategy to be successful in a sufficiently heterogeneous environment.

In much of the early work on the Prisoner's Dilemma, the population is treated as essentially structureless, a reasonable starting assumption, but not very realistic for large social systems. Lately, interest has emerged into the evolution of cooperation in the presence of population structure, but generally this work has focused on either one- or two-dimensional space. Watts and Strogatz, interested in this question, adopted a generalized version of Tit-for-Tat that could be used by players located on an arbitrary graph. In their version the formulation was entirely local; players could only react to the conditions within their immediate social and temporal neighborhoods.

Similar to the case with the spread of disease, Watts and Strogatz found three regimes of behavior in their simulation. For large h, where now the variable parameter is the average hardness (h) of players—the "harder" a player is, the more reluctant it is to cooperate. Regardless of population structure, cooperation always dies out; for sufficiently low h, cooperation always dominates, but the timescale depends quite sensitively on the fraction of shortcuts; and for intermediate h, how much cooperation succeeds depends on the fraction of shortcuts. What became clear throughout is that as the number of shortcuts increases, cooperation is increasingly difficult to sustain. This is due to the fact that cooperation in the Prisoner's Dilemma context requires that potential cooperators interact with each other preferentially. In this case, in a highly clustered graph, cooperators located in the same cluster can survive, even thrive, even within a noncooperative majority. However, the introduction of even a few shortcuts can weaken the cooperators' position. Those who believe in altruism will be happy to know that if the greater population is sufficiently predisposed to cooperate in the first place, then cooperation will spread much faster in a small world than in a large one.

For those seeking to optimize both the spread and sustenance of cooperation, the primary task is striking a balance between high clustering and speedy transmission. Since small-world topology exhibits both these features it may be truly useful to such an endeavor. However, the matter is not straightforward, even for this model, because for any given constant population structure, any change in the disposition toward cooperation (hardness) can tip the balance from rapid growth to rapid decline. Nevertheless, in the design of organizational structures, the idea of optimizing between clustering and length may be a useful concept.

Next Steps

The work by Watts and Strogatz suggests that distributed systems can exhibit dramatically different behavior within the structural context of small-world networks. In fact, the research has set off a small avalanche among researchers in both the natural and social sciences to explore the implications of the small-world phenomenon. At the Institute, Watts and SFI Research Professor Mark Newman have been examining the scaling properties, phase transitions, and site percolation properties of small-world graphs. Another aspect of the phenomenon will be studied in a working group organized by Charles Sabel on using the intuitions from small-world dynamics to increase the effectiveness of organizations solving complex problems in rapidly changing environments. As Watts notes in one of his early papers on the subject, the notion of small-world connectivity "may have implications in fields as diverse as public health, organizational behavior, and design." The work has just begun.