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 xwhat its symbols mean and ywhat its symbols mean are to connect. Writing Γ(x)what its symbols mean for x's friends:
Score
Formula
Idea
Common neighbors
∣Γ(x)∩Γ(y)∣what its symbols mean
More mutual friends, more likely
Jaccard's coefficient
∣Γ(x)∪Γ(y)∣∣Γ(x)∩Γ(y)∣
Mutual friends relative to all their friends
Adamic/Adar
z∈Γ(x)∩Γ(y)∑log∣Γ(z)∣1what 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/log1020≈0.77 versus 1/log102000≈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.
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.
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)