Abstract
This paper consists of two parts. In the first part, we study a centralized rumor blocking problem with a novel social objective function different from those in the literature. We will show that this objective function is non-decreasing and submodular and hence corresponding rumor blocking problem has a greedy approximation with objective function value at least \(1-1/e\) of the optimal. In the second part, we study a decentralized rumor blocking problem with two selfish protectors, which falls into a 2-player non-cooperate game model. We will show that this game is a basic valid utility system and hence the social utility of any Nash equilibrium in the game is at least a half of the optimal social utility.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Budak C, Agrawal C, El Abbadi A (2011) Limiting the spread of misinformation in social networks. In: Proceedings of the 20th international conference on World wide web. ACM, pp. 665–674
Chen W, Lu W, Zhang N (2012) Time-critical influence maximization in social networks with time-delayed diffusion process. arXiv:1204.3074
Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 1029–1038
Fan L, Lu Z, Wu W, Thuraisingham B, Ma H, Bi Y (2013) Least cost rumor blocking in social networks. In: Proceedings IEEE 33rd international conference on distributed computing systems (ICDCS), pp 540–549
Fan L, Wu W, Xing K et al (2016) Precautionary rumor containment via trustworthy people in social networks. Discret Math Algorithm Appl 8(01):1650004
Fan L, Wu W, Zhai X et al (2014) Maximizing rumor containment in social networks with constrained time. Soc Netw Anal Min 4(1):1–10
He X, Song G, Chen W et al (2012) Influence blocking maximization in social networks under the competitive linear threshold model. In: SDM, pp 463–474
Kempe D, Kleinberg J, Tardos É (2005) Influential nodes in a diffusion model for social networks. International colloquium on automata, languages, and programming. Springer, Berlin
Kempe D, Kleinberg J (2003) É Tardos. Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 137–146
Kotnis B, Kuri J (2014) Cost effective rumor containment in social networks. arXiv:1403.6315
Li S, Zhu Y, Li D, Kim D, Huang H (2013) Rumor restriction in online social networks. In: Proceedings 2013 IEEE 32nd international performance computing and communications conference (IPCCC). pp 1–10
Nemhauser LG, Wolsey AL, Fisher LM (1978) An analysis of approximations for maximizing submodular set functional. Math Program 14(1):265–294
Vetta A (2002) Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In: Proceedings 43rd annual IEEE symposium on foundations of computer science. pp 416–425
Acknowledgments
This research was supported in part by the National Natural Science Foundation of China under grant numbers 11201439 and 11271341. This work was also supported in part by the Fundamental Research Funds for the Central Universities under grant number 201513013.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chen, X., Nong, Q., Feng, Y. et al. Centralized and decentralized rumor blocking problems. J Comb Optim 34, 314–329 (2017). https://doi.org/10.1007/s10878-016-0067-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-016-0067-z