Journal
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS
Volume 8, Issue 1, Pages -Publisher
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S179383091650004X
Keywords
Rumor; trust; social networks; social relation graph; Greedy Algorithm
Categories
Funding
- National Science Foundation of USA [CNS101630, CCF0829993]
- NRF by MSIP [2013R1A2A2A01014000]
- Basic Science Research Program by MEST [2011-0012216]
- IITP grant by MSIP [10041244]
- MSIP, Korea under ITRC support program [IITP-2015-R0992-15-1012]
- National Research Foundation of Korea [2013R1A2A2A01014000] Funding Source: Korea Institute of Science & Technology Information (KISTI), National Science & Technology Information Service (NTIS)
Ask authors/readers for more resources
In a social network, rumor containment is vital, as the diffusion of a rumor will bring terrible results. Precautionary measure can be used to control rumor propagation: Anticipating the spread of a rumor, one can (1) select a set of trustworthy people (TP) in the network, (2) alert the TP about the rumor, and (3) ask the TP to protect their neighbors by sending out alerts. In this paper, we study the problem of how to select the least number of TP, satisfying the requirement that the entire network is protected by the alerts that the TP send. We propose an asymmetric trust (AT) information propagation model. Under this model, we study the Least Number TP Selection (LNTS) problem, establish its NP-hardness and reformulate it as a minimum submodular cover problem. As a result, the Greedy Algorithm is a constant-factor approximation algorithm. Using real-world data, we evaluate the performance of the Greedy Algorithm, and compare it with other algorithms. Experimental results indicate that the Greedy Algorithm performs the best among its competitors.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available