一种基于局部传播路径的复杂网络关键节点识别方法

何欣怡 马茜 杨丹丹 张茂郁

一种基于局部传播路径的复杂网络关键节点识别方法

何欣怡，马茜，杨丹丹，张茂郁

（天津商业大学，天津  300134）

摘  要：复杂网络中的关键节点识别是研究复杂网络结构、功能、性质的重要基础，在市场营销、谣言控制、交通规划等不同领域都有很强的应用价值。节点的关键性等价于节点的影响力，因此，关键节点识别问题可看作节点影响力评估问题。文章提出了一种基于局部传播路径的复杂网络关键节点识别方法，该方法仅需计算目标节点两步之内的拓扑结构，还综合考虑了传播概率对节点影响力评估的影响。与常见的度中心性、介数中心性、接近中心性、Kshell中心性相比，该算法识别结果更准确，在不同传播概率下表现更稳定。

关键词：复杂网络；关键节点识别；影响力；传播路径

中图分类号：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

0  引  言

关键节点识别是复杂网络科学关注的热点和前沿性问题，具有重要的理论意义和应用价值。计算机病毒在网络中的扩散、某种言论观点在社交网络上的传播、传染病在人群中的蔓延、国家或城市之间的商品、资金、技术、人员、信息、车辆等的流动都可以看成是服从某种规律的网络传播行为。这其中，关键节点在观点、信息、车辆、人群等的传播或流动中扮演着重要的角色，往往起着推波助澜或逆转风向的关键作用，识别这些节点可以帮助促进传播或抑制蔓延[1，2]。同时，网络功能的正常运转也极大依赖着这些重要节点。研究表明，复杂网络中只要5%～10%的重要节点同时失效，整个网络就会无法正常运转[3]。识别这些关键节点并采取相应的保护措施，可以提高整个网络的稳健性和安全性。例如，识别交通网络中的重要枢纽，可以优化交通路线，方便乘客换乘，预防交通拥堵[4]。在电力网络中对关键节点进行优化，可以优化调度，预防大规模停电[5]。关键节点识别的一般思路是根据某一指标对节点的影响力进行量化，并根据量化值对节点影响力进行排序，关键节点识别问题可看作是节点影响力度量问题。节点影响力主要是通过信息、行为等的传播体现的。因此，节点的影响力可表示为节点的传播能力，复杂网络的关键节点识别问题可看作对节点的影响力或传播能力的评估问题[6]。

本文提出一种基于局部传播路径的复杂网络关键节点识别方法。本方法在独立级联模型的基础上，首先遍历搜索从目标节点出发2步之内能到达的所有节点，这些节点被称为受影响节点，然后搜索从目标节点出发到达受影响节点的所有路径。基于每条传播路径计算激活概率，并基于此计算目标节点对该受影响节点的所有2步之内的传播路径的激活概率之和。将目标节点对所有受影响节点的激活概率之和作为目标节点的影响力。本方法除了考虑目标节点的局部拓扑结构外，还综合考虑了传播概率对节点影响力评估的影响。通过在不同数据集上进行实验可以发现，该方法可以在不同的传播概率下更准确地识别关键节点。

1  相关工作

关键节点识别的前提是对节点的影响力进行评估，节点的影响力评估是指采用一定的标准对节点影响力的大小进行衡量、排序的问题。目前，复杂网络中的节点影响力评估方法大部分都是基于网络拓扑结构进行的。该类方法多数较为简单，实用性强，且网络拓扑结构数据，尤其是局部网络拓扑结构数据较易获得，因此受到大量的关注。在这类方法中，节点的影响力可理解为该节点在网络中与其他节点相连使其具有的重要性。因此，节点的影响力也常被称作节点的中心性（Centrality）[7-9]。

目前，较为常见的中心性方法包括基于局部网络结构的评价方法——度中心性（Degree Centrality）。此方法将目标节点的邻居数量作为影响力评估指标，简单直观，时间复杂度低，但在多数情况下，该方法衡量节点影响力的结果不够准确，因为其考虑的信息太过局限。基于全局网络结构的评估方法考慮了节点在整个网络结构中位置的重要性，包括介数中心性（Betweenness Centrality， BC）、接近中心性（Closeness Centrality， CC）等。介数中心性、接近中心性均假设节点影响力沿最短路径向全网传播。与基于局部网络结构的评价方法相比，基于全局网络结构的方法的评估结果更为准确。但因网络结构一般较为复杂，规模庞大，该类方法的时间复杂度很高。而且现实中的很多复杂网络的拓扑结构很难完整获取，因此，该类方法有较大的局限性。Kitsak等人[10]认为节点在网络中的位置决定了节点的影响力，越接近网络核心其影响力越大，并据此提出了k壳中心性（Kshell Centrality， KS）评价方法。该方法时间复杂度较低，但赋予很多节点相同的评估值，导致它们的影响力难以区分。此外，基于特征向量的评价方法也是评估节点影响力的重要方法，代表性的算法为谷歌的PageRank算法。基于特征向量的评价方法虽然可取得较好的评价效果，但它们只适用于有向、连通的网络，应用范围有限，且也面临着网络结构难以完整获取的问题。近年来，很多工作致力于研究不同指标的适用范围，及在动态网络中的影响力评估问题[11-14]。

