Featured Research

from universities, journals, and other organizations

'Six Degrees Of Kevin Bacon' Game Provides Clue To Efficiency Of Complex Networks

Date:
November 18, 2008
Source:
University of California - San Diego
Summary:
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.

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.
Credit: CAIDA, San Diego Supercomputer Center, UC San Diego

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.

Related Articles


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).

“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.


Story Source:

The above story is based on materials provided by University of California - San Diego. Note: Materials may be edited for content and length.


Cite This Page:

University of California - San Diego. "'Six Degrees Of Kevin Bacon' Game Provides Clue To Efficiency Of Complex Networks." ScienceDaily. ScienceDaily, 18 November 2008. <www.sciencedaily.com/releases/2008/11/081117153207.htm>.
University of California - San Diego. (2008, November 18). 'Six Degrees Of Kevin Bacon' Game Provides Clue To Efficiency Of Complex Networks. ScienceDaily. Retrieved October 31, 2014 from www.sciencedaily.com/releases/2008/11/081117153207.htm
University of California - San Diego. "'Six Degrees Of Kevin Bacon' Game Provides Clue To Efficiency Of Complex Networks." ScienceDaily. www.sciencedaily.com/releases/2008/11/081117153207.htm (accessed October 31, 2014).

Share This



More Mind & Brain News

Friday, October 31, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Studying Effects of Music on Dementia Patients

Studying Effects of Music on Dementia Patients

AP (Oct. 30, 2014) — The University of Wisconsin-Milwaukee is studying the popular Music and Memory program to see if music, which helps improve the mood of Alzheimer's patients, can also reduce the use of prescription drugs for those suffering from dementia. (Oct. 30) Video provided by AP
Powered by NewsLook.com
Techy Tots Are Forefront of London's Baby Show

Techy Tots Are Forefront of London's Baby Show

AP (Oct. 28, 2014) — Moms and Dads get a more hands-on approach to parenting with tech-centric products for raising their little ones. (Oct. 28) Video provided by AP
Powered by NewsLook.com
Cocoa Could Be As Good For Memory As It Is For A Sweet Tooth

Cocoa Could Be As Good For Memory As It Is For A Sweet Tooth

Newsy (Oct. 27, 2014) — Researchers have come up with another reason why dark chocolate is good for your health. A substance in the treat can reportedly help with memory. Video provided by Newsy
Powered by NewsLook.com
Five-Year-Olds Learn Coding as Britain Eyes Digital Future

Five-Year-Olds Learn Coding as Britain Eyes Digital Future

AFP (Oct. 27, 2014) — Coding has become compulsory for children as young as five in schools across the UK. Making it the first major world economy to overhaul its IT teaching and put programming at its core. Duration: 02:19 Video provided by AFP
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
 
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:  

Breaking News:

Strange & Offbeat Stories

 

Health & Medicine

Mind & Brain

Living & Well

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:  

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile iPhone Android Web
Follow Facebook Twitter Google+
Subscribe RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins