Albert-Laszlo Barabasi, Linked: The New Science of Networks (Perseus, 2002)
Comprehensive and thought-provoking, Barabasi provides a rich yet readable source for the non-mathematician seeking to understand and apply the emerging science of self-organizing, scale-free networks. A Professor of Physics and director of the Study of Self-Organized Networks at Notre Dame, Barabasi reviews and brings together 250 years of research that has deep significance for fields as diverse as quantum physics, molecular biology, digital security, global economics and counter-terrorism. Understanding the science may be a critical skill for those involved with the law and regulation of any complex system.
His history of the science starts in 18th century Russia and leads to Random Graph Theory in the 1950's and the studies of "small world" and clustering effects in the sixties and seventies. The Internet and the Web provided an ideal test bed for the study of "hubs" and "power law" effects in what are now called "scale-free" networks. He examines the "fit-get-rich" effect and the conditions in which a network may lead to a "winner-take-all" outcome. He then warns of the Achilles Heel of scale-free networks: the innate characteristics that make them robust and resistant to random failure makes them vulnerable to targeted attacks and subject to "cascading failure," such as in electrical blackouts. He shows the scale-free networks in biological processes and how the science contributes to the fight against AIDS and cancer, and touches on the potential studies in economic networks. He closes with cautions about the scale-free nature of terrorist networks such as Al-Queda.
Read more below ...
Random Graph Theory. Barbarasi begins with a history of Random Graph Theory, beginning with Leonhard Euler in 18th century Russia, and continuing with the research of Paul Erdos and Alfred Renyi in the 20th century. Erdos and Renyi documented clustering effects that are observed and described by various names in various disciplines: the emergence of a giant component (math); percolation and phase transition (physics); the formation of a community (sociology).
Six Degrees of Separation and Small Worlds. In the 1960's and 1970's, experiments by scholars including Stanley Milgram, Mark Granoveter, Duncan J. Watts, Steven Strogatz and Barabasi demonstrated a that a variety of clustering and "small world" effects could be found and quantified in all highly connected real networks, effects not explainable by Random Graph Theory. Those effects have been found in social networks, neural paths, the World Wide Web, the physical connections of the Internet, ownership of companies, food webs and cell biology. These studies demonstrated that huge networks do not need lots of random links; just a few long-range links between clusters enable small world features.
Hubs and Connectors. Malcolm Gladwell, in "The Tipping Point," addressed the pivotal role of "connectors" in the sudden and dramatic spread of viruses, the success of fashion breakthroughs and other events characterized by a sudden transition to explosive spread. Throughout the world of scale-free networks, those connectors are found as hubs. Recent studies of the architecture of the World Wide Web showed it to be dominated by a few very highly connected nodes, hub Websites with many links that hold together large clusters and many unpopular and seldom-noticed nodes. Even though hubs cannot be explained by the models used by Erdos/Renyi and Watts/Strogatz, they turn out to be ubiquitous in most complex networks that scientists have studied so far.
The 80/20 Rule. The economist Vilfredo Pareto observed the principle commonly known as the "80/20 Rule," described mathematically by a "power law" distribution in a chart or histogram of values. Unlike the familiar "bell curve" characteristic of charts of random events, the power law distribution has no peak but is a curve in which a few large events coexist with many small events. The number of links in a small fraction of the nodes is "off the scale" of the large majority of nodes; such networks are called "scale-free". In 1999, Barabasi's team found that these power law curves are consistently found in numerous large networks.
Barabasi: "power laws are at the heart of some of the most stunning conceptual advances in the second half of the twentieth century, emerging in fields like chaos, fractals and phase transitions. Spotting them in networks signaled unsuspcted links to other natural phenomenon, and placed networks at the forefront of our understanding of complex systems in general." Barabasi, op cit pp. 72-73. Power laws are found at the molecular level, where the physical world is marked by "phase transitions" from states of disorder to order, such as when water freezes. Barabasi: "Nature normally hates power laws. In ordinary systems all quantities follow bell curves, and correlations decay rapidly, obeying exponential laws. But all that changes if the system is forced to undergo a phase transition. Then power laws emerge -- nature's unmistakable sign that chaos is departing in favor of order." Id. p. 77.
The Rich Get Richer. Studies of the evolution of system structures showed that hubs result from the combination of system growth and "preferential attachment" to existing nodes in a "scale-free model" described in 1999. Improvements in the model sought to include other phenomenon such as the appearance of internal links between established nodes, node disappearance and the rewiring of links due to aging or retirement of nodes.
Einstein's Legacy. The explosive success of "new kid on the block" Google could not be explained by the scale-free model until a measure of a node's ability to stay in front of the competition produced a "fitness model." Examining the fitness model data, Ginestra Bianconi was startled to find that the calculations used were very similar to those found in the formation of a Bose-Einstein condensate. The math describing the behavior of "Bose gases" (a unique creature of sub-atomic quantum mechanics) turned out to be identical to those in the network fitness model. This similarity means, according to Barabasi, that in certain circumstances, particularly fit nodes in a network did not merely get richer ... the winner could take all.
In an ordinary "fit-get-rich" network, the fittest node gets biggest, but other fit nodes are close behind, so that "the power laws and the fight for links are not antagonistic but can coexist peacefully." Id. 102. In a "winner-takes-all" system, the fittest node grabs all the links, shaping the network into a "star" or "hub and spoke" topology which is not scale free ... there is a single hub and many tiny nodes. These findings have obvious relevancy to those studying antitrust law and policy and the ongoing case of Microsoft.
Achilles Heel. Natural systems exhibit robustness, the ability to survive under a wide range of conditions, because of their interconnectivity and scale-free topology. Experiments on a model of the Internet showed that one could remove the majority, even 80%, of the nodes and the rest would hold together as long as the small minority of hubs survived. Even though they are robust in the face of failure due to random events or errors, scale-free networks have an Achilles heel: they are vulnerable to simultaneous targeted attacks on the largest hubs.
Following the 1996 Western power blackout, Duncan Watts published a study of fads and "cascading failures" in systems such as electrical power grids. Cascading failures are not unique to electrical networks. They have been observed in many complex systems, including the economy (the East Asian monetary crisis of 1997), in ecological systems, in cellular biological systems, and following the September 11 terror attacks. Watts' investigations resulted in a model he used to study such phenomenon, and found that such cascades do not occur instantaneously; failures may go unnoticed for a long time before starting a landslide. Such phenomena invite study from many disciplines.
Viruses and Fads. The spread of viruses and fads are examples of what is called diffusion in a complex network, with a calculable "spreading rate." They will die out unless that rate exceeds a critical "epidemic threshold." Random Graph Theory could not explain the persistence of certain computer viruses or the explosive spread of AIDS. When a scale-free model including highly linked hubs was used, researchers found that the epidemic threshold vanished. Thus, network science can explain the sudden explosion of the AIDS epidemic, a relatively hard-to-catch disease, due to one "hub" ... an infected and extremely promiscuous flight attendant known as "Patient Zero."
The Awakening Internet. The Internet (on which the World Wide Web runs) has grown more like an evolving ecosystem than a manufactured machine. In 1999, three Greek computer scientist brothers, found that the connectivity distribution of Internet routers followed a power law, demonstrating it to be a scale-free network, subject to the same vulnerabilities and robustness found in other such networks.
The Fragmented Web. Unlike the Internet infrastructure, the Web is a "directed" network; its many links each point only one way, shaping its topology into the form of a "bow tie" with four "continents," one being an archipelago of disconnected islands. It turns out that these same four continents are found in all "directed" networks and are predictable analytically. This topology, and its consequences for the navigability of the Web become relevant in legal and regulatory actions, such as the French court's order in 2000 that Yahoo must block French residents from navigating to neo-Nazi websites. Despite Lessig's assertions that code can enforce such legal directives, Barabasi maintains that the topology and navigability of the Web is a function of collective human actions using the code. The architecture of a scale-free, directed network represents a higher level of organization than the underlying code. As long as individuals decide to what nodes to link, the inherent topology (and navigability) survives, says Barabasi.
The Map of Life. The genome has been sequenced, but the behavior of a living system is more than its molecular components. Within each cell there is a metabolic network, a web of biochemical reactions that researchers are now mapping, revealing scale-free network topologies exhibiting "small world" properties. Understanding cellular networks advances the cause of understanding and stopping cancer, Parkinsons, AIDS and other diseases. Barabasi sees this as the most promising near-term payoff from network research.
Network Economy. The traditional tree-shaped corporate structure, suited to mass production, is poorly suited to deal with rapid innovation and market change. The challenge of competing in such environments led to industries like pharmaceuticals and technology developing scale-free networks of alliances and outsourcers. For years, economists spoke of a standard formal model of economics, in which companies interact not with each other but with "the market," a theoretical entity mediating economic transactions. Barabasi: "In reality, the market is nothing but a directed network. The weight of the links captures the value of the transaction, and the direction points from the provider to the receiver. The structure and evolution of this weighted and directed network determine the outcome of all macro economic processes." Id. pp. 208-209.
Barabasi quotes Walter W. Powell's book "Neither Market Nor Hierarchy: Network Forms of Organization:" "in markets the standard strategy is to drive the hardest possible bargain in the immediate exchange. In networks, the preferred option is often creating indebtedness and reliance over the long haul." Id. p. 209. As a scale-free network, the economy is subject to the same vulnerabilities as are power grids and the Internet. Failures can cascade through the whole economy, as did the 1997 financial crisis that began in Thailand and cascaded across the Pacific, resulting in the stock market crash of October 27, 1997. Barabasi asserts that this is a natural consequence of network interconnectedness and interdependency and invites economic and network research in this field. Footnotes point to many such studies, and to the network economics websites of Leigh Tesfatsion and Nicholas Economides.
Web Without a Spider. Chance and randomness still play a role in the development of scale-free networks. But it is a web without a spider in the center; there is no single controller or node whose removal will break the web. The tragedy of September 11, 2001 is a dramatic example. Al Queda did not spring to life suddenly; it evolved over a period of years "into a self-organized spiderless web in which a hierarchy of hubs kept the organization together." Id. p. 222. Valdis Krebs has mapped the interconnections of the 19 highjackers and the 15 individuals connected to them based on publicly disclosed contacts. The resulting topology shows the characteristics of a self-organized, scale-free network. The developing science of such networks may provide us the clues to controlling it.
Barabasi: "Network thinking is poised to invade all domains of human activity and most fields of human inquiry. It is more than another useful perspective or tool. Networks are by their very nature the fabric of most complex systems, and nodes and links deeply infuse all strategies aimed at approaching our interlocked universe." Id. p. 222.
Albert-Laszlo Barabasi, Linked: The New Science of Networks (Perseus, 2002)
DougSimpson.com/blog