FjellSystem Design Lab
Lesson 13.4• 8 min read

People you may know: ranking mutual friends

Common neighbors, Jaccard and Adamic/Adar scores, offline candidate generation, and filtering dismissed suggestions.

What you will learn

  • Rank friends of friends with common neighbors, Jaccard and Adamic/Adar scores.
  • Explain why Adamic/Adar gives less weight to popular mutual friends.
  • Compute suggestions offline, and filter out people already dismissed.

Recommending friends

"People You May Know" goes beyond the primer's scope, but it uses the same graph. Candidates are usually friends of friends. The question is how to rank them.

Liben-Nowell and Kleinberg, "The Link-Prediction Problem for Social Networks", compare several scores for how likely xx and yy are to connect. Writing Γ(x)\Gamma(x) for xx's friends:

Score Formula Idea
Common neighbors ∣Γ(x)∩Γ(y)∣\lvert\Gamma(x) \cap \Gamma(y)\rvert More mutual friends, more likely
Jaccard's coefficient ∣Γ(x)∩Γ(y)∣∣Γ(x)∪Γ(y)∣\dfrac{\lvert\Gamma(x) \cap \Gamma(y)\rvert}{\lvert\Gamma(x) \cup \Gamma(y)\rvert} Mutual friends relative to all their friends
Adamic/Adar ∑z∈Γ(x)∩Γ(y)1log⁡∣Γ(z)∣\displaystyle\sum_{z \in \Gamma(x) \cap \Gamma(y)} \frac{1}{\log \lvert\Gamma(z)\rvert} Mutual friends who have few friends count more

Why Adamic/Adar down-weights popular friends. A mutual friend with 20 friends says more about a shared circle than one with 2,000. With base-10 logarithms, the weights are 1/log⁡1020≈0.771/\log_{10} 20 \approx 0.77 versus 1/log⁡102000≈0.301/\log_{10} 2000 \approx 0.30. The base doesn't change the ranking; it scales every score by the same factor. A mutual friend always has at least two friends (both of you), so the logarithm is never zero.

Computing it at scale

Scoring every pair is impossible, so systems compute candidates and scores in batch, offline. Placement matters here too. In Ugander and Backstrom's slides on Balanced Label Propagation (lesson 3), keeping more friendships on the same shard cut the median number of machines a People You May Know query touched from 60 to 9. Query time fell by 49% and network traffic by 63%.

When showing suggestions, filter out people the user has already dismissed, blocked or sent a request to. A Bloom filter (chapter 6) can hold "already dismissed" compactly, with two caveats:

  • It has false positives: it occasionally hides someone who was never dismissed.
  • A standard Bloom filter cannot remove entries, so an undo needs another structure, or a rebuilt filter.

People you may know, ranked

How mutual friends are weighted (the Adamic-Adar index), and how a Bloom filter keeps dismissed people out of the list.

Ranked suggestions
  1. 4 mutual connections (Alice, Bob, Carla, Eva)Adamic-Adar
  2. 2 mutual connections (Alice, Eva)Adamic-Adar
  3. 2 mutual connections (Bob, David)Adamic-Adar
Score: Daniel BergmanTotal 2.177
Adamic-Adar indexScore(u, v) = ∑ 1 / log₁₀(|N(w)|)A rare mutual friend (few friends of their own) counts far more than a celebrity.
Mutual connections
  • Alice Lind|N(w)| = 30 friends+0.6771/log(30)
  • Bob Nygren|N(w)| = 450 friends+0.3771/log(450)
  • Carla Holm|N(w)| = 85 friends+0.5181/log(85)
  • Eva Blom|N(w)| = 45 friends+0.6051/log(45)
Redis cache hit: 1.2 ms
Why Adamic-Adar beats a raw count: if Clara and Elsa share a friend Alice, who has only 30 friends, that suggests a real circle (weight 0.677). Sharing David, a CTO with 1,200 connections, says much less (weight 0.325). With a Bloom filter suppressing dismissed suggestions in O(1), suggestions stay relevant and fast.
Figure 4: Friend suggestions scored offline, stored for serving, and filtered against dismissed candidates.
  • Mobile Feed Ingress: 1 × Clients & Users
  • PYMK Ranking & Filter Service: 8 × App Compute Server
  • Redis Candidate & Bloom Filter: 4 × Redis In-Memory Cache
  • Kafka Social Activity Bus: 3 × Message Queue / Kafka
  • Offline Candidate Scoring: 10 × App Compute Server
  • S3 Graph Parquet Data Lake: 2 × Object Storage (S3)
  • Mobile Feed Ingress sends requests to PYMK Ranking & Filter Service
  • PYMK Ranking & Filter Service sends requests to Redis Candidate & Bloom Filter
  • PYMK Ranking & Filter Service sends requests to Kafka Social Activity Bus
  • Kafka Social Activity Bus sends requests to Offline Candidate Scoring
  • Offline Candidate Scoring sends requests to S3 Graph Parquet Data Lake
  • Offline Candidate Scoring sends requests to Redis Candidate & Bloom Filter

Key takeaways

  • Candidates are usually friends of friends; the score decides the order.
  • Adamic/Adar weights each mutual friend by 1/log⁡1/\log of their friend count, so a mutual friend with 20 friends counts for more than one with 2,000.
  • Scores are computed in batch offline, and placement that keeps friends together makes that cheaper.
  • A Bloom filter can hold "already dismissed" compactly, but it sometimes hides someone wrongly and cannot remove an entry.

Sources

Adapted from The System Design Primer by Donne Martin, licensed under CC BY 4.0. Changes were made.