Collective Dynamics of ‘Small-world’ Networks

Networks,Reading,Science — Zac Townsend @ October 29, 2012 11:50 am

This article explores the dynamics of a network that is somewhere between regular and random.Regular networks are those where every node has the same number of connections. On the other hand, random networks are those that are built by introducing new nodes and randomly assigning edges between the new nodes and the old nodes with some probability, p (see the Erdos-Renyi model).

This paper "interpolates" between these two models by starting with a regular network (a ring lattice to be precise) and then rewiring each edge at random with probability p; in this way the graph is "tuned" between regular (p=0) and complete disorder / randomness (p=1).

To continue, we have to understand two measures that are often used in network theory: L(p) and C(p). L(p) is the average shortest length between all pairs of nodes. That is, if you find the shortest path between all pairs of nodes and then you take the average of those shortest paths you get L(p). C(p) is the clustering coefficient and is a measure of how many links exist between nodes divided by the number of possible such links.

For friendship networks, these statistics have intuitive meanings: L is the average number of friendships in the shortest chain connecting two people; C_v reflects the extent to which friends of v are also friends of each other; and thus C measures the cliquishness of a typical friendship circle.

The p=0 case is a "highly clustered, large world where L grows linearly with n" while the p=1 case is a "poorly clustered, small world where L grows only logarithmically with n". The key insight here is that allow it appears form these end points that large C and large L (and small C and small C) would always be associated from this simple analysis, it turns out that there is a "broad interval" where things stay clustered but the average length between nodes (L(P)) drops quickly. It's a "small world" because as you move, even just a little but, from a regular network to a random one there are introduced "short cuts" between groups that decreases the length: "The important implication here is that at the local level (as reflected by C(p)), the transition to a small world is almost undetectable."

The rest of the paper (Nature articles are quite short) shows three empirical examples fit this "small world" network model--IMDB film actors, the power gift, and the neural network of a nematode worm. The paper then finishes testing the implication of the network on a simulated disease outbreak where they show that 1) the smaller the L(p) of a network the faster the infection effects the entire population, 2) That a network just needs to be a little not regular for L(p) to drop significantly and 3) If it's a small world disease spread much more quickly than previous models suggest.

We hope that our work will stimulate further studies of smallworld 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.


  1. [...] some assumption that every node has the same number of edges, see regular networks from yesterday's post) because neither of these network types, however, is a satisfactory model of society. (As an aside, [...]

  2. [...] described by the random network model of Erdos and Renyi (the "ER" model). But, the ER model (and the WS model) is not up to the task of explaining the scale-free power law distributions that they find by [...]

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.