SpecialityIstituto dei Sistemi Complessi - CNR, Firenze, IT

Why are there six degrees of separation in a social network?In the short story "Chains" (1929), the Hungarian writer Frigyes Karinthy described a game where a group of people was discussing how the members of the human society were closer together than ever before. To prove this point, one participant proposes that any person out of the entire Earth population (around 1.8 billion at that time) could be reached using nothing except each personal network of acquaintances, betting that the resulting chain would be of no more than five individuals. The story coined the expression `six degrees of separation' to reflect the idea that all people of the world are six or fewer social connections apart from each other. In 1967, Stanley Milgram performed his famous set of experiments on social distancing where, with a limited sample of a thousand individuals, it was shown that people in the United States are indeed connected by a small number of acquaintances. Later on, Duncan Watts recreated Milgram's experiments with Internet email users by tracking 24,163 chains aimed at 18 targets from 13 countries and confirmed that the average number of steps in the chains was around six. Furthermore, many experiments conducted at a planetary scale on various social networks verified the ubiquitous character of this feature: 1) a 2007 study by Jure Leskovec and Eric Horvitz (with a data set of 30 billion conversations among 240 million Microsoft Messenger users) revealed the average path length to be 6, 2) the average degree of separation between two randomly selected Twitter users was found to be 3.435, and 3) the Facebook's network in 2011 (721 million users with 69 billion friendship links) displayed an average distance between nodes of 4.74.. Such abundant and consistent evidence points to the fact that the structure of these networks radically differs from either that of regular networks (where the diameter scales linearly with the size) and that of classical small-world networks (where, instead, the scaling law is logarithmic). A clear explanation of the mechanisms through which social networks organize into ultra-small world states (where the diameter does not depend on the system size over several orders of magnitude) is, however, still missing. Why does such a collective property emerge? What are its fundamental mechanisms? Why is the common shortest path length between units of a social network six, rather than five or seven or any other number, implying an average distance which is also not far from six? In my talk, I will show that the mechanism behind such observed regularity can be found in a dynamic evolution of the network. Precisely, I will rigorously show that, when a simple compensation rule between the cost incurred by nodes in maintaining connections and the benefit accrued by the chosen links is governing the evolution of a network, the asymptotic equilibrium state (a Nash equilibrium where no further actions would produce more benefit than cost), features a diameter which does not depend on the system's size, and is equal to 6. In other words, I will prove that any network where nodes strive to increase their centrality by forming connections if and only if their cost is smaller than the payoff tends to evolve into an ultra-small world state endowed with the 'six degree of separation' property, irrespective of its initial structure. Therefore, evolutionary rules of the kind traditionally associated with human cooperation and altruism can in fact account also for the emergence of such a famous attribute of social networks.