中心博士生刘长安在国际顶级期刊TKDE发表研究成果

💡
近日，复旦大学复杂决策分析中心博士生刘长安作为第一作者在国际顶级学术期刊IEEE Transactions on Knowledge and Data Engineering（实时影响因子12.8）上发表题为“A Fast Algorithm for Moderating Critical Nodes via Edge Removal”（《通过移边调节关键节点的快速算法》）的学术论文。文章受到了中心的支持，由唐世平教授和章忠志教授联合指导。该文章的发表是中心在网络空间安全领域诸多探索中的又一重大突破。

A Fast Algorithm for Moderating Critical Nodes via Edge Removal (Changan Liu et al., 2023)

内容摘要

网络中的关键节点极易遭受恶意攻击，从而引发诸如谣言和病毒的传播等级联灾难。对于减轻此类恶意传播可能造成的损害，有效调节关键节点至关重要。但目前的调节方法的运算成本高昂，且忽略了能够衡量节点传播能力的基本指标——信息中心性。

在此背景下，论文提出了通过移边调节关键节点的快速算法，研究如何在保持网络畅通的同时，从网络中移除k条边，以最小化目标节点v的信息中心性。这一问题极具挑战性：这是一个NP完备的问题，且目标函数非超模。该论文提出三种近似贪婪算法（ExactSM、ApproxiSC和FastICM），其中使用了多种新技术，例如基于随机游走的舒尔补充近似和快速求和估计。其中一种算法的运行时间与边的数量呈近线性关系。

最后，为了补充理论分析，论文在拥有超过一百万个节点的合成网络和真实网络上进行了一系列综合实验。实验结果证明了在各种设置下该算法的效果和效率都极佳。

核心结果

图1：主要算法流程图

为了评估快速算法的性能，研究首先将本文提出的三种算法与OPTIMUM、RANDOM和SOLVER算法返回的边的质量进行了对比。研究选取了四个小型网络，包括两个具有50个节点的随机网络BA和WS，以及两个真实的网络Karate和Dolphins。由于网络规模较小，可以将该算法的结果与通过穷举搜索得到的最优解进行比较。评估过程中随机选取了10个目标节点；对于每一个网络，按照k从1到5的取值，每次为选定的目标节点运行每个算法10次，并计算目标节点的最终平均信息中心度。最终平均信息中心度的值越低，算法的性能越好。

图2：不同算法在四种网络中去除边后目标节点平均信息中心度：BA (a)、WS (b)、Karate (c) 和Dolphins (d)

结果（图2）显示，本文提出的三种算法在各数据集上的性能基本一致，结果与最优解几乎吻合；另一方面，RANDOM算法始终表现不佳，而SOLVER算法的表现与本文算法相似。

图3：不同算法在四种网络中去除边后目标节点的平均信息中心度：Bomb train(a)、Virgili(b)、ca-GrQc(c)和Erdös(d)

为了进一步验证算法有效性，研究选取了四个较大的真实网络进行测试。在此背景下，由于计算限制，通过穷举搜索最优解并不可行，于是研究将本文算法与RANDOM、BETWEENNESS、SPANNING和SOLVER四个算法的结果进行了比较。评估过程与上文类似，k范围为1到10；如图3所示，本文算法的良好效果依旧得到了验证。

刘长安，博士生，目前在复旦大学计算机科学技术学院攻读博士学位，系中心与计算机科学技术学院联合培养博士，研究领域包括网络科学、计算社会科学、图机器学习、图数据挖掘和社会网络分析。