Information cascade in online social networks can be rather negative, e.g., the spread of rumors may trigger panic. To limit the influence of misinformation in an effective and efficient manner, the influence minimization (IMIN) problem is studied in the literature: given a graph G and a seed set S, blocking at most b vertices such that the influence spread of the seed set is minimized. In this paper, we are the first to prove the IMIN problem is NP-hard and hard to approximate. Due to the hardness of the problem, existing works resort to greedy solutions and use Monte-Carlo Simulations to solve the problem. However, they are cost-prohibitive on large graphs since they have to enumerate all the candidate blockers and compute the decrease of expected spread when blocking each of them. To improve the efficiency, we propose the AdvancedGreedy algorithm (AG) based on a new graph sampling technique that applies the dominator tree structure, which can compute the decrease of the expected spread of all candidate blockers at once. Besides, we further propose the GreedyReplace algorithm (GR) by considering the relationships among candidate blockers. Extensive experiments on 8 real-life graphs demonstrate that our AG and GR algorithms are significantly faster than the state-of-the-art by up to 6 orders of magnitude, and GR can achieve better effectiveness with its time cost close to AG.
翻译:在线社交网络的信息串联可能是相当消极的,例如,谣言的传播可能会引发恐慌。为了限制错误信息的影响,文献对影响最小化(IMIN)问题进行了研究:根据图表G和种子S,在最大 b 的顶点上封住种子组的影响力最小化。在本文中,我们首先证明IMIN问题是硬的,很难估计的。由于问题的难度,现有工作诉诸贪婪的解决方案,并利用蒙特卡洛模拟来解决问题。然而,这些影响最小化(IMIN)问题在大图上却具有成本抑制作用,因为它们必须罗列所有候选阻塞者,并在堵住每个目标时计算预期扩散的减少量。为了提高效率,我们建议高级Greedy算法(AGA)基于一种新的图形取样技术,应用了调控树结构,它可以一次理解所有候选人阻塞者的预期扩散的减少量。此外,我们进一步建议GreedReplace算法(GR)在大型图表上具有成本比AGRA更接近的频率,通过考虑AGRA系统进行更接近的实验室,从而更接近AGRA的G-G-GIGG-GGAR系统能够更接近地展示更接近地展示其实际的进度。</s>