Recommend Connections Through Mutual Friends and Evaluate the Ranking

Scenario

A social platform wants to build a "People You May Know" (PYMK) recommendation feature. The system suggests potential connections to a user based on their social network topology—specifically leveraging mutual friends—and ranks candidates to maximize valid, accepted connections.

Requirements

• Functional Requirements:
  • For a given user u, identify candidate users who share at least one mutual friend with u, strictly excluding u themselves and existing 1-hop connections.
  • Formulate bounded candidate scoring heuristics (mapping similarity into a known interval such as [0, 1]) to score topological proximity before or alongside ML ranking.
  • Rank candidates using candidate features (graph topology, mutual connection counts, interaction history, user profile attributes).
  • Support an offline evaluation framework using ranking metrics (such as NDCG or MAP) and justify the choice of relevance labels.
• Non-Functional Requirements & Scale:
  • 100 million active users; 10 billion total undirected friendship edges.
  • Average user has ~200 friends, but degree distribution is heavy-tailed (super-connectors have 10,000+ friends).
  • Serving latency: p99 under 100 ms for top-20 recommendations.

What to Cover

1. Candidate Generation (Retrieval): Architecture for 2-hop neighbor traversal at scale. Explain how to handle high-degree nodes ("celebrity/hub problem") to avoid combinatorial explosion.
2. Bounded Affinity Scoring: Define mathematical scoring functions (e.g., Jaccard similarity, normalized Adamic-Adar, or Cosine similarity of adjacency vectors) that map to a bounded range like [0, 1]. Discuss why raw mutual friend count is insufficient.
3. ML Ranking Pipeline: Describe features, training data generation (handling negative samples and impression bias), and the ranking objective (e.g., point-wise calibrated probability vs. list-wise learning to rank).
4. Evaluation Strategy: Detail how to evaluate the ranking system offline using NDCG. Explain the theoretical assumptions of NDCG (e.g., item independence, position discounts) versus real-world social network dynamics, and define the online A/B test metrics.