























The spread of rumors in online networks threatens public safety and results in economic losses. To overcome this problem, a lot of work studies the problem of rumor control which aims at limiting the spread of rumors. However, all previous work ignores the relationship between the influence block effect and counts of impressions on the user. In this paper, we study the problem of minimizing the spread of rumors when impression counts. Given a graph $G(V,E)$, a rumor set $R \in V$ and a budget $k$, it aims to find a protector set $P \in V \backslash R$ to minimize the spread of the rumor set $R$ under the budget $k$. Due to the impression counts, two following challenges of our problem need to be overcome: (1) our problem is NP-hard; (2) the influence block is non-submodular, which means a straightforward greedy approach is not applicable. Hence, we devise a branch-and-bound framework for this problem with a ($1-1/e-ε$) approximation ratio. To further improve the efficiency, we speed up our framework with a progressive upper bound estimation method, which achieves a ($1-1/e-ε- ρ$) approximation ratio. We conduct experiments on real-world datasets to verify the efficiency, effectiveness, and scalability of our methods.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。