Name
Abstract | ||
|---|---|---|
Online Social Networks (OSNs) have recently emerged as an effective medium for information sharing. Unfortunately, it has been frequently observed that malicious rumors being spread over an OSN are not controllable, and this is not desirable. This paper proposes a new problem, namely the gamma - k rumor restriction problem, whose goal is, given a social network, to find a set S of nodes with k protectors (gamma * k protectors from the contaminated set, and (1 - gamma) * k protectors from the decontaminated set) to protect the network such that the number of decontaminated nodes is maximum. We show that the objective function of the gamma - k rumor restriction problem is submodular, and use this result to design a greedy approximation algorithm with performance ratio of 1 - 1/e for the problem under the linear threshold model and independent cascade model, respectively. To verify our algorithms, we conduct experiments on real word social networks including NetHEPT, WikiVote and Slashdot0811. The results show that our algorithm works efficiently and effectively. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/PCCC.2013.6742780 | 2013 IEEE 32ND INTERNATIONAL PERFORMANCE COMPUTING AND COMMUNICATIONS CONFERENCE (IPCCC) |
Keywords | Field | DocType |
Rumor containment, Real-world social networks, IC model, LT model | Social network,Algorithm design,Computer science,Rumor,Computer network,Approximation theory,Submodular set function,Linear programming,Threshold model,Information sharing | Conference |
ISSN | Citations | PageRank |
1097-2641 | 10 | 0.58 |
References | Authors | |
25 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Li Songsong | 1 | 24 | 3.76 |
| Zhu Yuqing | 2 | 467 | 37.26 |
| Deying Li | 3 | 1216 | 101.10 |
| Kim Donghyun | 4 | 458 | 41.00 |
| Huang Hejiao | 5 | 307 | 37.23 |