From Milgram to multiplexes: mutual greedy routing explained for everyone

My average intermediate degree of separation from everyone on Facebook is 3.39 [1]. This means that I probably know you through a chain of 3 to 4 intermediate individuals. That does not seem a lot, but how can one find these people? Facebook can calculate this number because they know the structure of the whole network: who is connected to whom, globally. But without this knowledge, how can I reach any individual?

The answer dates back to the origin of the famous “six degrees of separation”. In 1967 Stanley Milgram conducted an experiment. Participants chosen as starting points of the study were provided with information about a target person to whom they had to send a  letter. The results were quite surprising. On average, it took only five steps for the letter to reach the target. Five steps means six degrees of separation; an expression that has become famous since Milgram’s experiment. This means that people can actually find the chains of intermediate individuals connecting everyone in a small number of steps. As Milgram puts it, “each intermediary moves the folder toward the target person. That is, a certain amount of information about the target person –his place of employment, place of residence, schooling, and so forth– is given to the starting subject, and it is on the basis of this information alone that he selects the next recipient” [2]. Just as people nowadays use Facebook and Twitter simultaneously, individuals in Milgram’s study used information from multiple “domains” at the same time, e.g., the geographic location and occupation of an individual, to bring the message closer to its destination.

We can understand these different domains as different networks, like in the mentioned case of Facebook and Twitter. In these networks, individuals are represented as nodes. Individuals use all networks to disseminate information, which increases its spread significantly and can enhance the chance to reach other individuals. But, how can one reach any individual using both Facebook and Twitter, without the knowledge of who is connected to whom in the whole network? And, under which conditions is it better to use both networks compared to using only a single network?

We show that the key to answer these questions lies within hidden geometric relations between the different networks, which are present in many different real systems. Our findings reveal that these relations are optimal for reaching nodes in the system using several networks, in the same way as individuals reached the target in Milgram’s experiment. In other words, if the discovered relations between the networks are present, individuals can be reached more efficiently if one uses several networks at the same time. Furthermore, we show that adding only a small number of other networks can increase the message transfer efficiency close to perfection. On the contrary, if the discovered geometric relations were absent, there would be no benefit of using multiple networks compared to using a single network.

The discovered geometric relations across networks are a fundamental property of the organization of natural and human made systems. The universality of the presence of these relations suggests that there are some common underlying principles —like physical laws— that govern all of these systems. Our findings can have important applications in diverse domains, ranging from improving information transport and navigation or search in communication systems and online social networks, to understanding functional and structural networks in the human brain and deciphering their precise relationship(s), to predicting links among nodes (e.g., terrorists) in a specific network by knowing their connectivity in some other network.

[1] https://research.facebook.com/blog/three-and-a-half-degrees-of-separation/.
[2] Jeffrey Travers and Stanley Milgram. An experimental study of the small world problem. Sociometry, 32(4):425–443, 1969.

Download this article as PDF: here

Want to know more?

Read the paper: http://www.nature.com/nphys/journal/v12/n11/full/nphys3812.html

Check out a presentation: 

Or contact me

 

Advertisements

2 thoughts on “From Milgram to multiplexes: mutual greedy routing explained for everyone

  1. Hi. The Nature paper is asking me to pay for access, and your “Download this article as PDF” doesn’t seem to contain the full text. Am I missing something, or could you put an open-access link on your site? Thanks.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s