Publication Type

Journal Article

Version

acceptedVersion

Publication Date

4-2018

Abstract

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.

Keywords

Linear programming, Social network sensors, Sub-gradient method

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

Publication

ACM Transactions on Knowledge Discovery from Data

Volume

12

Issue

4

First Page

40:1

Last Page

24

ISSN

1556-4681

Identifier

10.1145/3178048

Publisher

ACM

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1145/3178048

Download

Share

COinS