Graphs, Ranking & Search

Friends of Friends

Each dot is a person and each line is a friendship. Tap someone to see their friend group and who they might want to meet.

Look, the dots huddle into clumps! Tap a person and I will tell you who their friends have in common with them.

The town

Challenges

Say hello: tap a person to see their friends and suggestions.
Find the most popular person: the dot with the most friends. Big dots are a clue.
Take a suggestion: press Add on one of the suggested people.
Build a bridge: make friends between two different groups.
Break up a friendship (use the Make or break mode) and watch the suggestions change.

What just happened?

For grown-ups: what's really going on

The town is an undirected graph G = (V, E) drawn with a force-directed layout (Fruchterman-Reingold style): nodes repel like charges, edges act as springs, a weak gravity keeps everything in view.

  • Community detection uses asynchronous label propagation (Raghavan et al. 2007): visit nodes in random order and adopt the most common label among neighbours, with random tie-breaks. It is very fast but non-deterministic; we fix the seed so results are repeatable. Louvain and Leiden optimise modularity instead and are more robust.
  • Link prediction with common neighbours scores a pair by |N(u) ∩ N(v)|. The Jaccard version normalises by the size of the union: |N(u) ∩ N(v)| / |N(u) ∪ N(v)|, so people with huge friend lists do not win just by being popular.
  • Real systems add more signals (Adamic-Adar weights rare shared friends more, plus profile and activity data) and learn the weights with a model. The idea that friends of friends become friends is called triadic closure.
  • Suggestions can create filter bubbles: recommending only people already close to your group strengthens the clumps.

Further reading: Easley and Kleinberg, Networks, Crowds, and Markets · Liben-Nowell and Kleinberg, The link-prediction problem for social networks (2007).