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, ScienceWatch.com 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?

Coauthor
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