Archive ScienceWatch

Watts Duncan Watts & Steve Strogatz
Featured Scientist from Essential Science IndicatorsSM

According to Essential Science Indicators from Thomson Reuters, the paper "Collective dynamics of 'small-world' networks" (Nature 393[6684]: 440-2, 4 June 1998) by Duncan Watts and Steven Strogatz, ranks at #6 among Highly Cited Papers in Physics. This paper has garnered 2,700 citations between January 1, 1998 and August 31, 2008.

Duncan Watts is a Principal Research Scientist at Yahoo! Research, where he directs the Human Social Dynamics Group, as well as a Professor of Sociology at Columbia University. Steven Strogatz is the Jacob Gould Schurman Professor of Applied Mathematics in the Department of Theoretical and Applied Mechanics at Cornell University.

In the interview below, talks with both authors about this paper and its impact on a variety of fields.

What was your inspiration for this study reported in your paper?

Our first source of inspiration was a project we had started on the collective synchronization of crickets. In that project, our question had been, "how do hundreds of snowy tree crickets spontaneously fall into a state where they’re all chirping in unison?" We thought this might be a tractable experimental system for studying biological synchronization more generally. Theories had been around since the 1960s, but nobody had tested them quantitatively in any real biological system. So we began working with Tim Forrest, an entomologist who taught us about crickets and bioacoustics and led our experimental efforts.

Meanwhile, we began ruminating about the theoretical side of the problem, and it occurred to us that we had no idea how the crickets were connected. Who was listening to whom? Did a cricket pay attention only to its nearest neighbors, or was it responding to the entire population, or to something in between those two extremes? And did the details of the connectivity even matter?

Steve Strogatz

These were the kinds of questions that led us to thinking about connectivity more generally and about its potential impact on dynamical processes like synchronization. Of course, physicists and mathematicians had made great progress in the study of coupled dynamical systems, but only under the assumption that these systems were coupled in particularly simple ways—like a regular lattice, or uniform mixing.

Our other source of inspiration, meanwhile, was the notion of "six degrees of separation," which had just entered popular consciousness in the mid-1990s. The play and movie with that name had come out a few years earlier, and it was natural for a mathematically minded person to begin thinking about the small-world phenomenon and the math that must lurk behind it. Pretty soon, we figured out that sociologists, graph theorists, and others had been interested in describing the structure of various types of real-world networks for many years. But once again, little work had been done to link the network properties they were measuring to the dynamical properties—like information propagation, epidemics of disease, herding behavior, cascading failures—of the systems that the networks were connecting.

In a sense, therefore, what we set out to do was introduce some of the features of real-world networks into models of dynamical systems, and thereby try to unify these two fields—network analysis and dynamical systems theory—that had, up to then, developed largely in isolation. In particular, we wondered whether dynamical systems connected in a "six degrees" way might be capable of collective behavior that was very different from what had been seen on more traditional topologies like square grids or random graphs.

How did you perform this study—what were your methods?

In general, problems to do with the structure of complex networks are not amenable to traditional analytical methods; so although we did make some simple back-of-the-envelope calculations, we relied mostly on computer simulations. Ten years ago, desktop computers were not nearly as powerful as they are today, but they were still capable of running simulations that only a few years earlier would have required access to institutional computing facilities. So we were able to study networks (both models and also empirical examples) that were considerably larger than those studied previously. The size was important, because some of the phenomena we were interested in only became relevant in "large" networks of thousands, or even millions of nodes.

Would you sum up your findings for our readers?

Our paper made three separate, but related, contributions. First, we introduced a simple parameterized family of models that exhibited an interesting combination of properties—specifically, high local "clustering" and short global path lengths—that were reminiscent of Stanley Milgram’s famous "small-world" problem.

Second, we showed that these "small-world" networks arose naturally in at least three very different real-world domains—collaborations of movie actors, the power transmission grid of the western United States, and the neural network of C. elegans—suggesting that the "small-world" network architecture might be a very general one. Up to that point, network analysts had tended to study a single network at a time—and certainly not networks from different domains—so our finding that at least one property of networks might be shared across very different domains was also new.

And third, we showed that the structural properties of "small-world" networks could have a dramatic impact on their dynamical properties, like, for example, the size and speed of an epidemic of disease, or the computational capability of cellular automata.

You talk about how "infectious diseases spread more easily in small-world networks than in regular lattices." Could you talk about this point a little?

In perfectly regular lattices, every node’s neighbors also tend to be connected to each other, and this local redundancy, or "clustering," acts as a natural break on the spread of a disease; clearly if all the neighbors of an infected node are also already infected, the disease has few places to go. In a random network, by contrast, there is no such clustering, meaning that almost every neighbor of any given infected node will be susceptible; thus, diseases can spread with maximum efficiency. Both these results are obvious, but what we found that is less obvious is that when just a tiny fraction of the links in a regular lattice are randomly rewired, diseases can spread almost as well as they do in a completely random network.

"...we’re interested in using the web as a virtual lab to run very large-scale, human subjects experiments."

