Social Circle Discovery: Why Simple LDA Beats Complex Structural Models

TL;DR

Managing privacy on social media is a nightmare because manually grouping friends into "circles" is tedious. This paper introduces an elegant solution: treat your friends like a collection of words. By using Latent Dirichlet Allocation (LDA)—a tool usually reserved for finding topics in text—the authors discovered that they could group friends more accurately and faster than complex models that try to "math out" the exact shape of a social network.

Background & Motivation: The 5% Paradox

Most Facebook users have hundreds of friends, yet only 5% bother to create custom friend lists. This leads to "sharing violations"—accidentally showing a party photo to your boss or a political rant to your grandmother.

The technical challenge is that social circles aren't just about who you know (connectivity) or who you are (profile attributes); they are a messy combination of both. Furthermore, circles overlap: your high school friend might also be your current coworker.

The "Bag-of-Friends" Insight (Methodology)

The paper's genius lies in its simplicity. Instead of building a complex "Network + Attribute" joint probabilistic model, the authors repurposed LDA.

How it works:

1. Friend as a Document: Every friend you have is treated as a single "document."
2. Attributes as Words: If a friend went to "Stanford" and lives in "San Francisco," those become words in the document.
3. Connectivity as Words: The authors added the User ID of the friend and the User IDs of all their neighbors as additional words.
4. Topics as Circles: LDA processes these "documents" and identifies hidden "topics." In this context, a topic isn't "Politics" or "Sports"—it is a Social Circle.

By mixing IDs and attributes into the same "vocabulary," the model naturally finds clusters where people have both similar backgrounds AND high connectivity.

Experiments: David vs. Goliath

The authors compared their LDA-based approach against the heavyweights: Block-LDA, SCAN, and the then-SOTA McAuley-Leskovec model.

Key Results:

• Accuracy: On Facebook data, the simple LDA approach reached an accuracy score ($\sigma$) of 0.84, matching the much more complex McAuley model.
• Twitter Breakthrough: On Twitter data, the LDA approach actually outperformed the state-of-the-art, likely because LDA is more robust to the "noisy" nature of Twitter lists.
• Efficiency: Because LDA is a well-optimized, standard algorithm, it runs at a fraction of the computational cost of custom structural models.

Critical Insights: Why This Works

The paper reveals a fundamental truth in machine learning: Feature Engineering often trumps Model Complexity.

The exploratory analysis (shown below) proves that neither connectivity nor attributes alone are sufficient. Most circles have a "Modularity" score near zero, meaning they don't look like distinct groups if you only look at the graph. But when you add profile "words," the latent structure becomes clear.

Conclusion & Limitations

This paper is a masterclass in Occam's Razor. By treating a social graph as a text corpus, they bypassed the need for expensive graph-mining algorithms.

Limitations:

• The model struggles with numerical data (like age or years of experience) because LDA requires categorical "tokens."
• It doesn't yet account for Tie Strength (how often you talk to someone), which is a massive signal for privacy.

Future Outlook: The next generation of this work likely involves Graph Embeddings or Hyper-relational LDA, but the core takeaway remains: don't over-engineer the model until you've fully exploited the representation of the data.