General rumor blocking: an efficient random algorithm with martingale approach

DOI10.1007/978-3-030-04618-7_14MaRDI QIDQ6073044zbMATH OpenOpenAlexFDO

Authors Qizhi Fang, Xin Chen, Qingqin Nong, Zongchao Zhang, Yongchang Cao, Yan Feng, Tao Sun, Suning Gong, Du Ding-Zhu

Publication date 16 October 2023

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-04618-7_14

zbMATH Keywords

greedy approachmartingalerandom algorithmrumor blocking

Mathematics Subject Classification ID

Randomized algorithms (68W20) Social networks; opinion dynamics (91D30)

Review text

This paper studies general rumor blocking with an eye on an efficient random algorithm with martingale approach. The general rumor blocking problem is presented and a greedy algorithm is described which returns a \(1-e^{-1}\)-approximate solution. An efficient random algorithm R-GRB is proposed for general rumor blocking problem. The approximate ratio and time complexity are analyzed based on the tools of reverse methods and martingale's method. For the entire collection see [Zbl 1400.68037].

Recommendations

• General rumor blocking: an efficient random algorithm with martingale approach
• Blocking rumor by cut
• Centralized and decentralized rumor blocking problems
• Efficient algorithm for stochastic rumor blocking problem in social networks during safety accident period
• Simple, fast and deterministic gossip and rumor spreading

Cited in

(2)

• Online conflict resolution: algorithm design and analysis
• Efficient algorithm for stochastic rumor blocking problem in social networks during safety accident period

This page was built for publication: General rumor blocking: an efficient random algorithm with martingale approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6073044)