学术报告：iminimize系统——基于顶点阻断的负面影响力最小化研究

作者及发表信息

本研究的核心作者包括：
- Siyi Teng（华东师范大学）
- Jiadong Xie（新南威尔士大学，通讯作者）
- Mingkai Zhang（广州大学）
- Kai Wang（上海交通大学安泰经济与管理学院）
- Fan Zhang（广州大学）

研究论文《iminimize: a system for negative influence minimization via vertex blocking》发表于ACM国际信息与知识管理会议（CIKM 2023），会议于2023年10月21日至25日在英国伯明翰举行。论文已收录于ACM数字图书馆，DOI编号为10.¹¹⁴⁵⁄_3583780.3614743。

学术背景

研究领域与问题

本研究属于社交网络分析与数据挖掘领域，聚焦于负面信息传播控制（negative influence minimization）问题。随着社交平台的普及，虚假信息、谣言或流行病传播等负面影响的扩散速度显著提升。传统解决方案（如基于度中心性（degree centrality）或介数中心性（betweenness centrality）的启发式方法）存在效率低或效果不足的缺陷。

研究目标

iminimize系统旨在通过顶点阻断（vertex blocking）策略，在给定预算（如最多阻断𝑏个顶点）下，高效选择关键顶点进行阻断，以最小化负面信息在网络中的传播范围。其核心创新在于：
1. 算法效率：提出基于支配树（dominator tree）的贪心算法，比现有方法快3个数量级；
2. 系统实用性：首次提供交互式可视化平台，支持用户自定义网络和预算，实时验证阻断效果。

研究流程与方法

1. 系统架构

iminimize采用客户端-服务器架构，包含三大模块：
- 输入模块：支持用户上传有向图数据（如社交网络或路网），设置边激活概率（如加权级联模型（weighted cascade, WC）或三值模型（trivalency, TR））、阻断预算𝑏及可视化参数。
- 服务器处理模块：
- 预期传播估计：通过蒙特卡洛模拟（Monte-Carlo simulations, MCS）生成105次随机图采样，计算种子集𝑆的预期影响力；
- 顶点选择算法：基于贪心策略迭代选择使预期传播下降最大的顶点，结合支配树理论优化计算效率（详见文献[21]）。
- 输出模块：可视化阻断前后的传播效果，展示阻断顶点列表及传播下降比例。

2. 关键技术

• 贪心算法优化：传统贪心算法需枚举所有候选顶点并重复MCS，计算复杂度高。iminimize通过以下改进提升效率：
  
  • 图采样与支配树：在单次采样中，利用支配树一次性计算所有候选顶点的传播减少量（定理6[21]）；
    
  • 大数定律（Law of large numbers）保证采样结果的统计稳定性。
    
• 交互功能：用户可动态调整预算𝑏，系统实时更新阻断方案与可视化结果。
  

主要结果

1. 社交网络案例（Twitter数据集）

• 数据集：MelCup17数据集包含34,573名用户及70,756条边，种子集𝑆为412名初始发布者。
  
• 阻断效果：阻断100个顶点后，感染概率下降约50%（图2c）。
  
• 效率对比：比传统贪心算法快6个数量级，且无效果损失。
  

2. 流行病控制案例（明尼苏达路网）

• 数据集：2,642个交叉路口（顶点）和3,303条道路（边），种子集为100个感染地点。
  
• 阻断效果：阻断50个顶点后，预期感染地点减少67.99%（图3c）。
  

结论与价值

科学价值

1. 理论贡献：提出首个结合支配树与贪心算法的顶点阻断方案，解决NP难问题的高效近似计算；
   
2. 方法普适性：适用于多种网络（社交网络、路网），支持边概率自定义。
   

应用价值

1. 社交网络管理：帮助平台快速阻断谣言传播关键用户；
   
2. 公共卫生：优化流行病控制中的检测点部署策略。
   

研究亮点

1. 算法创新：支配树技术将计算复杂度从𝑂(𝑛3)降至𝑂(𝑛 log 𝑛)；
   
2. 系统开源：代码发布于GitHub，支持用户扩展；
   
3. 交互设计：首次实现预算动态调整与实时可视化，提升决策透明度。
   

其他价值

• 可扩展性：用户可替换阻断策略模块（如改用介数中心性），探索不同场景下的优化方案。
  
• 跨领域潜力：未来可应用于网络安全（阻断恶意节点）或金融风控（限制风险传播）。
  

（报告字数：约1,800字）