按年被提到
20112011 · 2 次2026
社会、经济与科学研究›社会物理与科学趣闻·arXiv:1111.4570 · cs.SI

Four Degrees of Separation

Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander, Sebastiano Vigna · 2011
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2011-11-22 · 最近 2013-02-13
3不同的人
2活跃月份
3讨论串
41被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Frigyes Karinthy, in his 1929 short story "Láancszemek" ("Chains") suggested that any two persons are distanced by at most six friendship links. (The exact wording of the story is slightly ambiguous: "He bet us that, using no more than five individuals, one of whom is a personal acquaintance, he could contact the selected individual [...]". It is not completely clear whether the selected individual is part of the five, so this could actually allude to distance five or six in the language of graph theory, but the "six degrees of separation" phrase stuck after John Guare's 1990 eponymous play. Following Milgram's definition and Guare's interpretation, we will assume that "degrees of separation" is the same as "distance minus one", where "distance" is the usual path length-the number of arcs in the path.) Stanley Milgram in his famous experiment challenged people to route postcards to a fixed recipient by passing them only through direct acquaintances. The average number of intermediaries on the path of the postcards lay between 4.4 and 5.7, depending on the sample of people chosen. We report the results of the first world-scale social-network graph-distance computations, using the entire Facebook network of active users (\approx721 million users, \approx69 billion friendship links). The average distance we observe is 4.74, corresponding to 3.74 intermediaries or "degrees of separation", showing that the world is even smaller than we expected, and prompting the title of this paper. More generally, we study the distance distribution of Facebook and of some interesting geographic subgraphs, looking also at their evolution over time. The networks we are able to explore are almost two orders of magnitude larger than those analysed in the previous literature. We report detailed statistical metadata showing that our measurements (which rely on probabilistic algorithms) are very accurate.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论ot · 2013-02

“Among other things, HyperLogLog was used in the recent computation of Facebook's average diameter ("Four degrees of separation" [1]). In this paper Google squeezes out every last bit of precision, using tables to correct the bias and specialized algorithms for small cardinalities. It is an outstanding effort, I guess they use these counters everywhere. …”

HyperLogLog in Practice: Algorithmic Engineering of Cardinality Estimation原评论 ↗
被提交为 story · 2 次