Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:

 

“6 Degrees of Kevin Bacon” Provides Clue to Complex Networks

19.11.2008
Results could remove bottlenecks from the Internet and biological systems.

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.


Source: CAIDA, San Diego Supercomputer Center, UC San Diego

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 (visit http://ucsdnews.ucsd.edu/graphics/images/2008/11-08HiddenMetricSpace.jpg).

Figure 1: How the hidden metric space guides communication. If node A wants to reach node F, it checks the hidden distances between F and its two neighbors B and C. Distance CF (green dashed line) is smaller than BF (red dashed line), therefore A forwards information to C. Node C then performs similar calculations and selects its neighbor D as the next hop on the path to F. Node D is directly connected to F. The result is path ACDF shown by green edges in the observable topology.

Source: CAIDA, San Diego Supercomputer Center, UC San Diego.

“Such routing allows networks to efficiently find intended communication targets even though they do not have a global view of the system,” said Claffy.

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.

Warren R. Froelich | Newswise Science News
Further information:
http://www.sdsc.edu

More articles from Physics and Astronomy:

nachricht Further Improvement of Qubit Lifetime for Quantum Computers
09.12.2016 | Forschungszentrum Jülich

nachricht Electron highway inside crystal
09.12.2016 | Julius-Maximilians-Universität Würzburg

All articles from Physics and Astronomy >>>

The most recent press releases about innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Electron highway inside crystal

Physicists of the University of Würzburg have made an astonishing discovery in a specific type of topological insulators. The effect is due to the structure of the materials used. The researchers have now published their work in the journal Science.

Topological insulators are currently the hot topic in physics according to the newspaper Neue Zürcher Zeitung. Only a few weeks ago, their importance was...

Im Focus: Significantly more productivity in USP lasers

In recent years, lasers with ultrashort pulses (USP) down to the femtosecond range have become established on an industrial scale. They could advance some applications with the much-lauded “cold ablation” – if that meant they would then achieve more throughput. A new generation of process engineering that will address this issue in particular will be discussed at the “4th UKP Workshop – Ultrafast Laser Technology” in April 2017.

Even back in the 1990s, scientists were comparing materials processing with nanosecond, picosecond and femtosesecond pulses. The result was surprising:...

Im Focus: Shape matters when light meets atom

Mapping the interaction of a single atom with a single photon may inform design of quantum devices

Have you ever wondered how you see the world? Vision is about photons of light, which are packets of energy, interacting with the atoms or molecules in what...

Im Focus: Novel silicon etching technique crafts 3-D gradient refractive index micro-optics

A multi-institutional research collaboration has created a novel approach for fabricating three-dimensional micro-optics through the shape-defined formation of porous silicon (PSi), with broad impacts in integrated optoelectronics, imaging, and photovoltaics.

Working with colleagues at Stanford and The Dow Chemical Company, researchers at the University of Illinois at Urbana-Champaign fabricated 3-D birefringent...

Im Focus: Quantum Particles Form Droplets

In experiments with magnetic atoms conducted at extremely low temperatures, scientists have demonstrated a unique phase of matter: The atoms form a new type of quantum liquid or quantum droplet state. These so called quantum droplets may preserve their form in absence of external confinement because of quantum effects. The joint team of experimental physicists from Innsbruck and theoretical physicists from Hannover report on their findings in the journal Physical Review X.

“Our Quantum droplets are in the gas phase but they still drop like a rock,” explains experimental physicist Francesca Ferlaino when talking about the...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

Event News

ICTM Conference 2017: Production technology for turbomachine manufacturing of the future

16.11.2016 | Event News

Innovation Day Laser Technology – Laser Additive Manufacturing

01.11.2016 | Event News

#IC2S2: When Social Science meets Computer Science - GESIS will host the IC2S2 conference 2017

14.10.2016 | Event News

 
Latest News

Researchers identify potentially druggable mutant p53 proteins that promote cancer growth

09.12.2016 | Life Sciences

Scientists produce a new roadmap for guiding development & conservation in the Amazon

09.12.2016 | Ecology, The Environment and Conservation

Satellites, airport visibility readings shed light on troops' exposure to air pollution

09.12.2016 | Health and Medicine

VideoLinks
B2B-VideoLinks
More VideoLinks >>>