Social Network Monitoring for Bursty Cascade Detection

Social network services have become important and efficient platforms for users to share all kinds of information. The capability to monitor user-generated information and detect bursts from information diffusions in these social networks brings value to a wide range of real-life applications, such as viral marketing. However, in reality, as a third party, there is always a cost for gathering information from each user or so-called social network sensor. The question then arises how to select a budgeted set of social network sensors to form the data stream for burst detection without compromising the detection performance. In this article, we present a general sensor selection solution for different burst detection approaches. We formulate this problem as a constraint satisfaction problem that has high computational complexity. To reduce the computational cost, we first reduce most of the constraints by making use of the fact that bursty cascades are rare among the whole population. We then transform the problem into an Linear Programming (LP) problem. Furthermore, we use the sub-gradient method instead of the standard simplex method or interior-point method to solve the LP problem, which makes it possible for our solution to scale up to large social networks. Evaluating our solution on millions of real information cascades, we demonstrate both the effectiveness and efficiency of our approach.