我院数据与商务智能系王凯副教授、林学民教授和信息、技术与创新系刘佳璐副教授与合作者谢嘉东、张帆、张文杰于2025年12月在国际顶尖期刊INFORMS Journal on Computing上发表学术论文“Influence Minimization via Blocking Strategies”，2025, 37(6): 1587-1604。 

      【论文摘要】

      题目：基于阻断策略的影响力最小化研究

      影响力最小化问题（Influence Minimization Problem）旨在给定图结构和种子节点集合的情况下，通过阻断有限数量的节点或边，使种子节点的影响力传播最小化。这是网络分析中一个关键但尚未被充分探索的领域，对于限制错误信息（如谣言）在社交网络中的传播以及控制流行病在接触网络中的扩散具有重要意义。鉴于该问题在独立级联（IC）和线性 阈值（LT）模型下的NP难特性，以往的研究多采用贪婪算法结合蒙特卡洛模拟来求解。然而，现有方法在处理大规模网络时计算成本过高，难以满足即时决策的需求。

      本研究提出了一种名为AdvancedGreedy的算法，该算法利用了一种结合支配树（Dominator Tree）结构的创新图采样技术。研究发现，AdvancedGreedy算法在LT模型下能够实现 (1-1/e-ε) 的近似比。针对IC模型，本研究进一步提出了一种基于识别候选阻断者之间关系的新型启发式算法GreedyReplace。在真实网络上的大量实验表明，本文提出的算法在效率上实现了显著提升，极大地提升了大规模网络治理的实用性。

      【作者介绍】

      王凯，上海交通大学安泰经济与管理学院副教授。

      研究领域：图数据管理与分析。

      林学民，上海交通大学安泰经济与管理学院讲席教授，欧洲科学院外籍院士和IEEE会士。

      研究领域：大数据管理与数据挖掘。

      刘佳璐，上海交通大学安泰经济与管理学院副教授。

      研究领域：科技与社会交互中产生的管理问题。