(원문)
The idea that everyone in the world is connected to everyone else by just six degrees of separation was explained by the ‘small-world’ network model 20 years ago. What seemed to be a niche finding turned out to have huge consequences.
In 1998, Watts and Strogatz1 introduced the ‘small-world’ model of networks, which describes the clustering and short separations of nodes found in many real-life networks. I still vividly remember the discussion I had with fellow statistical physicists at the time: the model was seen as sort of interesting, but seemed to be merely an exotic departure from the regular, lattice-like network structures we were used to. But the more the paper was assimilated by scientists from different fields, the more it became clear that it had deep implications for our understanding of dynamic behaviour and phase transitions in real-world phenomena ranging from contagion processes to information diffusion. It soon became apparent that the paper had ushered in a new era of research that would lead to the establishment of network science as a multidisciplinary field.
Before Watts and Strogatz published their paper, the archetypical network-generation algorithms were based on construction processes such as those described by the Erdös–Rényi model2. These processes are characterized by a lack of knowledge of the principles that guide the creation of connections (edges) between nodes in networks, and make the simple assumption that pairs of nodes can be connected at random with a given connection probability. Such a process generates random networks, in which the average path length between any two nodes in the network — measured as the smallest number of edges needed to connect the nodes — scales as the logarithm of the total number of nodes. In other words, randomness is sufficient to explain the small-world phenomenon popularized as ‘six degrees of separation’3,4: the idea that everyone in the world is connected to everyone else through a chain of, at most, six mutual acquaintances.
However, random construction fell short of capturing the local cliquishness of nodes observed in real-world networks. Cliquishness is measured quantitatively by the clustering coefficient of a node, which is defined as the ratio of the number of links between a node’s neighbours and the maximum number of such links. In real-world networks, node clustering is clearly exemplified by the axiom ‘the friends of my friends are my friends’: the probability of three people being friends with each other in a social network, for example, is generally much higher than would be predicted by a model network constructed using the simple, stochastic process.
To overcome the dichotomy between randomness and cliquishness, Watts and Strogatz proposed a model whose starting point is a regular network that has a large clustering coefficient. Stochasticity is then introduced by allowing links to be rewired at random between nodes, with a fixed probability of rewiring (p) for all links. By tuning p, the model effectively interpolates between a regular lattice (p → 0) and a completely random network (p → 1).
At very small p values, the resulting network is a regular lattice and therefore has a high clustering coefficient. However, even at small p,short cuts appear between distant nodes in the lattice, dramatically reducing the average shortest path length (Fig. 1). Watts and Strogatz showed that, depending on the number of nodes5, it is possible to find networks that have a large clustering coefficient and short average distances between nodes for a broad range of p values, thus reconciling the small-world phenomenon with network cliquishness.
Figure 1 | The small-world network model. In 1998, Watts and Strogatz1 described a model that helps to explain the structures of networks in the real world. a, They started with a regular network, depicted here as nodes connected in a triangular lattice in which each node is connected to six other nodes. b, They then allowed links between nodes to be rewired at random, with a fixed probability of rewiring for all links. As the probability increases, an increasing number of short cuts (red lines) connect distant nodes in the network. This generates the small-world effect: all nodes in the network can be connected by passing along a small number of links between nodes, but neighbouring nodes are connected to one another, forming clustered cliques.
Watts and Strogatz’s model was initially regarded simply as the explanation for six degrees of separation. But possibly its most important impact was to pave the way for studies of the effect of network structure on a wide range of dynamic phenomena. Another paper was also pivotal: in 1999, Barabási and Albert proposed the ‘preferential-attachment’ network model6, which highlighted that the probability distribution describing the number of connections that form between nodes in real-world networks is often characterized by ‘heavy-tailed’ distributions, instead of the Poisson distribution predicted by random networks. The broad spectrum of emergent behaviour and phase transitions encapsulated in networks that have clustered connectedness (as in Watts and Strogatz’s model) and heterogeneous connectedness (as in the preferential-attachment model) attracted the attention of scientists from many fields.
A string of discoveries followed, highlighting how the complex structure of such networks underpins real-world systems, with implications for network robustness, the spreading of epidemics, information flow and the synchronization of collective behaviour across networks7,8. For example, the small-world connectivity pattern proved to be the key to understanding the structure of the World Wide Web9 and how anatomical and functional areas of the brain communicate with each other10. Other structural properties of networks came under the microscope soon after11–13, such as modularity and the concept of structural motifs, all of which helped scientists to characterize and understand the architecture of living and artificial systems, from subcellular networks to ecosystems and the Internet.
The current generation of network research cross-fertilizes areas that benefit from unprecedented computing power, big data sets and new computational modelling techniques, and thus provides a bridge between the dynamics of individual nodes and the emergent properties of macroscopic networks. But the immediacy and the simplicity of the small-world and preferential-attachment models still underpin our understanding of network topology. Indeed, the relevance of these models to different areas of science laid the foundation of the multidisciplinary field now known as network science.
Integrating knowledge and methodologies from fields as disparate as the social sciences, physics, biology, computer science and applied mathematics was not easy. It took several years to find common ground, agree on definitions and reconcile and appreciate the different approaches that each field had adopted to study networks. This is still a work in progress, presenting all the difficulties and traps inherent in interdisciplinary work. However, in the past 20 years a vibrant network-science community has emerged, with its own prestigious journals, research institutes and conferences attended by thousands of scientists.
By the 20th anniversary of the paper, more than 18,000 papers have cited the model, which is now considered to be one of the benchmark network topologies. Watts and Strogatz closed their paper by saying: “We hope that our work will stimulate further studies of small-world networks.” Perhaps no statement has ever been more prophetic.