Because so little randomness is required, this finding suggests that stopping diseases from spreading in the real world probably requires getting to them very close to their source, while they are still impeded by the local clustering. Unfortunately, it also suggests that human psychology may be particularly poor at understanding the threat posed by infectious diseases: because we all live in little, homogenous clusters, we may perceive diseases as being distant, and therefore not our concern, whereas in fact they are much closer to us than they appear.

How was this paper received by the community?

It was received with a lot more excitement than we had bargained for. We had already run our ideas past a few smart colleagues, and they couldn’t see the point of what we’d done. One dismissed it as a rehash of percolation theory and another thought it was just a routine question about the diameter of a random graph. From talking to our nonscientific friends, however, we thought our ideas would appeal to the general public. Networks were just starting to be in the air. The Web had exploded in 1994, and was raising general awareness of the presence of networks in people’s lives, and the Kevin Bacon game was the biggest craze of 1996. So in one sense, at least, the interest could be attributed to good (and lucky!) timing.

The other source of interest, however, was that our paper pointed out a whole new class of problems at the intersection of networks and dynamical systems where physicists felt they could make a contribution. They could do empirical work on real networks, like food webs, power grids, gene networks, and the Internet. They could make better models of complex networks and analyze them with graph theory or statistical mechanics. They could study dynamical systems on networks and ask how the topology affects the collective behavior. As a result, while a number of the papers that followed were devoted to analyzing or extending the specific model we proposed, many more were motivated more generally by our approach of using simple, generative models to understand complex network dynamics.

Where have you taken your small-world networks research since the publication of the 1998 paper?

One direction we have pursued since the paper was inspired by the subsequent work of Jon Kleinberg, who pointed out that the small-world problem implies not only that short paths exist between distant pairs of individuals, but also that they can find these paths; thus the small-world problem is essentially a search problem. Searching in networks is actually a very general idea that applies to "networking" for jobs and resources, and also collaborative problem solving. So we’re very interested in understanding what it is about the structure of networks that allows people to network.

Another direction is to understand how individual choices are influenced by the choices of others, and under what conditions social influence can propagate through a network. Parallels with the spread of infectious disease are obvious, but also possibly misleading; so we’re also interested in characterizing different classes of "influence response functions" and how they lead to different collective phenomena.

Third, we’re interested in using new technologies, like email and social networking services, to map out very large social networks, and to study their evolution over time. The standard mental model of a network as a static "web" may be accurate for some applications, like power-transmission grids, that change only on time scales much longer than the phenomena of interest, but it is probably quite inaccurate for other applications, like social networks, where new relationships are constantly forming, and old ones are lapsing. Understanding when it is necessary to adopt a dynamic view of the networks themselves, and how to model such networks, are therefore questions of great interest to us.

Finally, we’re interested in using the web as a virtual lab to run very large-scale, human subjects experiments. We have already conducted a couple of these experiments—one, a recreation of Stanley Milgram’s original small-world experiment, and the other a virtual "market" for music—but we feel we have barely scratched the surface of what is possible.

What are your hopes for this field for the future?

The activity of the last ten years has been very exciting. Thousands of papers have been written, many new models and empirical networks have been studied, and we are even beginning to see the outlines of a new field that we might call "Network Science."

In spite of all this progress, however, we are still a long way from understanding the kinds of questions that originally motivated us. We can’t use network analysis to ward against epidemics of disease or estimate the risk of widespread financial meltdowns. We don’t know why some people are better at networking than others, or why some organizations survive catastrophic failures while others don’t. And we don’t understand how to design networks to foster cooperation, improve computation, or speed communication in real systems.

Admittedly these are big questions, so it’s not surprising that we don’t yet have answers to them. But real progress will require moving beyond simple models of networks, and paying more attention to their empirical details—not just the direction and strength of ties, but also the presence of many types of ties defined on the same node set. We also hope to see the emergence of better and more consistent protocols for collecting and analyzing data—especially longitudinal data—such that the results of different studies can be meaningfully compared. And finally, we hope to see more emphasis on experimental rather than purely observational studies.

What would you like the "take-away lesson" about your research to be?

Our main message is the same as it has always been: that the behavior of complex interconnected systems cannot be understood without also understanding the role played by the network. These days, it’s become conventional to say that "networks matter," but as the current financial crisis illustrates quite painfully, we still don’t understand how. Getting network science to the point where we do understand will not be easy, but the good news is that there will be interesting and important questions remaining to be answered for many years to come.

Duncan J. Watts, Ph.D.
Yahoo! Research
New York, NY, USA

Steven H. Strogatz, Ph.D.
Department of Theoretical and Applied Mechanics
Cornell University
Ithaca, NY, USA

Duncan Watts & Steve Strogatz's current most-cited paper in Essential Science Indicators, with 2,700 cites:
Watts DJ and Strogatz SH, "Collective dynamics of 'small-world' networks," Nature 393(6684): 440-2, 4 June 1998. Source: Essential Science Indicators from Thomson Reuters.

Keywords: small-world networks, biological synchronization, six degrees of separation, dynamical systems, complex networks, structural properties, real-life networks.

Download this article

2008 : December 2008 - Author Commentaries : Duncan Watts & Steve Strogatz