2  本文涉及的基础知识

2.1  网络表示

一般用图的形式来表示复杂网络。一个具体的复杂网络可抽象为图G=（V， E），其中V表示网络中的节点集合，节点的数目用n表示，E表示边集合，边的数目用m表示。为方便处理和计算，图G可表示成邻接矩阵A={auv}∈{0，1}n×n的形式。auv=1则表示节点u和节点v之间有边直接相连，auv=0则表示无边直接相连。

2.2  独立级联模型

在关键节点识别的工作中一般会根据传播模型对目标节点的影响力传播过程进行模拟，即假设节点影响力的传播遵从某种模型。本文以独立级联模型（Independent Cascade Model， ICM）进行相关工作并进行实验。该模型是一种信息传播模型，原理简单，且使用广泛。根据ICM模型，网络中的节点只有两种状态——激活（active）和非激活（inactive）。某一时刻网络中的每一个节点须处于这两种状态中的一种[15]。用户收到某信息并会将该信息传播给予它直接相连的邻居节点，则称该节点处于激活状态；相反，用户没有收到该信息或者收到该信息但并不会传播给予它相连的邻居节点，则称该节点处于未激活状态。ICM在离散时间点t点的动态传播过程如下：

（1）在t=0时，网络中大部分节点处于非激活状态，只有少量节点处于激活状态，这些处于激活状态的节点被称为种子节点。种子节点一般为提前指定的。

（2）在t≥1的任何时刻，每一个在t-1时刻被激活的节点u都有且仅有一次机会去尝试激活它处于非激活状态的所有邻居节点v，激活成功的概率为puv。

（3）当多个节点u1， u2， u3尝试激活它们共同的处于未激活状态的邻居节点v时，它们尝试激活的顺序是随机的，且尝试激活的行为是互相独立不受影响的。

（4）以上过程不断重复，当网络中不再有新的节点被激活时，本次传播终止。此时，网络中处于激活状态的节点的数量就是本次传播中种子节点的影响力。

由于每次根据ICM模型进行模拟产生的传播结果可能不同，因此在实际应用中通常要进行1 000次以上的大量模拟来降低不确定性。一般取多次模拟出的处于激活状态的节点数目的平均值作为初始种子节点的最终影响力。在关键节点影响力识别问题中，通常依次把每一个节点作为种子节点，把根据ICM模型进行大量模拟得出的结果作为其真实影响力值。

2.3  评价指标

关键节点识别问题等价于节点影响力评估问题。目前评价各种影响力评估方法好坏的主要思路是：按照某种评估方法计算网络中每一个节点的影响力评估值，将所有节点按照评估值大小降序排列。同时依次将网络中的每一个节点作为种子节点根据传播模型进行多次模拟求平均，这个值被看作是节点的真实影响力值，将所有节点的真实影响力值降序排列。通过计算这两个序列的一致性来评价该评估方法的优劣，这两个序列越一致，则说明该方法越有效。Kendall's Tau（τ）系数常被用来衡量上述两个排序列表的一致性，该系数的相关定义如下：

考虑两个序列x和y。对任意一对观测值（xi， yi）和（xj， yj），计算（xi-xj）（ yi-yj），如果大于0则称这对观测值是一致的，如果小于0则称这对观测值是不一致的；如果等于0则称这对观测值既不是一致的也不是不一致的。具体的计算公式为：

（1）

Nc和Nd分别表示一致的和不一致的观测对数量。τ值越接近1，则两个序列越一致，说明该评估方法准确性越高。

2.4  常用评估方法

度中心性（Degree Centrality， DC）。指与该节点直接相连的邻居节点的个数。度中心性属于基于局部拓扑结构的方法，计算非常简单，用来分析节点的直接影响力。

介数中心性（Betweenness Centrality， BC）。指网络中通过该节点的最短路径的数目与所有节点对之间最短路径数目的比值，属于全局影响力方法，计算复杂度较高。

接近中心性（Closeness Centraity， CC）。指的是目标节点到网络中所有其他节点的最短距离和，属于全局影响力方法，计算复杂度高，但评估效果较好。

中心性Kshell中心性（Kshell Centrality， KS）。具体计算方法如下：首先将网络中所有DC=1的节点及与它们相连的边去掉，这些节点的KS值为1，重复这个过程直到网络中没有度值为1的节点存在；然后采用同样的方式去掉网络中度值为2的节点及与它们相连的边，这些节点的KS值为2。重复上述过程直到网络中的所有节点均被移除，此时，网络中的每个节点都有一个KS值。

3  基于局部传播路径的关键节点识别方法

