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 xxwhat its symbols mean and yywhat its symbols mean are to connect. Writing Γ(x)\Gamma(x)what its symbols mean for xx's friends:

Score Formula Idea
Common neighbors ∣Γ(x)∩Γ(y)∣\lvert\Gamma(x) \cap \Gamma(y)\rvertwhat its symbols mean 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}what its symbols mean 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 does not 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 score), and how a Bloom filter keeps dismissed people out of the list.

Ranked suggestions
  1. 4 mutual friends (Alice, Bob, Carla, Eva)Adamic/Adar
  2. 2 mutual friends (Alice, Eva)Adamic/Adar
  3. 2 mutual friends (Bob, David)Adamic/Adar
Score: Daniel BergmanTotal 2.177
Adamic/Adarscore(x, y) = ∑ 1 / log₁₀ |Γ(z)|, over each mutual friend zMutual friends who have few friends count more.
Mutual friends
  • Alice Lind|Γ(z)| = 30 friends+0.6771/log(30)
  • Bob Nygren|Γ(z)| = 450 friends+0.3771/log(450)
  • Carla Holm|Γ(z)| = 85 friends+0.5181/log(85)
  • Eva Blom|Γ(z)| = 45 friends+0.6051/log(45)
Why Adamic/Adar down-weights popular friends: if Clara and Elsa share a friend Alice, who has only 30 friends, that suggests a shared circle (weight 0.677). Sharing David, who has 1,200 friends, says much less (weight 0.325). The Bloom filter holds the people already dismissed compactly, though it sometimes hides someone never dismissed.
Users1× instanceLoad balancer2× instancesSuggestions service2× instancesRanked suggestions2× instancesDismissed people(Bloom filters)2× instancesOffline scoring job2× instancesFriend graph (friendskept together)4× instancesUsers1× instanceLoad balancer2× instancesSuggestions service2× instancesRanked suggestions2× instancesDismissed people(Bloom filters)2× instancesOffline scoring job2× instancesFriend graph (friendskept together)4× instancesUsers1× instanceLoad balancer2× instancesSuggestions service2× instancesRanked suggestions2× instancesDismissed people(Bloom filters)2× instancesOffline scoring job2× instancesFriend graph (friendskept together)4× instances
Figure 4

Friend suggestions scored offline, stored for serving, and filtered against dismissed people.

An offline job reads the friend graph in batch, takes each user’s friends of friends as candidates, scores them, for example by Adamic/Adar, and stores each user’s ranked list. When a user opens their suggestions, the suggestions service reads that list and leaves out anyone in the user’s Bloom filter of people already dismissed, blocked or sent a request; a dismissal adds the person to the filter. The friend graph is placed so friends share a shard, which makes the batch job cheaper. The lesson gives no rate, so each server is drawn once with a spare.

  • Users: 1 × Users
  • Load balancer: 2 × Load balancer
  • Suggestions service: 2 × App server
  • Ranked suggestions: 2 × NoSQL store
  • Dismissed people (Bloom filters): 2 × Cache
  • Offline scoring job: 2 × App server
  • Friend graph (friends kept together): 4 × NoSQL store
  • Users sends requests to Load balancer
  • Load balancer sends requests to Suggestions service
  • Suggestions service sends requests to Ranked suggestions
  • Suggestions service sends requests to Dismissed people (Bloom filters)
  • Offline scoring job sends requests to Friend graph (friends kept together)
  • Offline scoring job sends requests to Ranked suggestions

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.
Sources4