Collective dynamics of 'small-world' networks

Abstract

Networks of coupled dynamical systems have been used to model biological oscillators[1-4], Josephson junction arrays[5,6], excitable media[7], neural networks[8–10], spatial games[11], genetic control networks[12] and many other self-organizing systems. Ordinarily,the connection topology is assumed to be either completely regular or completely random. But many biological, technological and social networks lie somewhere between these two extremes. Here we explore simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder. We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them ‘small-world’ networks,by analogy with the small-world phenomenon[13,14] (popularly known as six degrees of separation[15]). The neural network of the worm Caenorhabditis elegans, the power grid of the western United States, and the collaboration graph of film actors are shown to be small-world networks. Models of dynamical systems with small-world coupling display enhanced signal-propagation speed, computational power, and synchronizability. In particular, infectious diseases spread more easily in small-world networks than in regular lattices.

Paper

To interpolate between regular and random networks, we consider the following random rewiring procedure (Fig. 1). Starting from a ring lattice with $n$ vertices and $k$ edges per vertex, we rewire each edge at random with probability $p$. This construction allows us to ‘tune’ the graph between regularity ($p=0$) and disorder ($p=1$), and thereby to probe the intermediate region $0< p < 1$, about which little is known.

We quantify the structural properties of these graphs by their characteristic path length $L(p)$ and clustering coefficient $C(p)$, as defined in Fig. 2 legend. Here $L(p)$ measures the typical separation between two vertices in the graph (a global property), whereas $C(p)$ measures the cliquishness of a typical neighbourhood (a local property). The networks of interest to us have many vertices with sparse connections, but not so sparse that the graph is in danger of becoming disconnected. Specifically, we require $n \gg k \gg \ln(n) \gg 1$, where $k \gg \ln(n)$ guarantees that a random graph will be connected[16]. In this regime, we find that $L \sim n/2k \gg 1$ and $C \sim 3/4$ as $p \to 0$, while $L \approx L_\text{random} \sim \ln(n)/\ln(k)$ and $C \approx C_\text{random} \sim k/n \ll 1$ as $p \to 1$. Thus the regular lattice at $p=0$ is a highly clustered, large world where $L$ grows linearly with $n$, whereas the random network at $p=1$ is a poorly clustered, small world where $L$ grows only logarithmically with $n$. These limiting cases might lead one to suspect that large $C$ is always associated with large $L$, and small $C$ with small $L$.

On the contrary, Fig. 2 reveals that there is a broad interval of $p$ over which $L(p)$ is almost as small as $L_\text{random}$ yet $C(p) \gg C_\text{random}$. These small-world networks result from the immediate drop in $L(p)$ caused by the introduction of a few long-range edges. Such ‘short cuts’ connect vertices that would otherwise be much farther apart than $L_\text{random}$. For small $p$, each short cut has a highly nonlinear effect on $L$, contracting the distance not just between the pair of vertices that it connects, but between their immediate neighbourhoods, neighbourhoods of neighbourhoods and so on. By contrast, an edge removed from a clustered neighbourhood to make a short cut has, at most, a linear effect on C; hence $C(p)$ remains practically unchanged for small $p$ even though $L(p)$ drops rapidly. The important implication here is that at the local level (as reflected by $C(p)$), the transition to a small world is almost undetectable. To check the robustness of these results, we have tested many different types of initial regular graphs, as well as different algorithms for random rewiring, and all give qualitatively similar results. The only requirement is that the rewired edges must typically connect vertices that would otherwise be much farther apart than $L_\text{random}$

The idealized construction above reveals the key role of short cuts. It suggests that the small-world phenomenon might be common in sparse networks with many vertices, as even a tiny fraction of short cuts would suffice. To test this idea, we have computed $L$ and $C$ for the collaboration graph of actors in feature films (generated from data available at http://us.imdb.com), the electrical power grid of the western United States, and the neural network of the nematode worm C. elegans[17]. All three graphs are of scientific interest. The graph of film actors is a surrogate for a social network[18], with the advantage of being much more easily specified. It is also akin to the graph of mathematical collaborations centred, traditionally, on P. Erdos (partial data available at http://www.acs.oakland.edu/~grossman/erdoshp.html). The graph of the power grid is relevant to the efficiency and robustness of power networks[17]. And C. elegans is the sole example of a completely mapped neural network.

Table 1 shows that all three graphs are small-world networks. These examples were not hand-picked; they were chosen because of their inherent interest and because complete wiring diagrams were available. Thus the small-world phenomenon is not merely a curiosity of social networks[13, 14] nor an artefact of an idealized model – it is probably generic for many large, sparse networks found in nature.

⊕ Table 1: Empirical examples of small-world networks 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$). (Actors: n = 225,226, k = 61. Power grid: n = 4,941, k = 2.67. C. elegans: n = 282, k = 14.) The graphs are defined as follows. Two actors are joined by an edge if they have acted in a film together. We restrict attention to the giant connected component[16] of this graph, which includes ~90% of all actors listed in the Internet Movie Database (available at http://us.imdb.com), as of April 1997. For the power grid, vertices represent generators, transformers and substations, and edges represent high-voltage transmission lines between them. For C. elegans, an edge joins two neurons if they are connected by either a synapse or a gap junction. We treat all edges as undirected and unweighted, and all vertices as identical, recognizing that these are crude approximations. All three networks show the small-world phenomenon: $L \gtrsim L_\text{random}$ but $C \gg C_\text{random}$.

We now investigate the functional significance of small-world connectivity for dynamical systems. Our test case is a deliberately simplified model for the spread of an infectious disease. The population structure is modelled by the family of graphs described in Fig. 1. At time $t = 0$, a single infective individual is introduced into an otherwise healthy population. Infective individuals are removed permanently (by immunity or death) after a period of sickness that lasts one unit of dimensionless time. During this time, each infective individual can infect each of its healthy neighbours with probability $r$. On subsequent time steps, the disease spreads along the edges of the graph until it either infects the entire population, or it dies out, having infected some fraction of the population in the process.

Two results emerge. First, the critical infectiousness $r_\text{half}$, at which the disease infects half the population, decreases rapidly for small $p$ (Fig. 3a). Second, for a disease that is sufficiently infectious to infect the entire population regardless of its structure, the time $T(p)$ required for global infection resembles the $L(p)$ curve (Fig. 3b). Thus, infectious diseases are predicted to spread much more easily and quickly in a small world; the alarming and less obvious point is how few short cuts are needed to make the world small.

Our model differs in some significant ways from other network models of disease spreading[20-24]. All the models indicate that network structure influences the speed and extent of disease transmission, but our model illuminates the dynamics as an explicit function of structure (Fig. 3), rather than for a few particular topologies, such as random graphs, stars and chains[20-23]. In the work closest to ours, Kretschmar and Morris[24] have shown that increases in the number of concurrent partnerships can significantly accelerate the propagation of a sexually-transmitted disease that spreads along the edges of a graph. All their graphs are disconnected because they fix the average number of partners per person at $k = 1$. An increase in the number of concurrent partnerships causes faster spreading by increasing the number of vertices in the graph’s largest connected component. In contrast, all our graphs are connected; hence the predicted changes in the spreading dynamics are due to more subtle structural features than changes in connectedness. Moreover, changes in the number of concurrent partners are obvious to an individual, whereas transitions leading to a smaller world are not.

We have also examined the effect of small-world connectivity on three other dynamical systems. In each case, the elements were coupled according to the family of graphs described in Fig. 1.

1. For cellular automata charged with the computational task of density classification[25], we find that a simple ‘majority-rule’ running on a small-world graph can outperform all known human and genetic algorithm-generated rules running on a ring lattice.
2. For the iterated, multi-player ‘Prisoner’s dilemma’[11] played on a graph, we find that as the fraction of short cuts increases, cooperation is less likely to emerge in a population of players using a generalized ‘tit-for-tat’[26] strategy. The likelihood of cooperative strategies evolving out of an initial cooperative/non-cooperative mix also decreases with increasing $p$.
3. Small-world networks of coupled phase oscillators synchronize almost as readily as in the mean-field model[2], despite having orders of magnitude fewer edges. This result may be relevant to the observed synchronization of widely separated neurons in the visual cortex[27] if, as seems plausible, the brain has a small-world architecture.

We hope that our work will stimulate further studies of small-world networks. Their distinctive combination of high clustering with short characteristic path length cannot be captured by traditional approximations such as those based on regular lattices or random graphs. Although small-world architecture has not received much attention, we suggest that it will probably turn out to be widespread in biological, social and man-made systems, often with important dynamical consequences.