DC只统计目标节点的邻居数目，考虑的拓扑结构过少导致其效果不好。而BC、CC评估效果有改善但需要在整个网络上进行最短路径的计算，尽管有很多优化算法，但在大规模网络中计算复杂度依然很高，且完整的网络结构难以获取。KS方法计算复杂度介于DC和BC、CC之间，但对节点影响力的区分度不好，即很多节点的KS值相同。基于此，本文提出了一种基于局部拓扑结构和传播路径的节点影响力评估方法——局部传播路径法（Local Propagation Paths， LPP）。该方法将目标节点对两步之内能到达的所有节点的所有两步之内的传播路径的激活概率之和作为目标节点的影响力，因为仅考虑了两步之内的节点，所以计算复杂度不高；又因为考虑的范围比DC要大，且包含传播概率等信息，评估会更加准确。该方法的具体计算方法如下：

对于网络中的每一个节点v∈V，计算节点v对两步之内能到达的所有节点w的影响力之和，计算方法如下：

（2）

其中，PATHvw={path1， path2， …， pathk， …， pathL}，PATHvw表示节点v到节点w所有路径（共有L条）的集合，pathk表示节点v到节点w的第k条具体路径：

（3）

其中， 指节点Vi和节点Vi+1之间的传播概率。因为LPP只考虑了目标节点对两步之内节点的影响力，所以1≤n≤2。

图1展示了利用LPP评估方法识别关键节点的流程。对网络中的每一个节点，根据式（2）、式（3）计算节点的LPP值。然后将所有节点按LPP值由大到小的顺序排序，得到序列R。在序列R中，位置越靠前代表影响力越大，然后根据需要选择前K个节点作为关键节点。

4  实验结果

为了评估LPP评估方法的表现，本文在四个真实复杂网络上进行了实验，分别为空手道俱乐部网络Karate、爵士音乐家网络Jazz、邮件往来网络Email、MSN博客空间博主之间的交流关系网Blog。这四个数据集均为网络公开数据集，网络基本情况如表1所示，其中，n表示网络节点数量，m表示网络边的数量（四个网络均为无向网络），k表示网络节点平均度。实验的硬件环境为：3.2 GHz的Intel（R）Core（TM）i5-3470 CPU，3.89 GB的内存。软件环境为MATLAB R2013a。

网络节点的真实影响力采用ICM模型模拟获得，模型中的传播概率p取0.01～0.1之间。对每一个传播概率，依次将每个节点作为初始激活的种子节点进行模拟传播，传播终止时网络中处于激活状态的节点的数量作为该种子节点的影响力。为了结果准确，本文对每个节点模拟10 000次取平均值作为该节点的真实影响力。将节点按其模拟出的真实影响力由大到小的顺序排列，得到真实影响力排序序列。本文将LPP的评估效果与DC、BC、CC、KS对比。对每一种方法，计算网络中所有节点在该方法下的评估值，按评估值由高到低的顺序排序得到该方法的排序序列。然后计算真实影响力序列与该方法的排序序列的一致性τ。实验结果如图2所示，横轴代表传播概率p，纵轴代表肯达尔系数τ。τ值越大，表明该方法准确性越高。

如图2所示，在这四个数据集中，在绝大多数传播概率下，LPP均能取得最大的τ值，说明LPP在大多数传播概率下评估效果最好。在Jazz网络中，当传播概率较大时LPP表现稍逊于DC，但差距并不明显。从图2中还可以看出，DC、KS、BC等的评估效果随传播概率的变化而产生较大波动，例如在Email和Blog数据集中，DC、BC等的评估效果随传播概率增大而明显变差。LPP也有波动但幅度较小，说明该方法较为健壮。总体看来，BC和KS效果最差，和它们为很多节点赋予相同的评估值导致这些节点的影响力无法区分有很大关系。

除了比较各评估方法的评估效果外，本文还比较了各方法的运行时间。因Karate和Jazz网络规模小，运行时间差距不明显，本文只比较了各方法在Email和Blog中的运行时间，结果如表2所示。基于网络局部结构的评估方法DC、LPP的运行时间比BC、CC等基于全局网络结构的方法的运行时间短。在网络规模较大时DC、LPP的优势将更明显。

5  结  论

复杂网络中的关键节点识别问题等价于节点影响力评估问题。本文分析了常见节点影响力评估方法DC、CC、KS等存在的问题，提出了一种基于局部传播路径的度量方法LPP。该方法结合了DC、CC的优点，基于局部拓扑结构进行计算使其能在大规模网络上运行，考虑了两步之内的节点的个数及它们之间的传播概率，使得结果更加准确。在四个真实复杂网络上的实验证明LPP方法在准确性、健壮性、运行时间方面均有优势。

在未来的工作中，本文将尝试在评估方法中加入更多的现实信息，例如考虑网络的异质性、社区结构等因素，使得节点影響力评估结果更加准确、贴近现实。

參考文献：

[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—），女，汉族，山东威海人，讲师，博士，研究方向：复杂网络。

收稿日期：2022-09-12

基金项目：天津市大学生创新创业训练计划项目（202210069069）；天津市教委科研计划项目（2021SK141）