nodes with huge numbers of links are relatively rare, like huge earthquakes. And the rate at which the probability of links goes down is quantified by a power law, just like the math describing the distribution of city or earthquake sizes. In other words, a good theory of networks should explain not only how Kevin Bacon (or Dennis Hopper) can be so connected, but also why networks are analogous to earthquakes.

Barabási and Albert proposed an explanation based on the recognition that networks are rarely static arrangements of nodes with fixed numbers of links, but rather are usually growing and evolving structures. As networks grow by adding new nodes, Barabási and Albert hypothesized, new links do not form at random. Rather each new node prefers to link to nodes that already have a lot of links. In other words, the rich get richer, and the result of such a growth process is a scale-free network with very rich hubs. The dynamics of the process indicated that “the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems,” Barabási and Albert noted.8

While their “preferential attachment” scheme did indeed predict the formation of hubs, it did not explain many other aspects of real-world networks, including clustering. And it turned out that not all small-world networks are scale-free. Barabási and Albert’s original work, for instance, suggested that the networks explored by Watts and Strogatz were scale-free as well as being small worlds. But they aren’t. The power grid is a small world but isn’t scale-free, and neither is the neural network of C. elegans, Strogatz said. Still, there are many examples of networks that are both small-world and scale-free, with the World Wide Web being one spectacular example. And social networks are typically both small-world and scale-free, so understanding networks in terms of power laws would seem a good strategy for using networks to study human interactions.

Following Barabási and Albert’s pioneering efforts to quantify network evolution, many other groups have joined the hunt to identify all the important qualities of networks and devise math-

The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement