Loading...
Please wait, while we are loading the content...
Similar Documents
Limiting the Spread of Misinformation in Social Networks
| Content Provider | CiteSeerX |
|---|---|
| Author | Budak, Ceren Abbadi, Amr El Agrawal, Divyakant |
| Abstract | In this work, we study the notion of competing campaigns in a social network. By modeling the spread of influence in the presence of competing campaigns, we provide necessary tools for applications such as emergency response where the goal is to limit the spread of misinformation. We study the problem of influence limitation where a “bad ” campaign starts propagating from a certain node in the network and use the notion of limiting campaigns to counteract the effect of misinformation. The problem can be summarized as identifying a subset of individuals that need to be convinced to adopt the competing (or “good”) campaign so as to minimize the number of people that adopt the “bad ” campaign at the end of both propagation processes. We show that this optimization problem is NP-hard and provide approximation guarantees for a greedy solution for various definitions of this problem by proving that they are submodular. Although the greedy algorithm is a polynomial time algorithm, for today’s large scale social networks even this solution is computationally very expensive. Therefore, we study the performance of the degree centrality heuristic as well as other heuristics that have implications on our specific problem. The experiments on a number of close-knit regional networks obtained from the Facebook social network show that in most cases inexpensive heuristics do in fact compare well with the greedy approach. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Degree Centrality Heuristic Emergency Response Necessary Tool Specific Problem Facebook Social Network Show Greedy Algorithm Optimization Problem Certain Node Social Network Approximation Guarantee Case Inexpensive Heuristic Various Definition Influence Limitation Greedy Approach Close-knit Regional Network Polynomial Time Algorithm Large Scale Social Network Bad Campaign Greedy Solution |
| Content Type | Text |
