Fun! My 2012 paper "Four degrees of separation” w/ Lars Backstrom, Paolo Boldi, Marco Rosa, and Sebastiano Vigna, a big crunch of the distance distribution of FB, has been awarded a Test of Time Award from the Web Science Trust. webscience.org/wst-selects-... Paper: stanford.edu/~jugander/pa... 1/ 🧵 - ThreadSky

jugander.bsky.social • 37 days ago

Fun! My 2012 paper "Four degrees of separation” w/ Lars Backstrom, Paolo Boldi, Marco Rosa, and Sebastiano Vigna, a big crunch of the distance distribution of FB, has been awarded a Test of Time Award from the Web Science Trust. https://webscience.org/wst-selects-2025-test-of-time-paper-winner/ Paper: https://stanford.edu/~jugander/papers/websci12-fourdegrees.pdf 1/ 🧵

Comments

amycoplan.bsky.social•37 days ago

jugander.bsky.social•37 days ago

Story time. The paper came about because Lars saw a talk on a paper by Paolo, Marco, and Seba at WWW'11, on "HyperANF", a clever sketching-based method for efficiently estimating the distance distribution of large graphs. He wondered: could it work on Facebook scale? https://arxiv.org/abs/1011.5599 2/

jugander.bsky.social•37 days ago

HyperANF required putting the graph in memory, but fortunately Paolo and Seba had also recently made progress on graph compression with their "Layered Label Propagation" method, also a WWW'11 paper, a clever way to create a very efficient linear indexing of graphs. https://arxiv.org/abs/1011.5425 2/

jugander.bsky.social•37 days ago

Lars connected with Paolo and Seba to see how well these ideas might be able to compress graphs at FB. I had interned at FB under Lars in 2010, was returning in 2011, and I quickly became the "hands on the keyboard" for this effort. 3/

jugander.bsky.social•37 days ago

The compression and computations were a real slog, something that was just barely feasible on the hardware we had at the time (a 1TB RAM machine), and it's with good reason that a considerable portion of the paper is about graph compression! But we figured it out. 4/

jugander.bsky.social•37 days ago

We ran the computations on the full FB graph, but also on the induced graph of the US, of Italy, and of Sweden, plus a union of Italy+Sweden to understand what country-country distances looked like. We studied each of these graphs in annual snapshots, through Jan 2007/08/09/10/11 and May 2011. 5/

jugander.bsky.social•37 days ago

Here's the "four degrees" result, where you see that the pairwise distance distribution (for the May 2011 FB graph) is really concentrated around 4. Single countries around 3. The avg distance for the FB graph was 4.74. Sweden and Italy both average 3.9. 6/

Comments

Posting Rules

Reply