基于环形影响的有影响力节点识别

《Physica A: Statistical Mechanics and its Applications》：Identifying influential nodes based on circle influence

　　

摘要
识别有影响力节点是网络科学中的基本问题，在网络营销、应急响应和金融风险管理等领域有着广泛应用。在现有方法中，基于拓扑的方法因其高效性和实用适用性而备受关注。大多数方法从个体中心视角来刻画节点重要性，关注目标节点所施加影响的规模、其影响节点的重要性，或其对网络中其他节点的可达性。然而，这种个体中心视角可能无法充分考虑目标节点周围圈层所提供的影响力信息。为了解决这一局限性，我们提出了一族基于圈层影响力的有影响力节点识别方法。其核心思想是：除了个体影响力之外，还可以结合周围圈层的影响力来更好地表征节点的重要性。据此，我们通过同时考虑圈层成员的个体传播能力和其圈层影响力来对圈层影响力进行建模，并进一步开发了一个统一框架来量化每个节点的最终影响力。在11个真实世界网络上进行的广泛实验表明，所提出的混合圈层影响力度量在针对11个基线的整体性能上表现最优，在所有数据集-基线组合的平均相对改进为47.31%，在Kendall's τ上比表现最佳的基线方法高出5.31%。除了性能提升之外，本工作还为有影响力节点识别提供了一个统一的算法框架，并为从个体与其局部网络环境的交互作用角度理解节点重要性提供了一种新视角。

引言
随着网络科学的快速发展，越来越多的真实世界系统被建模为复杂网络[1]。这种抽象使得我们能够系统地分析网络结构[2]、[3]、传播动力学[4]、[5]、[6]和网络弹性[7]、[8]，从而揭示复杂系统背后的基本原理。在各种网络分析任务中，有影响力节点识别[9]是一个核心且具有挑战性的问题，具有广泛的实践意义，在流行病学控制[10]、[11]、科学影响力分析[12]、[13]、[14]、交通优化[15]、[16]以及生物网络分析[17]、[18]等方面均有应用。例如，在流行病学网络中，基于接触关系识别潜在的超级传播者有助于预防大规模爆发[19]、[20]、[21]；在引用网络中，识别有影响力的出版物有助于分析研究热点和演变趋势，从而为学术影响评估和学科发展提供参考[22]；在交通网络中，关键枢纽的识别有助于物流优化和拥堵风险预测[23]；在生物系统中，蛋白质-蛋白质相互作用网络的研究可以有助于发现疾病治疗的关键靶点[24]。

现有识别有影响力节点的方法可分为四类，包括基于拓扑的方法[25]、[26]、基于渗流的方法[27]、[28]、基于信息论的方法[29]、[30]以及基于机器学习的方法[31]、[32]、[33]、[34]、[35]。其中，基于拓扑的方法因其可解释性、低计算复杂度和有效性能而受到最多的关注和实际使用。基于拓扑的方法可进一步分为四类：基于邻域的方法[36]、[37]、基于路径的方法[25]、[38]、[39]、[40]、基于引力模型的方法[41]、[42]、[43]、[44]以及迭代优化方法[45]、[46]、[47]、[48]。基于邻域的方法假设节点的重要性与其影响周围邻居的能力高度相关，通常关注节点对邻居的覆盖度和其在网络中的位置[49]、[50]、[51]、[52]、[53]。代表性方法包括度中心性、k-shell中心性[49]和SocialCapital[36]。基于路径的方法强调节点对其他节点在网络的可达性和传播速度，常见指标包括接近中心性[38]、Katz中心性[54]和介数中心性[55]。基于引力模型的方法将牛顿万有引力定律引入有影响力节点识别中，认为节点的影响力不仅取决于直接邻居，还取决于间接邻居[41]、[42]。通过适当定义节点的"质量"和节点间的"距离"，这些方法可以更准确地量化影响力。迭代优化方法认为节点的影响力不仅取决于邻居的数量，还取决于这些邻居的影响力，典型算法包括PageRank[45]、HITS[46]和LeaderRank[47]。最近，基于学习的方法，特别是基于图神经网络的方法，也被探索用于有影响力节点识别。代表性方法采用图卷积网络或图注意力机制来学习节点表示，并从网络结构中发现有影响力节点[33]、[34]、[35]。这些方法为手工设计的拓扑指标提供了一种数据驱动的替代方案，但通常需要标注数据和模型训练。其训练和测试协议在不同研究中也有所不同，包括在合成网络上训练后迁移到真实网络，以及在真实网络上构建训练-测试划分，这对统一评估和跨网络泛化提出了挑战。

从上述综述可以看出，大多数现有的基于拓扑的方法主要从个体节点视角评估节点重要性，关注节点能直接影响的邻居数量、这些邻居的影响力或节点在网络中的可达性等要素。尽管邻域信息已被广泛用于有影响力节点识别，但它通常作为评估目标节点本身的证据来纳入。相比之下，围绕节点的局部影响环境很少被明确作为独立的评价对象。这一区别促使我们从"利用邻域评估节点"转向明确评估局部影响环境本身，并考察圈层级信息如何贡献于节点重要性。如图1所示，如果我们仅考虑节点对直接邻居的影响，节点u似乎比节点v1具有更小的直接影响。然而，节点u的邻居（例如v1、v2、v3）各自具有相对较高的影响力。这些邻居的聚合影响力高于v1的邻居。这表明，尽管u看似具有较弱的直接影响，但其局部圈层表现出更大的聚合传播潜力，这为评估u的重要性提供了额外信息。这一例子凸显了仅基于节点对邻居的直接影响来评估节点不足以捕捉其在网络中的真实重要性。更一般地说，个体的影响力不仅与个体特征有关，还与个体所嵌入的影响力环境有关。

