The "new" science of networks.

INTRODUCTION

Building on a long tradition of network analysis in sociology and anthropology (Degenne & Forse 1994, Scott 2000, Wasserman & Faust 1994) and an even longer history of graph theory in discrete mathematics (Ahuja et al. 1993, Bollobas 1998, West 1996), the study of networks and networked systems has exploded across the academic spectrum in the past five years. Spurred by the rapidly growing availability of cheap yet powerful computers and large-scale electronic datasets, researchers from the mathematical, biological, and social sciences have made substantial progress on a number of previously intractable problems, reformulating old ideas, introducing new techniques, and uncovering connections between what had seemed to be quite different problems. The result has been called the "new science of networks" (Barabasi 2002, Buchanan 2002, Watts 2003)--a label that may strike many sociologists as misleading, given the familiarity (to social network analysts) of many of its central ideas. Nevertheless, the label does capture the sense of excitement surrounding what is unquestionably a fast developing field--new papers are appearing almost daily--and also the unprecedented degree of synthesis that this excitement has generated across the many disciplines in which network-related problems arise.

In reviewing the main results of this field, I have tried to strike a balance between the historical progression of the ideas and their logical order. To this end, the first section describes the main network modeling approaches, regarding local structure, global connectivity, searchability, and highly skewed degree distributions. I then summarize related empirical studies and discuss some of the issues associated with interpreting empirical data. Finally, I review preliminary progress on applications of network models to dynamical processes like disease spreading and information exchange. Throughout the discussion, I focus on the motivation and interpretation of ideas and results, referring the reader elsewhere (Newman 2003c) for the mathematical details. And although I concentrate on developments that seem most relevant to social networks, it is worth bearing in mind that many of the same results have been applied to, or motivated by, problems in other disciplines.

MODELS OF NETWORK STRUCTURE

Small-World Networks

An early contribution to the new science of networks, and one that captures some of its major themes, was that by Watts & Strogatz (1998), in which the authors made several related but distinct points:

1. Real-world networks are neither completely ordered nor completely random, but rather exhibit important properties of both.

2. Some properties of these networks can be embodied by simple mathematical models that interpolate between order and randomness. In Watts & Strogatz's specific example, "order" was represented by a uniform one-dimensional lattice, where each node was connected to its k nearest neighbors on the lattice, (1) and "randomness" was characterized by a tunable parameter p that specified the fraction of randomly rewired links (see Figure 1a).

[FIGURE 1 OMITTED]

3. These properties can be quantified with simple statistics: for example, the clustering coefficient C of a network is a measure of local density, and the average shortest path length L is a global measure of separation. In the case of the proposed model, L and C can be measured as a function of p.

4. When p = 0 (completely ordered), the network is "large" [L(0) ~ N/2k] and "highly clustered" [C(0) ~ 3/4], and when p = 1 (completely random), it is "small" [L(1) ~ ln(N)/ln(k)] and "poorly clustered" [C(1) ~ k/N], suggesting that path lengths are short only when clustering is low.

5. However, the model exhibits a broad region of p values in which C(p) is high relative to its random limit C(1), yet L(p) is, roughly speaking, as "small" as possible (see Figure 1b). Watts & Strogatz (1998) coined the term small-world networks (2) to refer to networks in this class, in reference to the early work of Pool & Kochen (1978), and subsequent experiments of Milgram and colleagues (Korte & Milgram 1970; Milgram 1967; Travers & Milgram 1969).

6. Because the conditions required for any network to belong to the small-world class (some nontrivial local order, combined with just a small fraction of long-range, random shortcuts) were relatively weak, Watts & Strogatz (1998) predicted that many real-world networks--whether social networks or otherwise--ought to be small-world networks. They then checked this prediction by considering three network datasets--the affiliation network of movie actors, the power transmission grid of the western United States, and the neural network of the nematode Caenorhabditis elegans--and found that all three examples satisfied the small-world criteria.

7. Finally, the authors claimed that the structure of a network can have dramatic implications for the collective dynamics of a system, whose connectivity the network represents. In particular, they claimed that large changes in dynamical behavior could be driven by even subtle modifications to the network structure--modifications that may be imperceptible to actors with only local knowledge of the network. They supported this claim with the example of a simple disease-spreading model, demonstrating that both the extent of an epidemic, and also the time taken for it to spread, were sensitively dependent on the level of randomness in the network--only a small amount of randomness was required for large, rapidly spreading epidemics to occur. In related work, Watts (1999) found equally dramatic effects of network structure on dynamics for the emergence of cooperation in a multiplayer game of Prisoner's Dilemma, the synchronization of coupled oscillators, and the ability of locally connected cellular automata to "solve" certain global computation problems.

