Social-Network Analysis Using Topic Models: Taming the Popularity Bias in Graphs

TL;DR

How do you categorize a user like Barack Obama on Twitter using only follow relationships? Standard topic models (LDA) fail because "super-nodes" appear in every category, creating noise. This paper introduces Two-Step Labeling and Threshold Noise Filtering, techniques that allow LDA to accurately group popular users into meaningful cohorts (e.g., "Politics" vs. "Cycling") by treating the follow-graph as a text corpus while carefully decoupling the influence of celebrity nodes.

Context: The Social Graph as a Document

In the world of Information Retrieval, the follow relationship is often chaotic. A user follows another for varied reasons: shared interests, professional ties, or pure celebrity status. This paper maps this graph onto the framework of Latent Dirichlet Allocation (LDA):

• Follower $\to$ A Document ($D$)
• Followed User $\to$ A Word ($W$)
• Interests $\to$ Latent Topics ($Z$)

However, there is a fundamental conflict. In NLP, "stop words" (like the, and) are useless and discarded. In social networks, "stop nodes" (like Barack Obama or Britney Spears) are the most important entities. Standard LDA spreads these popular nodes across all topics, making specialized clusters indistinguishable.

Methodology: Sophisticated Decoupling

The authors argue that we must preserve popular nodes but restrict their "gravitational pull" during the topic formation phase.

1. Two-Step Labeling

This is the core innovation. Instead of training on the whole graph at once, the process is split:

• Step 1 (Topic Establishment): Run LDA on a subset of the graph excluding popular users. This creates "clean" topics (e.g., a "Mobile Gadgets" topic that isn't polluted by general news accounts).
• Step 2 (Labeling Phase): The topics are frozen, and the edges leading to popular users are then assigned to these pre-established topics using collapsed Gibbs sampling.

2. Threshold Noise Filtering

Even with Two-Step Labeling, a popular user might have a high absolute number of assignments to an irrelevant topic simply because they have millions of followers. The authors implement a cut-off $C$: $P(z_k|g_i)<C\Rightarrow N_{g_i{z}_k}=0$ This acts as a "de-noising" filter, ensuring that a user is only associated with topics where they have a significant, non-coincidental presence.

Figure: The Threshold Noise Filtering process illustrated.

Experiments: Human-Perceived Quality

The researchers tested their methods on a real-world Twitter dataset of 10 million edges. While Perplexity ( a measure of how well the model predicts new data) remained stable across methods, the Human-Perceived Quality told a different story.

• Human Survey: 14 participants judged the relevance of users within generated topic groups.
• The Winner: The combined "Filter-2Step" method outperformed the baseline LDA by 1.64x.

Figure: Note the significant quality jump for 2step and Filter-2step methods.

Qualitative Win

In the Standard LDA (Base), a "Cycling" topic group incorrectly included Barack Obama and Stephen Fry simply because they are popular. In the Filter-2Step version, popular technology accounts like Google and Wired were correctly clustered together, while general news accounts like CNN were filtered out, resulting in a much "shorter" and more relevant list for technology enthusiasts.

Critical Insight & Perspectives

This work demonstrates that the structure of the graph—who follows whom—carries immense semantic weight, potentially more than the actual text of tweets, which can be noisy or misleading.

Limitations:

• The model assumes a static graph. In modern social networks, "popularity" is highly temporal (e.g., a politician during an election).
• It requires a predefined boundary $V$ to distinguish "popular" from "normal" users, which may require manual tuning for different networks.

Future Outlook: This approach provides a robust blueprint for Recommendation Systems. By understanding why a user follows someone (the topic label on the edge), platforms can recommend "Relevant Friends" instead of just "Popular Friends," mitigating the "rich-get-richer" phenomenon where only celebrities get recommended.

Takeaway

Don't treat celebrities as stop-words. Treat them as multi-faceted entities that require a two-stage filtering process to accurately place within a social interest graph.