Centralized and decentralized rumor blocking problems

Xin Chen, Qingqin Nong, Yanwei Feng, Yongchang Cao, Suning Gong, Qizhi Fang, Ker-I Ko

Research output: Contribution to journalArticle

4 Scopus citations


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 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.
Original languageEnglish
Pages (from-to)314-329
Number of pages16
JournalJournal of Combinatorial Optimization
Issue number1
StatePublished - Jul 2017

Fingerprint Dive into the research topics of 'Centralized and decentralized rumor blocking problems'. Together they form a unique fingerprint.

  • Cite this

    Chen, X., Nong, Q., Feng, Y., Cao, Y., Gong, S., Fang, Q., & Ko, K-I. (2017). Centralized and decentralized rumor blocking problems. Journal of Combinatorial Optimization, 34(1), 314-329. https://doi.org/10.1007/s10878-016-0067-z