Watts & Strogatz's observations, although new to the mathematical literature of coupled dynamical systems, and also to the condensed matter physics community, were not, in spirit at least, new to mathematical sociologists. Parameterized models of locally ordered but otherwise random networks, for example, had been the object of social network analysts' attention for decades, at first according to Rapoport's notion of random-biased nets (Rapoport 1951, 1957), and more recently according to what are generically referred to as exponential random graph models, developed by Holland & Leinhardt (1981), Frank & Strauss (1986), and others (Anderson et al. 1999, Pattison & Wasserman 1999, Robins et al. 1999, Wasserman & Pattison 1996). Furthermore, Granovetter (1973), following Rapoport, had introduced the distinction between "strong" and "weak" ties, where

the former could be construed as arising from local ordering principles like homophily (Lazarsfeld & Merton 1954) and triadic closure (Rapoport 1953a), and the latter from occasional random contacts, which Granovetter called local bridges, but which are clearly analogous to Watts & Strogatz's shortcuts. And finally, Rapoport (1953a,b) and others (Kretschmar & Morris 1996) had long been concerned with the effect of socio-structural biases in otherwise random networks on the spread of information or infectious disease.

However, a distinguishing feature of Watts & Strogatz (1998), and the one that arguably generated much of the subsequent interest in the physics community, was their identification of a universal class of networks; that is, a family of networks that share certain aggregate properties (in this case small L and large C) regardless of many of their individual details. This finding had two implications, both of which fit naturally into a physicist's worldview: (a) that at least some interesting features of even very complex networks could be captured by extremely simple models, and (b) that metrics and models devised to address social network problems might be usefully applied in other disciplines as well. Condensed matter physicists have subsequently analyzed what is now called the Watts-Strogatz model, or variants of it, in great detail (Barrat & Weigt 2000; Barthelemy & Amaral 1999; Dorogovtsev & Mendes 2000; Kulkarni et al. 2000; Newman & Watts 1999a,b; Newman et al. 2000). Specifically, it has been shown that whereas clustering C is a function of the fraction of random shortcuts p (Barrat & Weigt 2000), the average shortest path length L is a function of their absolute number Nkp (Newman et al. 2000). Although this difference may appear subtle, its implication is that in a sufficiently large network (i.e., as N is increased without bound) small-world behavior will result whenever the fraction of random shortcuts is greater than zero--that is, for any randomness at all. Furthermore, this result does not depend on the presence of a one-dimensional lattice--it is true for any connected substrate--hence the conditions required for small-world behavior to pertain are even weaker than at first thought. A particularly striking result in this regard is that for a slightly modified version of the ring lattice model (in which random shortcuts are added rather than rewired), Newman et al. (2000) showed that the addition of only five random shortcuts would halve the average path length L of the network, regardless of its size. (3)

The Algorithmic Small-World Problem

Unfortunately, the Watts-Strogatz model suffers from some serious problems that render it unsuitable as a model of social networks. One such problem was pointed out by Kleinberg (2000a,b), who observed that the small-world experiments of Milgram (Korte & Milgram 1970, Milgram 1967, Travers & Milgram 1969) demonstrated not only that short paths existed between randomly chosen individuals in a large population, but also that the individuals in question could locate these paths using only their local information about the network. Social networks, in other words, are not only small; they are also searchable. In a remarkable piece of analysis, Kleinberg proved that while models like that of Watts & Strogatz, in which links are rewired uniformly at random, exhibited short global path lengths, they could not exhibit searchability. He then proposed a class of generalized small-world networks comprising (a) an underlying d-dimensional lattice, and (b) random links superposed on the lattice, where the probability [P.sub.ij] of two nodes being connected randomly is

(1) [P.sub.ij] [varies] [r.sup.-[gamma].sub.ij],

and [r.sub.ij] is the lattice distance from i to j. When [gamma] = 0, random edges are formed with uniform probability (equivalent to the original Watts-Strogatz model), and when [gamma] is sufficiently large, only local ties are possible. Clearly in neither limit is the network searchable--in the former case because short paths cannot be found (Kleinberg's earlier result), and in the latter case because no short paths exist. In fact, Kleinberg proved that only when [gamma] = d, the dimension of the underlying lattice, would the network be searchable in the sense that the number of steps required to forward a message from a randomly chosen starter to a randomly chosen target is "short" (4) (Kleinberg 2000a). More generally, what Kleinberg showed is that network structure is important not only locally, i.e., because an individual's neighborhood provides him with information and resources, but also globally in that it enables him to navigate when searching for information or resources outside his neighborhood.

Affiliation Networks

Another problem with the Watts-Strogatz model, and also with Kleinberg's, is that both models rely on the presence of some underlying lattice substrate to (a) guarantee global connectivity and (b) provide a distance metric that is independent of the network distance. Clearly, social networks are not built on a lattice substrate, so the question arises whether one can account for clustering, short path lengths, and searchability in a less …