上海交大安泰经管学院数据与商务智能系王凯副教授、林学民教授和信息、技术与创新系刘佳璐副教授与合作者在国际顶尖期刊INFORMS Journal on Computing发表论文
文章导读
2025年，一项突破性算法正悄然改变大规模网络治理的格局。上海交大王凯、林学民、刘佳璐等学者在国际顶刊发表研究，揭秘如何高效遏制谣言与疫情的传播。面对传统方法计算成本高、响应慢的难题，团队提出AdvancedGreedy算法，首次结合支配树结构实现高效图采样，在线性阈值模型下逼近最优解；另设计GreedyReplace启发式算法应对独立级联场景。实验证明，新方法在真实网络中显著提升阻断效率，为社交网络与公共卫生领域的应急决策提供了强有力的计算工具。
— 内容由好学术AI分析文章内容生成，仅供参考。
上海交大安泰经管学院数据与商务智能系王凯副教授、林学民教授和信息、技术与创新系刘佳璐副教授与合作者谢嘉东、张帆、张文杰于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会士。
研究领域：大数据管理与数据挖掘。
刘佳璐，上海交通大学安泰经济与管理学院副教授。
研究领域：科技与社会交互中产生的管理问题。
作者： 学科建设与科研办公室 供稿单位： 安泰经济与管理学院
© 版权声明
本文由分享者转载或发布，内容仅供学习和交流，版权归原文作者所有。如有侵权，请留言联系更正或删除。
相关文章
这算法听起来挺牛的。