NDLI: Least Cost Rumor Blocking in Social Networks

Content Provider	IEEE Xplore Digital Library
Author	Lidan Fan Zaixin Lu Weili Wu Thuraisingham, B. Huan Ma Yuanjun Bi
Copyright Year	2013
Description	Author affiliation: Dept. of Comput. Sci., Univ. of Texas at Dallas Dallas, Dallas, TX, USA (Lidan Fan; Zaixin Lu; Weili Wu; Thuraisingham, B.; Yuanjun Bi) \|\| Sch. of Inf., Renmin Univ. of China, Beijing, China (Huan Ma)
Abstract	In many real-world scenarios, social network serves as a platform for information diffusion, alongside with positive information (truth) dissemination, negative information (rumor) also spread among the public. To make the social network as a reliable medium, it is necessary to have strategies to control rumor diffusion. In this article, we address the Least Cost Rumor Blocking (LCRB) problem where rumors originate from a community Cr in the network and a notion of protectors are used to limit the bad influence of rumors. The problem can be summarized as identifying a minimal subset of individuals as initial protectors to minimize the number of people infected in neighbor communities of Cr at the end of both diffusion processes. Observing the community structure property, we pay attention to a kind of vertex set, called bridge end set, in which each node has at least one direct in-neighbor in Cr and is reachable from rumors. Under the OOAO model, we study LCRB-P problem, in which α (0 <; α <; 1) fraction of bridge ends are required to be protected. We prove that the objective function of this problem is submodular and a greedy algorithm is adopted to derive a (1-1/e)-approximation. Furthermore, we study LCRB-D problem over the DOAA model, in which all the bridge ends are required to be protected, we prove that there is no polynomial time o(ln n)-approximation for the LCRB-D problem unless P = NP, and propose a Set Cover Based Greedy (SCBG) algorithm which achieves a O(ln n)-approximation ratio. Finally, to evaluate the efficiency and effectiveness of our algorithm, we conduct extensive comparison simulations in three real-world datasets, and the results show that our algorithm outperforms other heuristics.
Starting Page	540
Ending Page	549
File Size	1085926
Page Count	10
File Format	PDF
ISBN	9780769550008
ISSN	10636927
DOI	10.1109/ICDCS.2013.34
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-07-08
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Communities Bridges Integrated circuit modeling Approximation algorithms Approximation methods Social network services Greedy algorithms social networks least cost rumor blocking opportunistic One-Activate-One model deterministic One-Activate-Many model approximation algorithm
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Maximizing the Spread of Positive Influence in Online Social Networks

Fast Compaction Algorithms for NoSQL Databases

Scalable and parallelizable processing of influence maximization for large-scale social networks?

Time Constrained Influence Maximization in Social Networks

On the Upper Bounds of Spread for Greedy Algorithms in Social Network Influence Maximization

Competitive Rumor Spread in Social Networks

An efficient algorithm for influence maximization under linear threshold model

Rumor source detection with multiple observations:fundamental limits and algorithms

Rumor Source Obfuscation on Irregular Trees

Least Cost Rumor Blocking in Social Networks

Similar Documents

Maximizing the Spread of Positive Influence in Online Social Networks

Fast Compaction Algorithms for NoSQL Databases

Scalable and parallelizable processing of influence maximization for large-scale social networks?

Time Constrained Influence Maximization in Social Networks

On the Upper Bounds of Spread for Greedy Algorithms in Social Network Influence Maximization

Competitive Rumor Spread in Social Networks

An efficient algorithm for influence maximization under linear threshold model

Rumor source detection with multiple observations:fundamental limits and algorithms

Rumor Source Obfuscation on Irregular Trees

Least Cost Rumor Blocking in Social Networks