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 Hope to discover sure signs of life on Mars? New research says look for the element vanadium
22.09.2017 | University of Kansas

nachricht Calculating quietness
22.09.2017 | Forschungszentrum MATHEON ECMath

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: The pyrenoid is a carbon-fixing liquid droplet

Plants and algae use the enzyme Rubisco to fix carbon dioxide, removing it from the atmosphere and converting it into biomass. Algae have figured out a way to increase the efficiency of carbon fixation. They gather most of their Rubisco into a ball-shaped microcompartment called the pyrenoid, which they flood with a high local concentration of carbon dioxide. A team of scientists at Princeton University, the Carnegie Institution for Science, Stanford University and the Max Plank Institute of Biochemistry have unravelled the mysteries of how the pyrenoid is assembled. These insights can help to engineer crops that remove more carbon dioxide from the atmosphere while producing more food.

A warming planet

Im Focus: Highly precise wiring in the Cerebral Cortex

Our brains house extremely complex neuronal circuits, whose detailed structures are still largely unknown. This is especially true for the so-called cerebral cortex of mammals, where among other things vision, thoughts or spatial orientation are being computed. Here the rules by which nerve cells are connected to each other are only partly understood. A team of scientists around Moritz Helmstaedter at the Frankfiurt Max Planck Institute for Brain Research and Helene Schmidt (Humboldt University in Berlin) have now discovered a surprisingly precise nerve cell connectivity pattern in the part of the cerebral cortex that is responsible for orienting the individual animal or human in space.

The researchers report online in Nature (Schmidt et al., 2017. Axonal synapse sorting in medial entorhinal cortex, DOI: 10.1038/nature24005) that synapses in...

Im Focus: Tiny lasers from a gallery of whispers

New technique promises tunable laser devices

Whispering gallery mode (WGM) resonators are used to make tiny micro-lasers, sensors, switches, routers and other devices. These tiny structures rely on a...

Im Focus: Ultrafast snapshots of relaxing electrons in solids

Using ultrafast flashes of laser and x-ray radiation, scientists at the Max Planck Institute of Quantum Optics (Garching, Germany) took snapshots of the briefest electron motion inside a solid material to date. The electron motion lasted only 750 billionths of the billionth of a second before it fainted, setting a new record of human capability to capture ultrafast processes inside solids!

When x-rays shine onto solid materials or large molecules, an electron is pushed away from its original place near the nucleus of the atom, leaving a hole...

Im Focus: Quantum Sensors Decipher Magnetic Ordering in a New Semiconducting Material

For the first time, physicists have successfully imaged spiral magnetic ordering in a multiferroic material. These materials are considered highly promising candidates for future data storage media. The researchers were able to prove their findings using unique quantum sensors that were developed at Basel University and that can analyze electromagnetic fields on the nanometer scale. The results – obtained by scientists from the University of Basel’s Department of Physics, the Swiss Nanoscience Institute, the University of Montpellier and several laboratories from University Paris-Saclay – were recently published in the journal Nature.

Multiferroics are materials that simultaneously react to electric and magnetic fields. These two properties are rarely found together, and their combined...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

Event News

“Lasers in Composites Symposium” in Aachen – from Science to Application

19.09.2017 | Event News

I-ESA 2018 – Call for Papers

12.09.2017 | Event News

EMBO at Basel Life, a new conference on current and emerging life science research

06.09.2017 | Event News

 
Latest News

Rainbow colors reveal cell history: Uncovering β-cell heterogeneity

22.09.2017 | Life Sciences

Penn first in world to treat patient with new radiation technology

22.09.2017 | Medical Engineering

Calculating quietness

22.09.2017 | Physics and Astronomy

VideoLinks
B2B-VideoLinks
More VideoLinks >>>