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 mathematical models to explain them. Among the organizations tuned into this issue is Microsoft, which obviously has a great interest in the Internet and World Wide Web. So their top scientists are busy investigating network math themselves. Leaders of this pack are a husband-wife team, mathematician Jennifer Tour Chayes and her husband/collaborator Christian Borgs. When I visited the Microsoft research labs outside Seattle, they outlined to me their efforts to identify the features that network math needs in order to capture the essence of the Web's structure.
"The Internet and the World Wide Web are grown, they're not engineered," Chayes pointed out. "No one really planned the Internet, and certainly no one planned the structure of the World Wide Web." Consequently the Web embodies many of the nuances of natural networks that a good mathematical model will need to capture, such as the small-world property (the ability to get from one page to any other in a relatively few number of steps) and the clustering phenomenon (if a Web page links to 10 others, there's a good chance that many of those 10 will link to one another as well). A further important feature is the preferential attachment identified by Barabási that conditions how a network grows, or ages. As the Web grows, and pages are added to the network, the older pages do tend to acquire more links than newcomers. But it's not always true that the oldest pages are the most connected. "It's not just a function of aging," Chayes explained. AltaVista, for example, once was the Cadillac of Web search engines. But the younger Google now has many more links. So different sites must earn links not only by virtue of age, but also beauty—or "fitness."
"AltaVista has been around longer but more people tend to link to Google—it's in some sense a better page," said Chayes. "All other things equal, the older sites will on average have more links, but if one site is more fit than another, that compensates for age…. If I'm twice as fit and I'm half as old, I should tend to have about the same number of connections."9
Another important feature of the Web, shared by many (but not all) networks, is that the links are "directed." Unlike the Internet, where wires run both ways, Web page hyperlinks go in only one direction. "Just because I link to CNN, that doesn't mean that CNN links to me," Chayes said. (Although, of course, it should.)
Naturally, good network math also needs to show that the Web is scale-free. A few sites have a huge number of links, more have a medium number, and most have very few links at all. Chayes and Borgs emphasized that equations describing the Web should predict not only such a distribution of links, but also the presence of a "strongly connected component" of Web pages. In the strongly connected component, or SCC, you can move from any page to another by following hyperlinks one page at a time. If her page is in the SCC, says Chayes, she can find a path to any other SCC page. "I can follow a series of hyperlinks and get to that person's page, and that person can follow a series of hyperlinks and get back to my page."
Borgs pointed out that some Web pages can link into the SCC even though no path links back to them. Some pages get linked to from a page in the SCC but don't link back to an SCC page. Knowing which pages are within the SCC, or connected to it in which way, would be important information for Web advertisers, he noted.
Building mathematical models that reproduce all these features of the Web is still a work in progress. But the models of the Web and other networks devised so far suggest that mathematicians of the future may someday be able to explain the behavior of many networks encountered in human affairs—such as economic, political and social networks; ecosystems; protein networks inside cells; and networks of contact that spread diseases. "I think there is going to be a mathematics of networks," said Chayes. "This is a very exciting new science."
BACK TO THE GAMES
Since game theory also claims dominion over describing human behavior, I asked Chayes whether it had any role to play in the new math of social networks. Fortunately, she said yes. "We are trying to explain why these network structures have evolved the way they have evolved, and that's really a game theory problem," Chayes said. "So there's a lot of work on game theory models for the growth of the Internet and the World Wide Web."
In fact, Chayes, Borgs, and collaborators have shown how math that is similar at least in spirit to a game theory approach can explain the emergence of preferential attachment in an evolving network (rather than merely assuming it, as Barabási and Albert did). It's a matter of minimizing the costs of competing considerations—the cost of making a connection, and the cost of operating it once it has been made. (It's kind of like buying a car—you can get a cheap one that will cost you more to keep running, or shell out more up front for high performance with low maintenance.) That trade-off can be viewed as a competition between different network structures, and the math that forecasts minimum cost also predicts that something like preferential attachment will describe the network's evolution.
More explicit uses of game theory have been called on to explain the evolution of other kinds of networks. A popular use of network models, for instance, is in making sense of the mess of chemicals interacting inside living cells. The interplay of thousands of proteins ends up determining how cells behave, which is often a matter of life and death. Game theory can help explain how those biochemical networks evolved into their current complex form.
Biologists would, of course, naturally assume that cellular metabolism should evolve to reach some "optimal" condition for fueling cell activity most efficiently. But what's most efficient? That depends on the environment, and the environment includes other species evolving toward optimality. "Thus, by evolving towards optimal properties, organisms change their environment, which in turn alters the optimum," note computational biologist Thomas Pfeiffer and biophysicist Stefan Schuster.10 And that is just the sort of dynamic for which game theory—particularly evolutionary game theory—is optimal. For example, a key molecule in the network of cellular chemistry is ATP, which provides the energy needed to drive important metabolic processes. ATP is the product of a chain of chemical reactions. To stay alive, a cell needs a constant source of ATP, so the reaction "assembly" line has to operate 24/7.
There are, of course, different possible arrangements of the assembly line—that is, different combinations of reactions that could produce ATP (as with many networks, there being multiple pathways to get to a hub). An important question in cellular biology is whether cells should prefer to produce
ATP as rapidly as possible, or as efficiently as possible (that is, with pathways that produce greater quantities of ATP from the same amount of raw material, getting more ATP bang for the buck). Some reaction pathways are faster but more wasteful than others, posing a trade-off for cells desiring to achieve an optimum metabolism.
The best strategy, a game-theoretic analysis shows, depends on the various other organisms in the vicinity competing for resources. Where competition is present, game theory recommends fast but wasteful ATP production, a prediction that contradicts straightforward notions of optimizing resource allocation. After all, if a population of microbial cells are competing for food, it would seem best for the group for each microbe to make the most efficient use of the available food supply, so there will be enough to go around. But game theory says otherwise—it's another example of the Prisoner's Dilemma in action. What's best for the individuals doesn't compute to be the overall best deal for the group.
"This paradoxically implies that the tendency of the users to maximize their fitness actually results in a decrease in their fitness—a result that cannot be obtained from traditional optimization," Pfeiffer and Schuster point out. "In the framework of evolutionary game theory, slow and efficient ATP production can be seen as altruistic cooperative behavior, whereas fast and inefficient ATP production can be seen as selfish behavior."11
But it's also a mistake to assume that cells will always act selfishly to enhance their survival odds. Game theory math suggests that in scenarios where a microbe's neighbors eat a different kind of food (so there is no competition for a single resource), more efficient production of ATP at the expense of speed would be a better survival strategy. Actual observations confirm that cells typically consuming resources shared by others (such as certain yeast cells) have evolved metabolisms that use the fast-but-wasteful approach to producing ATP. In multicellular organisms, though, cells behave more cooperatively with their neighbors, evolving reaction pathways that produce ATP more efficiently.
Intriguingly, cancer cells seem to violate the cooperation strategy and behave more selfishly (in terms of using inefficient ATP-producing processes). Game theory hasn't exactly cured cancer yet, but insights into such properties of cancer cells may contribute to progress in fighting it.
On a higher evolutionary level, a combination of network math and game theory may be able to explain more advanced forms of human cooperative behavior. Evolutionary game theory's assault on the cooperation problem—how altruistic behavior can evolve in societies of seemingly selfish individuals—has relied mainly on playing the Prisoner's Dilemma game under a variety of circumstances. In some versions of the game, the players (or agents) may encounter anybody else in the population and then decide whether to defect or cooperate. In one version, though, the agents face such decisions only in interactions with their immediate neighbors (the game, in other words, is "spatially structured"). It appears that cooperation is more likely to evolve in games with spatial constraints, at least when the game is the Prisoner's Dilemma.
But perhaps the Prisoner's Dilemma does not always capture the essence of real life very accurately. Life might sometimes more closely resemble a different kind of game. One candidate is the "snowdrift" game, in which the best strategic choice differs from the classic Prisoner's Dilemma. In a Prisoner's Dilemma, each player earns the highest payoff by defecting, regardless of what the other player does. In the snowdrift game, your best move is to defect only if your opponent cooperates. If the opponent defects, you are better off cooperating.12 As it turns out, spatial constraints also influence the evolution of cooperation in the snowdrift game, but in a different way—inhibiting cooperation rather than enhancing it. That is a perplexing finding, calling into question game theory's validity for studying the cooperation issue.
However, as physicists Francisco Santos and Jorge Pacheco have pointed out, the "spatial constraint" of agents interacting only with their neighbors is not realistic, either. A more realistic spatial description of the agents, or players, is likely to be a scale-free network of the agent's relationships, simulating actual social connections. Merging the math of scale-free networks with game theory, the physicists found that cooperation ought to emerge with either the Prisoner's Dilemma or snowdrift games. "Contrary to previous results, cooperation becomes the dominating trait on both the Prisoner's Dilemma and the snowdrift game, for all values of the relevant parameters of both games, whenever the network of connections correspond to scale-free graphs generated via the mechanisms of growth and preferential attachment," the physicists reported in 2005 in Physical Review Letters.13
Numerous other papers have explored links between game theory and network math. It strikes me as a sensible trend that is bound to bear ever more mathematical fruit. Networks are, after all, complex systems that have grown and evolved over time. And game theory, as evolutionary biologists have discovered, is a powerful tool for describing the evolution of such complexity. (One paper specifically models a version of the Prisoner's Dilemma game showing how repeated play can lead to a complex network in a state that the authors refer to as a "network Nash equilibrium.")14 Game theory's importance to society thus cannot help but expand dramatically as the critical nature of social networks becomes ever more clear.
In fact, physicists building their version of a Code of Nature with the tools of statistical mechanics (as did Asimov's Hari Seldon) have turned increasingly to using those tools on a network-based foundation. This alliance of statistical physics and network math, coupled with game theory's intimate links to networks, argues that game theory and statistical physics may together nourish the new science of collective human behavior that physicists have already begun to call sociophysics.
* * *
9
Asimov's Vision Psychohistory, or sociophysics?
"Humans are not numbers." Wrong; we just do not want to be treated like numbers.
—Dietrich Stauffer
In 1951—the same year that John Nash published his famous paper on equilibrium in game theory—Isaac Asimov published the novel Foundation. It was the first in a series of three books (initially) telling the story of a decaying galactic empire and a new science of social behavior called psychohistory. Asimov's books eventually became the most famous science fiction trilogy to appear between Lord of the Rings and Star Wars. His psychohistory became the model for the modern search for a Code of Nature, a science enabling a quantitative description and accurate predictions of collective human behavior.1
Mixing psychology with math, psychohistory hijacked the methods of physics to forecast—and influence—the future course of social and political events. Today, dozens of physicists and mathematicians around the world are following Asimov's lead, seeking the equations that capture telling patterns in social behavior, trying to show that the madness of crowds has a method.
As a result, Asimov's vision is no longer wholly fiction. His psychohistory exists in a loose confederation of research enterprises that go by different names and treat different aspects of the issue. At various schools and institutes around the world, collaborators from diverse departments are creating new hybrid disciplines, with names like econophysics, socionomics, evolutionary economics, social cognitive neuroscience, and experimental economic anthropology. At the Santa Fe Institute, a new behavioral sciences program focuses on economic behavior and cultural evolution. The National Science Foundation has identified "human and social dynamics" as a special funding initiative.
Almost daily, research papers in this genre appear in scientific journals or on the Internet. Some examine voting patterns in diverse populations, how crowds behave when fleeing in panic, or why societies rise and fall. Others describe ways to forecast trends in the stock market or the likely effect of antiterrorist actions. Still others analyze how rumors, fads, or new technologies spread.
Diverse as they are, all these enterprises share a common goal of better understanding the present in order to foresee the future, and possibly help shape
it. Put them all together, and Asimov's idea for a predictive science of human history no longer seems unthinkable. It may be inevitable.
Among the newest of these enterprises—and closest to the spirit of Asimov's psychohistory—is a field called sociophysics. The name has been around for decades, but only in the 21st century has it become more science than slogan. Like Asimov's psychohistory, sociophysics is rooted in statistical mechanics, the math used by physicists to describe systems too complex to expose the intimate interactions of their smallest pieces. Just as physicists use statistical mechanics to show how the temperature of two chemicals influences how they react, sociophysicists believe they can use statistical mechanics to take the temperature of society, thereby quantifying and predicting social behavior.
Taking society's temperature isn't quite as straightforward as it is with, say, gas molecules in a room. People usually don't behave the same way as molecules bouncing off the walls, except during some major sporting events. To use statistical physics to take society's temperature, physicists first have to figure out where to stick the thermometer.
Fortunately, the collisions of molecules have their counterpart in human interaction. While molecules collide, people connect, in various sorts of social networks. So while the basic idea behind sociophysics has been around for a while, it really didn't take off until the new understanding of networks started grabbing headlines.
Social networks have now provided physicists with the perfect playground for trying out their statistical math. Much of this work has paid little heed to game theory, but papers have begun to appear exploring the way that variants on Nash's math become important in social network contexts. After all, von Neumann and Morgenstern themselves pointed out that statistical physics provided a model giving hope that game theory could describe large social groups. Nash saw his concept of game theory equilibrium in the same terms as equilibrium in chemical reactions, which is also described by statistical mechanics. And game theory provides the proper mathematical framework for describing how competitive interactions produce complex networks to begin with. So if the offspring of the marriage between statistical physics and networks is something like Asimov's psychohistory, game theory could be the midwife.
A Beautiful Math Page 18