8
Bacon’s Links
Networks, society, and games

Unlike the physics of subatomic particles or the largescale structure of the universe, the science of networks is the science of the real world—the world of people, friendships, rumors, disease, fads, firms, and financial crises.

—Duncan Watts, Six Degrees

Modern science owes a lot to a guy named Bacon.

If you had said so four centuries ago, you would have meant Francis Bacon, the English philosopher who stressed the importance of the experimental method for investigating nature. Bacon’s influence was so substantial that modern science’s birth is sometimes referred to as the Baconian revolution.

Nowadays, though, when you mention Bacon and science in the same breath you’re probably talking not about Francis, but Kevin, the Hollywood actor. Some observers might even say that a second Baconian revolution is now in progress.

After all, everybody has heard by now that Kevin Bacon is the most connected actor in the movie business. He has been in so many films that you can link almost any two actors via the network of movies that he has appeared in. John Belushi and Demi Moore, for instance, are linked via Bacon through his roles in Animal House (with Belushi) and A Few Good Men (with Moore). Actors



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



Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature 8 Bacon’s Links Networks, society, and games Unlike the physics of subatomic particles or the largescale structure of the universe, the science of networks is the science of the real world—the world of people, friendships, rumors, disease, fads, firms, and financial crises. —Duncan Watts, Six Degrees Modern science owes a lot to a guy named Bacon. If you had said so four centuries ago, you would have meant Francis Bacon, the English philosopher who stressed the importance of the experimental method for investigating nature. Bacon’s influence was so substantial that modern science’s birth is sometimes referred to as the Baconian revolution. Nowadays, though, when you mention Bacon and science in the same breath you’re probably talking not about Francis, but Kevin, the Hollywood actor. Some observers might even say that a second Baconian revolution is now in progress. After all, everybody has heard by now that Kevin Bacon is the most connected actor in the movie business. He has been in so many films that you can link almost any two actors via the network of movies that he has appeared in. John Belushi and Demi Moore, for instance, are linked via Bacon through his roles in Animal House (with Belushi) and A Few Good Men (with Moore). Actors

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature who never appeared with Bacon can be linked indirectly: Penelope Cruz has no common films with Bacon, but she was in Vanilla Sky with Tom Cruise, who appeared with Bacon in A Few Good Men. By mid-2005, Bacon had appeared in films with nearly 2,000 other actors, and he could be linked in six steps or fewer to more than 99.9 percent of all the linked actors in a database dating back to 1892. Bacon’s notoriety in this regard has become legendary, even earning him a starring role in a TV commercial shown during the Super Bowl. Bacon’s fame inspired the renaissance of a branch of mathematics known as graph theory—in common parlance, the math of networks. Bacon’s role in the network of actors motivated mathematicians to discover new properties about all sorts of networks that could be described with the tools of statistical physics. In particular, modern Baconian science has turned the attention of statistical physicists to social networks, providing a new mode of attack on the problem of forecasting collective human behavior. In fact, the new network math has begun to resemble a blueprint for a science of human social interaction, a Code of Nature. So far, though, the statistical physics approach to quantifying social networks has mostly paid little attention to game theory. Many researchers believe, however, that there is—or will be—a connection. For game theory is not merely the math for analyzing individual behavior, as you’ll recall—it also proscribes the rules by which many complex networks form. What started out as a game about Kevin Bacon’s network may end up as a convergence of the science of networks and game theory. SIX DEGREES In the early 1990s, Kevin Bacon’s ubiquity in popular films caught the attention of some college students in Pennsylvania. They devised a party game in which players tried to find the shortest path of movies linking Bacon to some other actor. When a TV talk show publicized the game in 1994, some clever computer science students at the University of Virginia were watching. They soon

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature launched a research project that spawned a Web page providing instant calculations of how closely Bacon was linked to any other actor. (You should try it—go to oracleofbacon.org.) The 1,952 actors directly linked by a common film appearance with Bacon each have a “Bacon number” of 1. Another 169,274 can be linked to Bacon through one intermediary, giving them a Bacon number of 2. More than 470,000 actors have a Bacon number of 3. On average, Bacon can be linked to the 770,269 linkable actors in the movie database1 in about 2.95 steps. And out of those 770,269 in the database, 770,187 (almost 99.99 percent) are linked to Bacon in six steps or fewer—nearly all, in other words, are less than six degrees of separation from Bacon. So studies of the Kevin Bacon game seemed to verify an old sociological finding from the 1960s, when social psychologist Stanley Milgram conducted a famous mail experiment. Some people in Nebraska were instructed to send a parcel to someone they knew personally who in turn could forward it to another acquaintance with the eventual goal of reaching a Boston-area stockbroker. On average, it took a little more than five mailings to reach the stockbroker, suggesting the notion that any two people could be connected, via acquaintances, by less than “six degrees of separation.” That idea received considerable publicity in the early 1990s from a play (and later a movie) of that title by John Guare. From a scientific standpoint, the Bacon game and Guare’s play came along at a propitious time for the study of networks. The six-degrees notion generated an awareness that networks could be interesting things to study, just when the tools for studying networks fell into scientists’ laps, in the form of powerful computers that, it just so happened, were themselves linked into a network of planetary proportions—the Internet. NETWORKS ARE US When I was growing up, “network” meant NBC, ABC, or CBS. Later came PBS, CNN, and ESPN, among others, but the basic idea stayed the same. As the world’s cultural focus shifted from TV

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature to computers, though, the notion of network expanded far beyond its origins. Nowadays it seems that networks are everywhere, and everything is a network. Networks permeate government, the environment, and the economy. Society depends on energy networks, communication networks, and transportation networks. Businesses engage networks of buyers and sellers, producers and consumers, and even networks of insider traders. You can find networks of good ol’ boys—in politics, industry, and academia. Atlases depict networks of rivers and roads. Food chains have become food webs, just another word for networks. Bodies contain networks of organs, blood vessels, muscles, and nerves. Networks are us. Of all these networks, though, one stands out from the crowd—the Internet and the World Wide Web. (OK, that’s actually two networks; the Internet comprising the physical network of computers and routers, while the World Wide Web is technically the software part, consisting of information on “pages” connected by URL hyperlinks.) During the early 1990s, awareness of the Internet and Web spread rapidly through the population, bringing nearly everybody in contact with a real live example of a network in action. People in various walks of life began thinking about their world in network terms. True, the word “network” already had its informal uses, for such things as groups of friends or business associates. But during the closing years of the 20th century, the notion of network became more precise and came to be applied to all sorts of systems of interest in biology, technology, and society. Throughout the scientific world, networks inspired a new viewpoint for assessing some of society’s most perplexing problems. Understanding how networks grow and evolve, survive or fail, may help prevent e-mail crashes, improve cell phone coverage, and even provide clues to curing cancer. Discovering the laws governing networks could provide critical clues for how to protect— or attack—everything from power grids and ecosystems to Web sites and terrorist organizations. Physicists specializing in network math have infiltrated disciplines studying computer systems, inter-

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature national trade, protein chemistry, airline routes, and the spread of disease. Using math to study networks is not entirely new, though. In fact, network math goes back at least to the 18th century, when the Swiss mathematician Leonhard Euler gave intellectual birth to the field with his analysis of a network of bridges in Königsberg, in eastern Prussia. In the mid-20th century, Paul Erdös and Alfréd Rényi developed the math to describe networks in their most abstract representation—essentially dots on paper connected by lines. The dots are known as nodes (or sometimes vertices); the lines are officially called edges, but are more popularly referred to as links. Such drawings of dots and lines are technically known as graphs, so traditional network math is known as graph theory.2 A graph’s dots and edges can represent almost anything in real life. The nodes may be any of various objects or entities, such as people, or companies, or computers, or nations; the links may be wires connecting machines, friendships connecting people, common film appearances connecting movie actors, or any other common property or experience. People, of course, belong to many different kinds of networks, such as networks of family, networks of friends, networks of professional collaborators. There are networks of people who share common investments, political views, or sexual partners. Traditional graph theory math does not do a very good job of describing such networks, though. Its dots and lines resemble real networks about as much as a scorecard resembles a baseball field. The scorecard does record all the players and their positions, but you won’t get much of an idea of what baseball is like from reading the scorecard. Same with graphs. Standard graph math describes fixed networks with nodes connected at random, whereas in the real world, networks usually grow, adding new parts and new connections, while perhaps losing others—and not always at random. In a random network, every node is an equal among many, and few nodes get much more or less than a fair share of links. But in many real-world networks, some nodes possess an unusually high number of links. (In a network of sexual partners, for ex-

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature ample, some people have many more “links” than average—an important issue in understanding the spread of HIV.) And real networks form clusters, like cliques of close friends. Erdös and Rényi knew full well that their dots and lines did not capture the complexities of real-world networks. As mathematicians, they didn’t care about reality—they developed their model to help understand the mathematical properties of random connections. Describing random connections was a mathematically feasible thing to do; describing all the complexities of real-world networks was not. Nobody knew how to go about doing it. But then a paper appearing in the British journal Nature began to change all that. Looking back, the birth of network mania can be dated to June 4, 1998, when Duncan Watts and Steven Strogatz published a brief paper (taking up only two and a half Nature pages) called “Collective Dynamics of ‘Small-World’ Networks.”3 NETWORK MANIA A few years later, when I met Strogatz at a complexity conference, I asked him why networks had become one of math’s hottest topics in the late 1990s. “I think our paper started it,” he said. “If you ask me when did this really start, I think it started in 1998 when our paper appeared in Nature on what we called small-world networks.” So I quizzed Strogatz about that paper’s origins. It really was a case of culture preparing the conditions for the advance of science. “When Watts and I started our work in 1995 or so, we were very aware of the whole Kevin Bacon thing, and we had heard of six degrees of separation, and the movie had come out of that play,” said Strogatz. “So it was in the air.”4 Of course, Kevin Bacon didn’t revolutionize science totally on his own. The Bacon game became famous just about the time that the public became aware of the Internet, thanks to the arrival of the World Wide Web. “I think the Web got us thinking about networks,” Strogatz

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature said. Not only was the Web a high-profile example of a vast, elaborate network, it made many other networks accessible for research. Web crawlers and search engines made it possible to map out the links of the Web itself, of course, and the Web also made it possible to catalog other large networks and store them for easy access (the database of movie actors being one prime example). Data on the metabolic reactions in nematode worms or the gene interactions in fruit flies could similarly be collected and transmitted. “Big databases became available, and researchers could get their hands on them,” Strogatz observed. “People started to think about things as networks.” Before that, he said, even actual networks weren’t usually viewed in network terms—the electric power network was known as a grid, and you were just as likely to hear the term telephone “system” as telephone network. “We didn’t think of them so much as networks,” Strogatz said. “I don’t think we had the visceral sensation of moving through a network from link to link.” With the Web it was different. It was almost impossible to think of it as a whole. You had to browse, link by link. And the Web touched all realms of science, linking specialists of all sorts with network ideas. “In many different branches of science,” Strogatz observed, “the kind of thinking that we call network thinking started to take hold.” Still, the revolution in network math did not begin until after the Watts-Strogatz paper appeared in 1998. They showed how to make a model of a “small-world” network, in which it takes only a few steps on average to get from any one node of the network to any other. Their model produced some surprises that led to a flurry of media coverage and the subsequent network mania. But Strogatz thinks some of those surprises have been misrepresented as being responsible for network math’s revival. Some experts would say, for example, that the Watts-Strogatz paper’s major impact stemmed from identifying the small-world nature of some particular real-world networks. Others have suggested that “clustering” of links (small groups of nodes connected more than randomness would suggest) was the key discovery. “This is to me the bogus view of

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature what was important about our paper,” Strogatz said. “The reason it caught on, I think, is because we were the first to compare networks from different fields and find that there were similar properties across fields.” In other words, diverse as networks are, many share common features that can be described in a mathematically precise way. Such commonalities gave people hope that network math could be more than a tedious chore of sorting out links in one kind of network and then moving on to the next. Instead, it seemed, general laws of networks might be possible, enabling accurate forecasts of how different kinds of networks would grow, evolve, and behave—chemical networks like proteins in cells, neural networks like nerve cells in brains, or social networks, such as actors in movies or stock traders in the economy. SMALL WORLDS One of the key common features of different networks is that many of them do in fact exhibit the small-world property. When a network’s nodes are people, for instance, small worlds are the rule. So discovering the rules governing small-world networks may be the key to forecasting the social future. Watts and Strogatz uncovered the small-world nature of certain networks by focusing on networks intermediate between those that were totally regular or totally random. In a regular network (what is often called a regular lattice), the nodes are connected only to their nearby neighbors. For an ultra-simple example, think of a series of nodes arranged in a circle. The dots representing the nodes are connected to their immediate neighbors on either side by the line representing the circle. Regular network

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature For a more elaborate (but still regular) network, you could connect the dots to their second-nearest neighbors as well. Each node would then be connected to four others—two neighbors on each side. In a random network, on the other hand, some nodes would be connected to many others, some maybe connected to only one. Some nodes would be linked only to other nodes nearby; some would be connected to nodes on the other side of the circle; some would be connected both to neighbors and to distant nodes. It would look like a mess. That’s what it means to be random. In a random network, it is usually easy to find a relatively short path from one node to any other, thanks to the random long-range links making connections across the circle. Regular networks, though, are not so easy to navigate. To get from one side of the circle to the other, you have to take the long way around, via linked neighbors. Random network But what happens, Watts and Strogatz wondered, with an “in-between” network—neither completely regular nor completely random? In other words, suppose you started with a regular network and then added just a few links at random between other nodes. It turned out that if even just a tiny percentage of the links created shortcuts between distant nodes, the new intermediate network would be a small world (that is, you could get anywhere in the network in a small number of steps). But that intermediate network retains an important feature of the regular network—its nearby nodes are still more highly connected than average (that is, they are “clustered”), unlike random networks where clustering is mostly absent. The mathematical existence of graphs combining these properties of random and regular networks was nice, if not necessarily

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature Intermediate (small-world) network important. But the fact that you needed very few shortcuts to make the network world small implied that small-world networks might be common in nature. Watts and Strogatz tested that possibility on three real-world examples: the film actors’ network starring Kevin Bacon, the electrical power grid in the western United States, and the network of nerve cells in the tiny roundworm C. elegans.5 In all three cases, these networks exhibited the small-world property, just like the models of hypothetical networks that were intermediate between regular and random. “Thus,” Watts and Strogatz concluded, “the small-world phenomenon is not merely a curiosity of social networks nor an artifact of an idealized model—it is probably generic for many large, sparse networks found in nature.”6 If so (and it was), Watts and Strogatz had opened a new frontier for mathematicians and physicists to explore, where all sorts of important networks could be analyzed with a common set of tools. In just the way that statistical physics made it possible to tame the complexities of a jumble of gas molecules, mathematicians could use similar math to compute a network’s defining properties. And just as all gases, no matter what kinds of molecules they contained, obeyed the same gas laws, many networks observed similar mathematical regularities. “Everybody pointed out, isn’t this remarkable that these totally different networks have these properties in common—how would you have ever thought that?” Strogatz said. Several network features can be quantified by numbers analogous to the temperature and pressure of a gas, what scientists call the parameters describing a system. The average number of steps to get from any one node to any other—the “path length”—is one such parameter. Another is the “clustering coefficient”—how likely

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature two nodes are to be directly linked if they are both linked to a third. A relatively high clustering rate is one of the counterintuitive features of small-world networks. The short path length in small-world networks is similar to the situation in random networks. On the other hand, the high clustering coefficient is completely unlike that in random networks, but is more similar to that in regular networks. This clustering property (you could call it the measure of “cliquishness”) is especially of interest in social networks. Since my sister Sue, for instance, has a friend Debby and a friend Janet, it is more likely than average that Debby and Janet also know each other. (They do.) “There is a tendency to form triangles, and you wouldn’t see that in random networks,” Strogatz pointed out. Besides clustering coefficient and path length, another critical number is the average number of links connecting one node to another, known as the degree coefficient. (The “degree” of a node is the number of other nodes it is linked to.) As a node in the actor network, Kevin Bacon would be ranked very high in degree, being connected to so many others. Being well connected, after all, is what makes the average path length between Bacon and other actors so short. But in a shocking development, it turned out that Bacon is far from the most connected of actors. Taking the average number of steps to link to another actor as the gauge, he doesn’t even rank in the top 1,000! It turns out, in fact, that Bacon’s true importance for networks had nothing to do with how special he is, but rather how typical he is. Many actors, like Bacon, serve as “hubs” connecting lots of other members of the acting community. And the existence of such hubs turns out to be a critical common feature of many real-world networks. THE POWER OF SCALE FREEDOM As of mid-2004, the actor leading the list as “most connected” (based on the average number of steps to link him with all the other actors) was Rod Steiger, at 2.679 steps. Bacon, at 2.95,

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature ranked 1,049th. (Still, as Bacon is more connected than 99 percent of all actors, he does qualify as an important hub.) In second place was Christopher Lee (2.684), followed by Dennis Hopper (2.698). Donald Sutherland ranked 4th. Among women, the most connected was Karen Black, in 21st place. It’s such highly connected actors, or hubs, that make it easy to get from any actor to any other in just a few steps. Choose any two actors at random. You can probably connect them in three steps or less. And it would be unusual to need more than four. If you search and search, you can find a few who would require more steps, but that is likely only if you deliberately choose actors who would not be very connected, like someone who appeared in only one film. (And remember, I said you need to choose two at random.) So for example, just off the top of my head I’ll say Basil Rathbone (because I saw a Sherlock Holmes movie last night) and Lindsay Lohan (no reason—I will not admit to having seen Herbie: Fully Loaded). These two actors are from entirely different eras, and Lohan is young and has been in relatively few films. But you can link them in only three steps. An aging Rathbone appeared in Queen of Blood (1966) with the pre–Easy Rider Dennis Hopper. Hopper was in Knockaround Guys with Bruce McFee, who appeared in Confessions of a Teenage Drama Queen (2004) with Lohan. The short path between Rathbone and Lohan was made possible by the hub provided by Hopper, who is, in fact, much more connected then Bacon.7 (Hopper is connected directly to 3,503 other actors, about 1,500 more than Bacon.) Hubs like Hopper make the actor network a small world. They make getting from one node to another easy, in much the way that major airport hubs like Chicago’s O’Hare or Dallas–Fort Worth unite the smaller airports in airline networks so you can get from one town to another without too many plane changes. Such large hubs generally do not exist, though, in either random or regular networks. In a regular network, every node has the same number of links, so there are no hubs. In a random network, shortcuts exist, but they might be very hard to find because prominent hubs would be very rare. In random networks, any one node

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature (actor or airport) is as likely to be linked as much as any other, so most of them are linked to about the same degree. Only a few would have a lot more links than average, or a lot less. If actors were linked randomly, their rankings by number of links would form a bell curve, with most of them close to the middle. But in many small-world networks, there is no such “typical scale” of the number of links. Such distributions—with no typical common size—are known as “scale free.” In scale-free networks, many lonely nodes will have hardly any connections at all, some nodes will be moderately well connected, and a few will be superconnected hubs. To mathematicians and physicists, such a scale-free distribution is a sure sign of a “power law.” In a groundbreaking paper published in Science in 1999, Réka Albert and Albert-László Barabási of Notre Dame University noted the scale-free nature of many kinds of networks, and consequently the usefulness of power laws for describing them. The revelation that networks could be described by power laws struck a responsive chord among physicists. (They “salivate over power laws,” Strogatz says—apparently because power law discoveries in other realms of physics have won some Nobel Prizes.) Power laws describe systems that include a very few big things and lots of little things. Cities, for example. There are a handful of U.S. cities with populations in the millions, a larger number of medium-sized cities in the 100,000 to a million range, and many, many more small towns. Same with earthquakes. There are lots of little earthquakes, too weak to notice; a fewer number of middling ones that rattle the dishes; and a very few devastating shocks that crumble bridges and buildings. In their Science paper, Barabási and Albert showed how the probability that a node in a scale-free network is linked to a given number of other nodes diminishes as the number of links increases. That is to say, scale-free networks possess many weakly linked nodes, fewer with a moderate number of links, and a handful of monsters—like Google, Yahoo, and Amazon on the World Wide Web. Nodes with few links are common, like small earthquakes;

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature 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-

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature ematical 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

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature 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,”

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature 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

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature 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 typi-

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature cally 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.

OCR for page 144
A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature 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.