Social Sensors Early Detection of Contagious Outbreaks in Social Media

摘要

Cascades of information in social media (like Twitter, Facebook, Reddit, etc.) have become well-established precursors to important societal events such as epidemic outbreaks, flux in stock patterns, political revolutions, and civil unrest activity. Early detection of such events is important so that the contagion can either be leveraged for applications like viral marketing and spread of ideas [4] or can be contained so as to quell negative campaigns [2] and minimize the spread of rumors. In this work, we algorithmically design social sensors, a small subset of the entire network, who can effectively foretell cascading behavior and thus detect contagious outbreaks. While several techniques (for example, the friendship paradox [3]) to design sensors exist, most of them exploit the social network topology and do not effectively capture the bursty dynamics of a social network like Twitter, since they ignore two key observations (1) Several viral phenomenal have already cascaded in the network (2) most contagious outbreaks are a combination of network flow and external influence. In light of those two observations, we present an alternate formalism for information where we describe information diffusion as a forest (a collection of trees). Intuitively, our forest model is a more natural metaphor because most social media phenomena that go truly viral have multiple origins, thus are a combination of several trees. We show that our model serves as a solid foundation to foretell the emergence of viral information cascades. We then use the forest model in conjunction with past information cascades, to view the problem under the algorithmic lens of a hitting set and select a subset of nodes (of the social network) by prioritizing their activation time and their occurrence in the cascades.