September 11, 2005

Duncan Watts: "Networks, Dynamics, and the Small-World Phenomenon"

Watts, Duncan J. "Networks, Dynamics, and the Small-World Phenomenon."
American Journal of Sociology. 1999, 105, 2, Sept, 493-527.

Abstract:

The small-world phenomenon formalized in this article as the coincidence of high local clustering and short global separation, is shown to be a general feature of sparse, decentralized networks that are neither completely ordered nor completely random. Networks of this kind have received little attention, yet they appear to be widespread in the social and natural sciences, as is indicated here by three distinct examples. Furthermore, small admixtures of randomness to an otherwise ordered network can have a dramatic impact on its dynamical, as well as structural, properties - a feature illustrated by a simple model of disease transmission.

Overview:

Watts begins by offering a historical overview of studies seeking to understand the small-world phenomenon. In defining the phenomenon, he articulates four axioms:

  • The network is numerically large in the sense that the world contains n people. In the real world, n is on the order of billions.
  • The network is sparse in the sense that each person is connected to an average of only k other people, which is, at most, on the order of thousands (Kochen 1989) - hundreds of thousands of times smaller than the population of the planet.
  • The network is decentralized in that there is no dominant central vertex to which most other vertices are directly connected. This implies a stronger condition than sparseness: not only must the average degree k be much less than n, but the maximal degree k max over all vertices must also be much less than n.
  • The network is highly clustered, in that most friendship circles are strongly overlapping. That is, we expect that many of our friends are friends also of each other.

From the axioms, Watts lays out a model for the small-world problem in a theoretical investigation of the structure that would allow for comparisons between actual and modeled. He constrains his model dependent on assumptions necessary to make it work (i.e. everyone has to be connected, ties are mutual). He offers different types of topologies that might emerge. The small-world comes about as a coincidence of high local clustering and short global separation.

After laying out this model, he refers back to case studies from network analysis for comparison (movie actors, power grids, neural networks, disease spread).

Commentary:

This is a theoretical structural paper; it is building models based on mathematic assumptions connected at some level to social occurrences but the model is not based on them. More than anything, the value of this paper is in defining the constraints that must be considered when reflecting on small-world problems. I'm not sure what these models or their miniature tests on closed systems can tell us about global networks.

Posted by zephoria at 1:03 AM | Comments (1) | TrackBack (0)