LP-Sensor: Scaling Bursty Event Detection to Millions of Users

TL;DR

Detecting "breaking news" or viral trends in social media usually requires monitoring a massive stream of data. This paper introduces a scalable Linear Programming (LP) framework to select a tiny, budgeted fraction of users (sensors) that can represent the entire network's burstiness. By using a sub-gradient method, the authors make it possible to find optimal sensors in networks with millions of users where traditional greedy algorithms like CELF fail to scale.

Backgound: The Search for the "Early Birds"

In social networks, every user acts as a "sensor." When a disaster strikes or a meme goes viral, these sensors fire off tweets. However, third-party developers often face API rate limits or high costs for data collection. The challenge is: Which 5,000 users should you follow to ensure you won't miss the next global burst?

The Bottleneck of Sub-modularity

Most classic solutions treat this as a Sub-modular Maximization problem. While greedy algorithms provide a $(1-1/e)$ approximation, they are inherently "one-by-one" (selecting the 1st best, then the 2nd best, etc.). In a social network of millions, this "greedy" approach becomes an expensive marathon. Furthermore, identifying a burst is harder than identifying an outbreak—a burst requires high evidence density in a short window, a property that doesn't always play nice with traditional sub-modular functions.

Methodology: Turning Constraints into Gradients

The authors shift the perspective from greedy selection to Constraint Satisfaction.

1. Additive Burstiness: They identify that many burst metrics (like velocity and acceleration) are additive. The burstiness of a set of users is simply the sum of the burstiness observed from each individual user.
2. LP Relaxation: By treating user selection as a probability (between 0 and 1) rather than a hard binary choice (0 or 1), they transform the NP-hard problem into a continuous LP problem.
3. Sub-gradient Descent: They recognize the LP problem is equivalent to a convex optimization task. They use a sub-gradient method to "push up" the detection threshold for all known bursty cascades simultaneously.

Figure: The sub-gradient method works by iteratively adjusting the "weight" of each user to ensure all historical bursty cascades remain detectable.

Experiments: Twitter and Weibo at Scale

The researchers tested their method on two massive datasets:

• Twitter (Singapore): 184k users, 32M tweets.
• Weibo (Shanghai): 105k users, 19M tweets.

Performance vs. Budget

As the budget ($m$)—the number of users you are allowed to follow—increases, the LP-based selection consistently achieves higher AUC than degree-based heuristics or CELF.

Figure: ROC curves showing LP solution (Red Line) dominating other methods across both URL and Hashtag cascades.

Efficiency: The Speed Demon

The most striking result is the runtime. While greedy algorithms take hours or even days to select 5,000 sensors, the sub-gradient method finishes in minutes, and its runtime is independent of the budget size.

Figure: Runtime comparison showing that the sub-gradient method (Blue) is significantly faster and more stable than Simplex or Interior-point methods.

Critical Insight & Conclusion

Why does it work? The LP method doesn't just pick "popular" users; it picks a diverse portfolio of sensors that collectively cover different topics and communities. The users selected by this method tend to have higher retweet ratios and are often news media accounts (like Channel NewsAsia), yet it also finds influential "normal" users that a simple degree-based search would miss.

Takeaway: If you are building a trend-monitoring tool, don't just follow the most popular celebrities. Use a global optimization approach like this LP framework to build a sensor network that is both efficient and comprehensive.

Future Work: The authors suggest moving beyond hashtags and URLs toward topic-agnostic burst detection, where the model must learn what a "topic" is while simultaneously deciding who to monitor.