"Six Degrees of Kevin Bacon" Game Provides Clue to Efficiency of Complex Networks

Published 11/17/2008

Media Contacts:
Warren R. Froelich, SDSC Communications, 858 822-3622 or froelich@sdsc.edu
Jan Zverina, SDSC Communications, 858 534-5111 or jzverina@sdsc.edu

As the global population continues to grow exponentially, our social connections to one another remain relatively small, as if we're all protagonists in the Kevin Bacon game inspired by "Six Degrees of Separation," a Broadway play and Hollywood feature that were popular in the 1990s.

In fact, classic studies show that if we were to route a letter to an unknown person using only friends or acquaintances who we thought might know the intended recipient, it would take five or six intermediary acquaintances before the letter reaches its intended destination.

The underlying success of this phenomenon called the "small-world paradigm," discovered in the 1960s by sociologist Stanley Milgram, recently provided a source of inspiration for researchers studying the Internet as a global complex network.

The result, a study by Marián Boguñá, Dmitri Krioukov, and Kimberly Claffy, published in Nature Physics on November 16, reveals a previously unknown mathematical model called "hidden metric space" that may explain the "small-world phenomenon" and its relationship to both man-made and natural networks such as human language, as well as gene regulation or neural networks that connect neurons to organs and muscles within our bodies.

For these researchers, the concept of an underlying "hidden space" may also be relevant to their professional interests: how to remove mounting bottlenecks within the Internet that threaten the smooth passage of digital information around the globe.

"Internet experts are worried that the existing Internet routing architecture may not sustain even another decade," said Krioukov, the study's principal investigator with the Cooperative Association for Internet Data Analysis (CAIDA), based at the San Diego Supercomputer Center at the University of California, San Diego. "Routing in the existing Internet has already reached its scalability limits; black holes are appearing everywhere."

"Discovery of such a metric space hidden beneath the Internet could point toward architectural innovations that would remove this bottleneck," added Claffy, director of CAIDA and adjunct professor of computer science at UC San Diego. "Although quite prevalent in the natural world, the idea of routing using only local rather than global knowledge of network connectivity represents a revolutionary change in how to think about engineering communications networks. It's clear that the Internet's current architectural requirements are incompatible with the overwhelming amount of information that's being transmitted through this now critical global infrastructure."

According to the researchers, natural networks appear to transmit signals or messages with a high degree of efficiency, even though no single node - whether it's an individual person in a social network or a single neuron in a neural network - can visualize the global structure of the entire network.

How is this possible? By constructing a mathematical model of geometry underlying the topology of these networks, the researchers discovered that many complex networks shared a similar characteristic - their global topological structure (or shape) maximizes their communication efficiency.

"A vast majority of very different complex networks have similar shapes," said Krioukov. "They have similar shapes not just for fun, but perhaps because they all evolved toward structures and shapes that maximize efficiency according to their main common function, and that function is communication."

Take, for example, the "small-world phenomenon" described earlier. In this case, the only information people possessed to make their routing decisions was a set of descriptive attributes of the destined recipient - his or her home base and occupations. People then determined who among their contacts was "socially closest" to the target. For aficionados of the Kevin Bacon game, the goal was to connect any actor in Hollywood to Bacon through the films he made.

"The success of Milgram's experiment indicates that social distances among individuals - although they may be difficult to define mathematically - have a role in shaping the network, and may also be essential for efficient navigation," said Claffy.

Added Krioukov: "When you know the network topology, you merely know the basic layout of a network. But when you discover its underlying geometry, or hidden space, you may know how this complex network really functions."

Likewise, neural networks in the body would not function as well if they could not route specific signals to appropriate organs or muscles in the body, although no neuron has a full view of global inter-neuronal connectivity in the brain. The same can be said for the regulation of genes, which are turned on and off by regulator genes to manufacture proteins.

So, what accounts for this inherent communication efficiency of complex networks? The study suggests the existence of an underlying geometric framework that contains all the nodes of the network, shapes its topology and guides routing decisions: a "hidden metric space." Distances in this space are akin to social distances in the "small-world phenomenon." They measure similarity between people. The more similar the two persons, the closer they are in the "social space," and the more likely they are friends, connected in the acquaintance network. To route a message, a person forwards it to the friend socially closest to the message destination, as illustrated in Figure 1 (below).

The primary motivation for this study, according to Krioukov, was the constantly increasing size and dynamics of the Internet, leading to increasing incidences of routing bottlenecks. Discovery of the Internet's "hidden metric space" would allow messages to be forwarded to destinations based on local measurements of similarities between nodes, their positions in the "hidden space," rather than on their positions in the network, which requires global measurements of its structure.

Krioukov also suggests that reconstruction of hidden metric spaces underlying a variety of real complex networks may have other practical applications. For example, hidden spaces in social or communications networks could yield new, efficient strategies for searching for specific individuals or content. The metric spaces hidden under some biological networks also could lead to powerful tools for studying the structure of information or signal flows in these networks.

"This could be applied to cancer research, for example, whose studies rely heavily on gene regulation," he said. "Suppose you were able to find the hidden space here. One could then figure out what drives gene regulation networks and what drives them to failure. This would be an important contribution to the field."

The research was supported in part by DGES grant FIS2007-66485-C02-02, Generalitat de Catalunya grant No. SGR00889, the Ramón y Cajal program of the Spanish Ministry of Science, by NSF CNS-0434996 and CNS-0722070, by DHS N66001-08-C-2029 and by Cisco Systems.
About CAIDA

CAIDA is a collaborative undertaking among organizations in the commercial, government, and research sectors aimed at promoting greater cooperation in the engineering and maintenance of a robust, scalable global Internet infrastructure.

About SDSC
Since being founded in 1985 through a grant from the National Science Foundation as one of the original academic, national-level supercomputer centers, the San Diego Supercomputer Center at UC San Diego has earned a reputation as a top resource for data-intensive research and expertise, involved in a broad range of studies, ranging from the inner workings of the human body to the outer reaches of space. SDSC is the main data repository for TeraGrid, the nation's largest open scientific discovery infrastructure linking compute resources among 11 partner sites in the U.S.

Corresponding author: dima@caida.org

Related Links

CAIDA: www.caida.org/home/
San Diego Supercomputer Center (SDSC): www.sdsc.edu
UC San Diego: www.ucsd.edu
Universitat de Barcelona: www.ub.edu/homeub/en/
National Science Foundation: www.nsf.gov
Link to article in Nature Physics: www.nature.com/nphys/journal/vaop/ncurrent/full/nphys1130.html