受上述观察的启发，我们引入了"圈层影响力"的概念，将节点的局部影响环境（称为其"圈层"）作为明确的评价对象，并表征其整体传播潜力。具体来说，节点重要性不仅可以从其个体结构或传播能力来评估，还可以从其周围圈层所包含的影响力信息来评估。与传统以个体为中心的影响力指标（关注节点单方面影响他人的能力）不同，圈层影响力明确评估节点的圈层，并进一步整合互补的圈层级信息以进行有影响力节点识别。据此，FOCI、SOCI和HCI被设计为从不同角度来表征圈层影响力，而非简单地扩展邻域范围。FOCI从成员的个体影响力评估圈层的传播潜力；SOCI进一步从与这些成员相关的圈层影响力进行评估。HCI整合这两类信息，而不引入额外的邻域聚合层。因此，邻域聚合是所提出圈层影响力视角的计算实现，而非逐步扩展邻域深度的动机。这也将圈层影响力与PageRank[45]和HITS[46]等递归中心性方法区分开来，后者通过整个网络上的递归依赖关系来评估节点重要性，以及主要使用局部结构信息来评估目标节点本身的传统基于邻域的指标。半局部和高阶邻域方法同样通过引入更广泛的或多阶邻域信息来增强目标节点评估，而此处使用的有限阶聚合则是为了评估局部影响环境，而非逐步扩大邻域深度。通过明确引入局部影响环境作为额外评价对象，所提出的框架将有影响力节点识别从节点级评估扩展到节点-圈层联合影响力评估。在11个真实世界数据集上的实验表明：仅考虑局部圈层中邻居节点的个体传播能力的一阶圈层影响力表现最差；考虑邻居节点的圈层影响力的二阶圈层影响力取得次优性能；而同时整合两者的混合圈层影响力取得了最佳性能，并优于11个基线方法。

章节摘要

问题描述
在复杂网络中，有影响力节点是指对其他节点产生显著影响的节点，通常以其能影响的节点数量来衡量。为估计节点的真实影响力，通常使用传播动力学模型，其中SIR模型[56]是最广泛采用的之一。在此，我们也使用SIR模型在简单网络（即无权无向网络）中衡量节点影响力。SIR模拟被广泛用于评估有影响力节点识别。

方法
本节介绍了所提出的圈层影响力框架。我们首先定义FOCI和SOCI从两个互补视角来表征圈层影响力，然后将它们结合构造HCI。我们进一步分析了HCI的邻边精炼能力和输入扰动稳定性。

实验
本节我们在11个真实世界网络上测试了所提方法的性能。我们使用以下研究问题（RQs）来指导实验。

RQ1：我们的方法是否优于基线方法？
RQ2：圈层级信息是否提供了超越基础节点级中心性的额外信息？
RQ3：方法的性能对SIR模型参数的敏感度如何？
RQ4：圈层在个体级效应之外如何贡献于节点重要性？
RQ5：方法的鲁棒性和计算性能如何？

工程应用
所提出的圈层影响力框架在需要识别有影响力节点以支持精准干预和资源分配的各种网络化系统中具有潜在应用。以恶意软件遏制和流行病控制为例，HCI生成的节点排名可以为优先配置有限的干预资源提供有用指导。在企业计算机网络中，计算机、服务器和其他联网设备可以表示为节点，而通信……

结论与讨论
本文研究了简单网络中有影响力节点识别问题，并引入了一种新视角，称为圈层影响力，它明确将节点周围的局部影响环境作为独立的评价对象。作为初步探索，我们将目标节点的局部圈层定义为其一跳邻居集（即直接邻居）。基于这一定义，我们表征了圈层对节点的支撑和放大效应。

CRediT作者贡献声明
武蓝鑫：论文——审阅与编辑、可视化、软件、方法论。李航：论文——审阅与编辑、验证、形式分析。夏维清：论文——审阅与编辑、验证、软件。张寅然：可视化、软件。杜亚君：论文——审阅与编辑、资金获取、形式分析。李仙永：论文——审阅与编辑、形式分析。李彦丽：论文——初稿撰写、方法论、资金获取、形式分析、概念构思。

未引用参考文献
[66]、[67]

利益冲突声明
作者声明，他们不存在已知的可能影响本文所报告工作的财务利益或个人关系。

致谢
本工作部分由中国国家自然科学基金（批准号62507039和62576287）、四川省科技计划（批准号2025ZNSFSC0506）以及宜宾市科技计划（编号2023SF004）资助。

武蓝鑫 | 李航 | 夏维清 | 张寅然 | 杜亚君 | 李仙永 | 李彦丽