American Scientist

Linked: The New Science of Networks. Albert-László Barabási. viii + 280 pp. Perseus Publishing, 2002. $26.

Take a group of people, say the guests at a party, and for each of them draw a dot on a sheet of paper. Now add lines between the dots such that two dots are joined by a line if the two people know each other. The resulting structure is called a network or graph: a set of nodes (dots) connected by links (lines). A graph is a mathematically compact notation of "connectedness." Your party network allows you to easily identify socialites (nodes with many links), strangers (isolated nodes) and cliques (subsets of fully connected nodes). Graph theory, a classical branch of mathematics, tells you more—for example, how fast rumors will spread at your party, or that at any party with six or more guests you will inevitably find either at least three people who know one another or at least three who are strangers.

Almost every complex system can be described in terms of a graph. Sometimes the links correspond to tangible objects—for example, the highway system, power lines or the telephone network. More often, links represent interactions, like the link between two proteins that take part in a chemical reaction within a cell. A graph of social interactions emerges if you draw a link between two scientists who coauthored a paper, two actors who played in the same movie or two people who had sex with each other. The world around us (and within us) is full of networks, and according to Albert-László Barabási, they are the key fabric of complex systems. In Linked he tells the story of how graph theory developed from Leonhard Euler's solution of the puzzle of the Königsberg bridges in 1736 to an all-encompassing science of complexity for the 21st century.

For the two centuries that followed Euler's invention of it, graph theory focused on ordered graphs that have little in common with the irregular networks found in the real world. This changed in 1959, when Paul Erdos and Alfred Rényi introduced graphs whose links are placed completely randomly. These random graphs dominated the science of networks for almost 40 years. Then people learned that pure randomness is not enough to capture the complexity of real-world networks. Computerized studies of large networks, such as the World Wide Web, have uncovered a peculiar feature that distinguishes real-world networks from random graphs: In many real networks you find nodes that have exceptionally many links. These nodes are called hubs. The guy down the street who apparently knows everyone is a hub in the social network; Google is a hub in the Web. In random graphs there is a scale—a typical number of links per node—and there are only a few nodes that have twice as many links as the typical node and practically no nodes with 10 times as many. Real networks, on the other hand, are scale-free, allowing the existence of hubs.

Most complex networks of scientific and practical importance are scale-free: the Web, the metabolic network within a cell, citation networks—you name it. The ubiquity of the scale-free topology calls for a general underlying mechanism. One possible mechanism is a "rich get richer" scenario: As the network grows node by node, each new node links to some of the existing nodes, and the probability of getting one of the new links is proportional to the number of links already present. In some networks, such as the network of Hollywood actors, this preferential attachment is indeed very plausible: Every aspiring actor wants to play in a movie with a star. In other networks, such as the metabolic network within a cell, this is not quite as obvious.

The scale-free topology accounts for many observed properties of complex networks. Everyone has heard about "the six degrees of separation": We live in a small world, being at most six handshakes away from anybody else on the planet. But it is not just our world that is small—all scale-free networks share this property, thanks to their hubs. With links to an unusually large number of nodes, hubs create short paths between any two nodes in the system. Hubs are also the Achilles' heel of networks. A coordinated attack on a few of the major hubs can cut a network into many disconnected pieces. Random failure of even a large number of nodes, on the other hand, does not affect the overall connectivity, since most of the nodes are not hubs. This is why the Internet works fine, even though at any given time many of its nodes are not operating properly. Sometimes, however, the failure of a node triggers failure of a connected node. Eventually the spread of disaster reaches a hub and affects major parts of the network. The August 1996 blackout in the western United States was an example of such a cascading failure.

"This book has a simple aim: to get you to think networks," Barabási declares in his introduction. Following his links through the wonderful world of graphs and networks and all their applications to the real world, you may indeed end up with a fresh and inspiring view of complex systems.—Stephan Mertens, Theoretical Physics, Otto-von-Guericke University, Magdeburg, Germany