Maximizing rumor containment in social networks with constrained time
- Authors
- Fan, L.; Wu, W.; Zhai, X.; Xing, K.; Lee, W.; Du, D.-Z.
- Issue Date
- 2014
- Publisher
- Springer-Verlag Wien
- Keywords
- Influence diffusion; Personal interests; Rumor containment; Time deadline; Time delay
- Citation
- Social Network Analysis and Mining, v.4, no.1, pp.1 - 10
- Indexed
- SCOPUS
- Journal Title
- Social Network Analysis and Mining
- Volume
- 4
- Number
- 1
- Start Page
- 1
- End Page
- 10
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/100756
- DOI
- 10.1007/s13278-014-0214-4
- ISSN
- 1869-5450
- Abstract
- The spread of rumor or misinformation in social networks may cause bad effects among the public. Thus, it is necessary to find effective strategies to control the spread of rumor. Specifically, in our paper, we consider such a setting: initially, a subset of nodes is chosen as the set of protectors, and the influence of protector diffuses competitively with the diffusion of rumor. However, in real world, we generally have limited budget (limited number of protectors) and time to fight with rumor. Therefore, we study the problem of maximizing rumor containment within a fixed number of initial protectors and a given time deadline. Generalizing two seminal models in the field—the Independent Cascade (IC) model and the Linear Threshold (LT) model—we propose two new models of competitive influence diffusion in social networks with the following three factors: a time deadline for information diffusion, random time delay of information exchange and personal interests regarding the acceptance of information. Under these two models, we show that the optimization problems are NP-hard. Furthermore, we prove that the objective functions are submodular. As a result, the greedy algorithm is used as constant-factor approximation algorithms with performance guarantee $$1-\frac{1}{e}$$1-1e for the two optimization problems. © 2014, Springer-Verlag Wien.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - School of Cyber Security > Department of Information Security > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.