摘 要：复杂网络中的关键节点识别是研究复杂网络结构、功能、性质的重要基础，在市场营销、谣言控制、交通规划等不同领域都有很强的应用价值。节点的关键性等价于节点的影响力，因此，关键节点识别问题可看作节点影响力评估问题。文章提出了一种基于局部传播路径的复杂网络关键节点识别方法，该方法仅需计算目标节点两步之内的拓扑结构，还综合考虑了传播概率对节点影响力评估的影响。与常见的度中心性、介数中心性、接近中心性、Kshell 中心性相比，该算法识别结果更准确，在不同传播概率下表现更稳定。
关键词：复杂网络；关键节点识别；影响力；传播路径
DOI:10.19850/j.cnki.2096-4706.2023.02.002
基金项目：天津市大学生创新创业训练计划项目（202210069069）；天津市教委科研计划项目（2021SK141）
中图分类号：TP399；O157.5 文献标识码：A 文章编号：2096-4706（2023）02-0008-04
A Method for Identifying Key Nodes in Complex Networks Based on Local Propagation Paths
HE Xinyi, MA Qian, YANG Dandan, ZHANG Maoyu
(Tianjin University of Commerce, Tianjin 300134, China)
Abstract: The identification of key nodes in complex networks is an important basis for studying the structure, function and nature of complex networks. It has strong application value in marketing, rumor control, traffic planning and other fields. The criticality of nodes is equivalent to the influence of nodes. Therefore, the problem of identifying key nodes can be regarded as the problem of evaluating the influence of nodes. This paper proposes a key node identification method for complex networks based on local propagation paths. This method only needs to calculate the topology structure of the target node in two steps, and it also comprehensively considers the effect of propagation probability on the evaluation of node influence. Compared with the common methods such as degree centrality, betweenness centrality, closeness centrality and kshell centrality, this method is more accurate and stable under different propagation probabilities.
Keywords: complex network; key node identification; influence; propagation path
参考文献：
[1] 王敏 . 复杂网络中关键节点挖掘与社区发现算法研究 [D].成都：电子科技大学，2020.
[2] 王安 . 基于复杂网络结构特征的节点重要性评估方法研究[D]. 北京：中国人民公安大学，2020.
[3] 王晋，王伯礼 . 基于复杂网络的城市群铁路网络节点重要度研究 [J]. 内蒙古公路与运输，2021（4）：52-57.
[4] 汪军，夏永跃，王运明，等 . 基于贪心介数的地铁 - 公交复合网络关键车站识别算法 [J]. 铁道标准设计，2022，66（7）：132-137.
[5] 朱大锐，王睿，程文姬，等 . 基于改进 PageRank 算法的输电网关键节点辨识方法研究 [J]. 电力系统保护与控制，2022，50（5）：86-93.
[6] 马茜 . 社会网络中的节点影响力度量和 k- 节点集的影响力最大化问题研究 [D]. 济南：山东大学，2017.
[7] 修志博 . 城市交通复杂网络节点重要度评估与级联失效研究 [D]. 长春：吉林大学，2020.
[8] 罗浩，闫光辉，张萌，等 . 融合多元信息的多关系社交网络节点重要性研究 [J]. 计算机研究与发展，2020，57（5）：954-970.
[9] 郭程远，陈鸿昶，王庚润，等 . 复杂网络节点重要性排序算法及应用综述 [J]. 信息工程大学学报，2021，22（3）：313-320+358.
[10] 谢丽霞，孙红红，杨宏宇，等 . 基于 K-shell 的复杂网络关键节点识别方法 [J].清华大学学报：自然科学版，2022，62（5）：849-861.
[11] 周庚 . 复杂网络节点中心性度量算法的研究及应用 [D].兰州：兰州理工大学，2020.
[12] 马媛媛，韩华 . 基于有效距离的复杂网络节点影响力度量方法 [J]. 复杂系统与复杂性科学，2022，19（1）：12-19.
[13] 蒋伟进，杨莹，罗田甜，等 . 基于全局—局部属性的复杂网络节点综合影响力评估算法 [J]. 物联网学报，2022，6（3）：133-145.
[14] 杨书新，梁文，朱凯丽 . 基于三级邻居的复杂网络节点影响力度量方法 [J]. 电子与信息学报，2020，42（5）：1140-1148.
[15] 邵玉，陈崚，刘维 . 独立级联模型下基于最大似然的负影响力源定位方法 [J]. 计算机科学，2022，49（2）：204-215.
作者简介：何欣怡（2001—），女，汉族，贵州六盘水人，本科在读，研究方向：数据挖掘；通讯作者：马茜（1989—），女，汉族，山东威海人，讲师，博士，研究方向：复杂网络。