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 DGIST develops 20 times faster biosensor
24.04.2017 | DGIST (Daegu Gyeongbuk Institute of Science and Technology)

nachricht New quantum liquid crystals may play role in future of computers
21.04.2017 | California Institute of Technology

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: Making lightweight construction suitable for series production

More and more automobile companies are focusing on body parts made of carbon fiber reinforced plastics (CFRP). However, manufacturing and repair costs must be further reduced in order to make CFRP more economical in use. Together with the Volkswagen AG and five other partners in the project HolQueSt 3D, the Laser Zentrum Hannover e.V. (LZH) has developed laser processes for the automatic trimming, drilling and repair of three-dimensional components.

Automated manufacturing processes are the basis for ultimately establishing the series production of CFRP components. In the project HolQueSt 3D, the LZH has...

Im Focus: Wonder material? Novel nanotube structure strengthens thin films for flexible electronics

Reflecting the structure of composites found in nature and the ancient world, researchers at the University of Illinois at Urbana-Champaign have synthesized thin carbon nanotube (CNT) textiles that exhibit both high electrical conductivity and a level of toughness that is about fifty times higher than copper films, currently used in electronics.

"The structural robustness of thin metal films has significant importance for the reliable operation of smart skin and flexible electronics including...

Im Focus: Deep inside Galaxy M87

The nearby, giant radio galaxy M87 hosts a supermassive black hole (BH) and is well-known for its bright jet dominating the spectrum over ten orders of magnitude in frequency. Due to its proximity, jet prominence, and the large black hole mass, M87 is the best laboratory for investigating the formation, acceleration, and collimation of relativistic jets. A research team led by Silke Britzen from the Max Planck Institute for Radio Astronomy in Bonn, Germany, has found strong indication for turbulent processes connecting the accretion disk and the jet of that galaxy providing insights into the longstanding problem of the origin of astrophysical jets.

Supermassive black holes form some of the most enigmatic phenomena in astrophysics. Their enormous energy output is supposed to be generated by the...

Im Focus: A Quantum Low Pass for Photons

Physicists in Garching observe novel quantum effect that limits the number of emitted photons.

The probability to find a certain number of photons inside a laser pulse usually corresponds to a classical distribution of independent events, the so-called...

Im Focus: Microprocessors based on a layer of just three atoms

Microprocessors based on atomically thin materials hold the promise of the evolution of traditional processors as well as new applications in the field of flexible electronics. Now, a TU Wien research team led by Thomas Müller has made a breakthrough in this field as part of an ongoing research project.

Two-dimensional materials, or 2D materials for short, are extremely versatile, although – or often more precisely because – they are made up of just one or a...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

Event News

Expert meeting “Health Business Connect” will connect international medical technology companies

20.04.2017 | Event News

Wenn der Computer das Gehirn austrickst

18.04.2017 | Event News

7th International Conference on Crystalline Silicon Photovoltaics in Freiburg on April 3-5, 2017

03.04.2017 | Event News

 
Latest News

DGIST develops 20 times faster biosensor

24.04.2017 | Physics and Astronomy

Nanoimprinted hyperlens array: Paving the way for practical super-resolution imaging

24.04.2017 | Materials Sciences

Atomic-level motion may drive bacteria's ability to evade immune system defenses

24.04.2017 | Life Sciences

VideoLinks
B2B-VideoLinks
More VideoLinks >>>