Rhea: Capturing Emerging Authorities in the Chaos of Social Streams

TL;DR

Rhea is a real-time sampling algorithm that identifies and captures content from authoritative users in social streams (Twitter, StackOverflow) as they emerge. By utilizing a "sketch-based" approach, it maintains a dynamic ranking of users with minimal memory, significantly outperforming traditional static "white-lists" that fail to adapt to changing trends.

Background Positioning

In the spectrum of Social Network Analysis (SNA), Rhea sits at the intersection of Stream Processing and Expertise Discovery. While most SOTA methods rely on pre-defined lists or heavy offline graph processing (like PageRank), Rhea provides a lightweight, online alternative for applications like news detection and sentiment analysis.

The Problem: The Volatility of Influence

The core motivation for Rhea is the observation that static white-lists decay rapidly. In a study conducted by the authors, they found that a list of top Twitter users from September lost nearly 50% of its relevance by December.

Prior work has relied on user-generated "Twitter Lists" to identify authorities, but this creates a "cold start" problem for new influencers and a "zombie" problem for those who are no longer active. To build a truly efficient content recommendation or opinion mining system, we need a filter that evolves at the same speed as the stream itself.

Methodology: The "Auth-Value" and Efficient Sketches

1. The Auth-Value Metric

The authors generalize the "z-score" (originally for Q&A sites) into a metric called auth-value. It is defined by the following physical intuition: True authorities attract attention (In-degree) without needing to desperately seek it (Out-degree). $auth(u)=\frac{in(u)-out(u)}{\sqrt{in(u)+out(u)}}$ This formula penalizes "reciprocal" users (spammers or conversationalists) and highlights "hubs" of information.

2. Architecture: Count-Min Sketch & Top-K-Heap

To handle 500 million posts without a memory explosion, Rhea uses two Count-Min Sketches (CMS) to track the in-degree and out-degree of every user seen in the stream. CMS allows for a probabilistic count with a tiny memory footprint.

To keep track of who is currently "winning," Rhea maintains a specialized Top-K-Heap.

• Hash-Table: For $O(1)$ lookup to see if a user is already in the "Top K."
• Min-Heap: For $O(\log K)$ updates and tracking the current "threshold" for authority.

Figure 1: Conceptual overview of deriving an authority network from a raw stream.

Experiments: Real-World Performance

The authors tested Rhea against WhiteList methods on Twitter and StackOverflow datasets.

Significant Hits on Recall and Precision

Rhea achieved a consistently high F1-score (~0.8) while WhiteList methods saw their performance plummet as the "gap" between the list creation and the stream time increased.

Figure 2: Performance comparison. Note that Rhea (bold lines) maintains high recall even as K increases, unlike static methods.

Ranking Accuracy (NDCG)

Using Normalized Discounted Cumulative Gain (NDCG), the authors proved that Rhea doesn't just find any authority; it finds the best ones. The rank correlation (Spearman's ρ) for Rhea was nearly perfect compared to a "ground truth" established by looking at the entire dataset offline.

Critical Analysis & Future Outlook

Takeaways

Rhea proves that local interaction data (mentions, replies) within a stream is a sufficient proxy for global network importance if sampled correctly. The use of a post-processing "filtering step" is a clever way to undo the errors of "greedy" sampling early in the stream's life.

Limitations

1. Susceptibility to Sybil Attacks: While the author-value penalizes simple reciprocation, sophisticated "spam farms" could potentially manipulate these scores.
2. Topic Neutrality: Rhea finds "general" authorities. For niche applications (e.g., finding experts only in "Quantum Computing"), a topical filter would need to be layered on top.

Future Work

Rhea paves the way for a new generation of Adaptive Recommender Systems that can handle the sheer scale of the "Firehose" while remaining sensitive to the rising stars of social media.

Reference Image Placeholders: Figure 3: Graphical representation of the Count-Min Sketch update logic used in Rhea.