Paper: Watts, D. and S. Strogatz (1998). Collective dynamics of 'small-world' networks. Nature 393:440-42.
Type of summary: Abstract
Problem definition: The authors explore the characteristics of 'small-world' graphs, in particular the characteristic path length L(p) and the clustering coefficient C(p), as a function of the probability p of randomly rewiring edges of a ring lattice graph.
Context (related work): Other works studying the topology of dynamic systems at the time would assume the underling graph structure to be either completely random or entirely regular.
Hypothesis: The values of L(p) and C(p) don't display a linear behaviour, as one would expect. Instead, for a certain interval of p, the graphs have low L(p) and high C(p).
Evidence: The authors simulate many graphs through a constructive algorithm following the small-world model, for different values of p, and compute L(p) and C(p). They also examine real world networks, such as the power grid, IMDB and neural network of C. elegans, which display the small world structure.
Contributions: This article provides a new model for random networks which lies between completely random and regular networks. The authors make the case that such model could be frequently found in social, biological and man-made systems and study its behaviour in important contexts such as that of disease spreading.