Access Restriction

Author Boldi, Paolo ♦ Vigna, Sebastiano
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Abstract—We recently measured the average distance of users in the Facebook graph, spurring comments in the scientific community as well as in the general press [1]. A number of interesting criticisms have been made about the meaningfulness, methods and consequences of the experiment we performed. In this paper we want to discuss some methodological aspects that we deem important to underline in the form of answers to the questions we have read in newspapers, magazines, blogs, or heard from colleagues. We indulge in some reflections on the actual meaning of “average distance ” and make a number of side observations showing that, yes, 3:74 “degrees of separation ” are really few. FOUR DEGREES OF SEPARATION In 2011, together with Marco Rosa, we developed a new tool for studying the distance distribution of very large (unweighted) graphs, called Hyper-ANF [2]: this algorithm built on powerful graph compression techniques [3] and on the idea of diffusive computation pioneered in [4]. The new tool made it possible to accurately study the distance distribution of graphs orders of magnitude larger than it was previously possible. The work on HyperANF was presented at the 20th World-Wide Web Conference, in Hyderabad (India), and Lars Backstrom happened to listen to the talk; he was intrigued by the possibility of experimenting our software on the Facebook graph and suggested a collaboration. Experiments were performed in the summer of 2011, resulting in the first world-scale socialnetwork graph-distance computations, using the entire Facebook network of active users (721 million users, 69 billion friendship links). The average distance (i.e., shortest-path length) observed was 4:74, corresponding to 3:74 intermediaries (or “degrees Partially supported by a Yahoo! faculty grant and by by the EU-
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article