宁 阳，武志峰，张 策

(天津职业技术师范大学 信息技术工程学院，天津 300222)

0 引 言

网络科学研究的是看起来互不相同的复杂网络之间共性和处理的普适方法。网络科学中研究的问题来源于各种实际网络，网络中的关键点识别是网络科学的重要研究内容之一。根据传播动力学的研究形成的理论和方法更好地认识不同网络上的传播行为之间的联系与区别。关键点识别的研究在不同的领域具有重要意义，例如在社会网络中找到最有影响力的人可以控制流言的传播，疾病传播过程中找到易感人群，对疾病进行有效的预防和控制，城市交通系统、电力系统中找到关键枢纽进行重点维护，降低经济损失风险等。有效地评价和衡量网络中节点的重要性，借助图论的概念和术语，将具体实际问题抽象为图，得到网络的拓扑性质，将多学科融合在一起作为研究方向，具有广泛的应用价值。

首先介绍提出不等概率叠加随机游走的相关工作，然后介绍不等概率叠加随机游走方法，构建不等概率转移矩阵，进行叠加。随机游走，通过相似和衡量节点重要性。通过对3个数据集的仿真实验，与度中心性、介数中心性、接近中心性和等概率叠加随机游走进行比较，并与SIR标准传播模型[1-2]进行Kendall tau距离[3-4]相关性分析，验证该方法的有效性。

1 相关工作

复杂网络中关键点识别的排序方法很多，文献[5]综述了关键点识别问题和方法，并对其进行分类，描述了最重要的进展和最新技术。近年来，学者通常在衡量节点的常用指标上进行改进。无向网络中几个常用衡量节点重要性的指标包括度值、介数、接近数、k-壳值和特征向量[6-10]。有向网络中经典的两个算法是Kleinberg提出的HITS算法[11]及Page和Brin提出的PageRank算法[12]。度中心性通过衡量一个节点的度，度越大节点越重要，即与节点在网络中所处的位置有关；介数中心性是经过某一节点整个网络中所有节点对之间的最短路径的数量反映节点重要性指标；接近中心性通过计算当前节点到网络中其他所有节点的距离在某种程度上反映节点重要性；k-壳值通过不断地在原始网络中去除度值为1，2，3…的节点及其连边，从而进行节点重要性识别的一种推广的度值指标；特征向量中心性既考虑了邻居节点的数量又考虑了邻居节点的重要性[1]。HITS算法通过刻画节点的权威性和枢纽性指标，衡量节点重要性。PageRank算法通过指向当前节点的数量和质量衡量节点重要性。文献[13]提出通过节点间的相互作用力构建随机游走模型中的概率转移矩阵，从物理学的角度考虑网络中边的实际意义。文献[14]考虑节点度及邻居节点拓扑重合度，获取节点两步内的邻居节点信息，通过计算节点之间相似度衡量节点重要性。文献[15]提出半局部中心性方法，解决大规模网络中时间消耗大的问题，仅考虑了节点两步转移到达节点的数量及节点度。文献[16]考虑节点二阶邻居节点，节点更有远见的转移到度(出度)大的节点，改进PageRank指标计算转移概率矩阵的平稳分布衡量节点重要性。文献[17]结合节点中心性和边的中心性指标在无向网络中重新定义转移概率矩阵衡量节点重要性。文献[18]提出了一种叠加游走相似和表征节点重要性的方法，考虑节点度、邻接节点的属性以及节点在网络中的位置，基于等概率的随机游走，但未考虑实际网络中游走的倾向性。

针对上述问题，以及受现有研究的启发，考虑节点之间的相似性[19]，进行有偏的随机游走，考虑两步到达节点的概率，提出一种基于不等概率叠加随机游走的重要节点识别算法。该方法将Node2 vec[20]中提到的随机游走方法2nd order随机游走与有叠加效应的局部随机游走指标[18-19]相结合，考虑节点之间的相似性，同时考虑不等概率随机游走。2nd order随机游走下一步的选择不再是等概率随机的，而是以不等概率进行随机游走。这里引入不等概率的随机游走，考虑有限次的游走步数、节点度的信息、节点之间的相似性作为不等概率随机游走的依据，进行无向网络中的关键节点识别。

2 不等概率叠加随机方法

文中提出的基于不等概率叠加随机游走关键点识别方法主要包括3个阶段，其中2.1节描述不等概率随机游走转移矩阵的构建，根据Jaccard指标[19,21]计算每个节点和网络中其他节点的相似性，考虑任意两个节点间有直接连边，但是无共同邻居的情况，采用文献[18]叠加随机游走通过相似和衡量节点重要度提到的节点度分之邻接矩阵值来计算。通过归一化处理，以此来构建概率转移矩阵。2.2节描述叠加效应的局部随机游走，根据有叠加效应的局部随机游走指标[19]，在局部随机游走指标(local random walk，LRW)[22]的基础上，将t步及其以前的结果加总得到叠加效应的局部随机游走相似性。这种方法可以增大邻近目标节点的点与目标节点相连的机会。2.3节基于相似和的叠加随机游走[18]，根据叠加效应的局部随机游走指标，累加各行相似度，从而根据对应节点的累加相似和进行重要节点识别。

2.1 构建不等概率随机游走转移矩阵

随机游走(random walk)指基于过去的表现，无法预测将来的发展步骤和方向，下一步的选择是随机的，一般来讲，节点通过存在边到达相邻节点的概率是相同的，到达非邻居节点的概率是0，即等概率的随机选择到达存在边的节点。

但实际中，从一个节点到其他邻居节点的概率不是均匀随机的，而是有偏的，所以文中提出基于不等概率进行随机游走，采用Jaccard指标衡量网络中节点之间的相似性，这里不仅考虑了存在边的邻居节点，同时也考虑了部分非邻居节点，即两步转移能够到达的节点。同时对于节点间存在直接连边，但是两个节点没有共同邻居，造成的Jaccard指标衡量相似性不足的问题，文中基于文献[18]考虑节点度的信息，作为相邻节点间转移概率。

将一个具体网络抽象为一个由点集V和边集E组成的图G=(V,E)。顶点数记为N=|V|，边数记为M=|E|。两种常见的表示图的基本结构是邻接矩阵(adjacency matrix)和邻接表(adjacency list)。文中将原始数据转化为邻接矩阵，图G的邻接矩阵A=(aij)N×N是一个N阶方阵，第i行第j列上的元素aij定义[1]如下：

无权无向图：

(1)

设置初始状态，将一个walker放置在无向无权图G任意节点i，构造随机游走模型，walker每一步根据节点之间相似性，以不等概率p到达邻居节点，同时，walker以p到达两步转移节点。游走的每一步方向都与已经发生的事件无关，walker经过的路线是一条马尔可夫链。

算法主要步骤如下：

(1)使用邻接矩阵表示图的基本结构，得到每个节点的度信息;

(2)使用Jaccard指标计算节点相似性，两节点直接相连，没有共同邻居利用节点度信息进行计算；Jaccard指标是在共同邻居的基础上考虑两端节点度的影响，提出的衡量节点相似性指标。

(2)

对于节点vx，邻居集合为Γ(x)，sxy为节点vx，vy的相似性。

(3)

(4)

2.2 基于叠加效应的局部随机游走

刘伟平和吕琳媛[22]考虑有限次的随机游走，提出一种基于网络局部随机游走的相似性指标(LRW),在LRW基础上，将t步及其以前的结果加总得到SRW的值，即：

(5)

设各个节点的初始资源分布为qx，基于t步随机游走的相似性为：

(6)

文中采用刘伟平和吕琳媛提出的一种与度分布一致性的初始资源，qx=kx/M，其中M作为网络的总边数，对每一对节点对都相同，计算过程忽略不计。πxy(t)表示walker从节点x经过t步游走到节点y的转移概率矩阵，一般的k步转移概率矩阵正好是一步转移概率矩阵的k次方，可以证明k步转移概率矩阵中各行元素之和都是1。

2.3 基于相似和的叠加随机游走

相似度矩阵中的值代表对应节点之间的相似度，每一行代表当前节点与其他所有节点的相似度，采用文献[18]提出的相似和概念衡量节点重要性。累加各行相似度，得到基于相似和的叠加随机游走相似性指标，将其用作网络中关键节点识别。

公式如下所示：

(7)

算法流程如图1所示。

图1 算法流程

3 实验结果与分析

3.1 SIR传播模型

文中使用SIR传播模型[1-2]得到的排序作为标准排序结果，在典型的传染病模型中，N个节点的状态可分为3类：

S:易染状态，初始条件下所有节点均为易染状态，该节点以β的概率被邻居节点感染。

I:感染状态，感染某种病毒作为传染源的节点，该个体以β概率感染其邻居节点。

R:移除状态，也称免疫状态或恢复状态，感染状态节点以β概率感染邻居易感节点后，以γ概率变为R移除状态，不再具有感染能力和易感特性。

3.2 Kendall tau距离

Kendall tau距离[3]计算两个排序列表之间成对分歧数量，即两个完成列表σ和τ，K(σ,τ)表示两个列表之间的差异性:

K(σ,τ)=

|{(i,j):iτ(j)}|

(8)

例：σ={1,2,3,4}，τ={1,3,2,4}，σ列表与τ列表二元组集合如图2所示。

二元组σ(1,2)(1,3)(1,4)(2,3)(2,4)(3,4)τ(1,3)(1,2)(1,4)(3,2)(3,4)(2,4)K000100K=1,K'=1-2*1/4*3=0.833

3.3 仿真实验

根据上述分析，为了验证文中提出的基于不等概率叠加随机游走关键点识别方法的有效性，对9/11恐怖袭击网络[24]、科研合作网[25]、USAir97数据集进行仿真实验，使用Python语言对算法进行实现，并与度中心性、介数中心性、接近中心性、等概率叠加随机游走方法进行比较；对3个数据集基于SIR模型计算标准排序结果，计算各中心性算法与SIR的Kendall tau距离的差异；分析算法的时间复杂度。表1给出了这3个网络的拓扑结构统计特征,其中n表示节点数，m表示边数，表示节点平均度，kmax表示节点最大度，表示网络节点间最短路径平均数，C表示聚类系数，用来评估节点聚集成团的集聚程度；R表示同配系数，用来反映邻接节点间的度相关性；H表示异质系数，衡量网络中节点度分布的异质性[1,26]。可以看出3个网络具有明显的小世界性，即高聚类系数和短的平均最短路径长度，同时USAir97拥有明显大度节点且具有高异质性，因此具有无标度网络的特征。

表1 网络拓扑结构的统计特征

9/11恐怖袭击是伊斯兰恐怖组织在美国发动的四次有组织的恐怖袭击，19名恐怖分子劫持四架客机，该无向网络结构共包含62个节点，148条边，每个节点代表一名恐怖分子，包含劫持客机的19名恐怖分子及其同谋者。节点之间的边代表恐怖分子之间的联系。网络结构如图3所示，其中4次劫机行动中所在飞机的恐怖分子编号为1-19(A11:1-2-3-4-5(飞行员)、UA175:5-6-7-8(飞行员)-9-10、AA77:11-12-13(飞行员)-14-15)、UA93:16-17-18(飞行员)-19[16]，利用文中提出的算法，得到如图4所示的节点重要度相似和排名，与介数中心性、度中心性、接近中心性指标、等概率叠加随机游走比较，结果如表2所示。

在四次恐怖劫持中，不等概率叠加随机游走识别同节点度、接近中心性指标、等概率叠加均识别出3名飞行员(5、8、13)，节点介数排序识别出1名，飞行员需要花费更多的资源培养，在劫持客机中是重要人员。上述算法在识别出的Top10节点中，度中心性可以识别出19名直接参与劫机的8名成员，其他方法次之；在Top15的节点中，度中心性、接近中心性和不等概率叠加随机游走均识别出19名直接参与劫机的10名成员，高于介数中心性、等概率叠加随机游走识别出的节点个数；Top19节点中，基于不等概率叠加随机游走可以识别出19名直接参与劫机的14名成员，其他方法次之。从表4可知，文中提出的方法与标准排序结果相似性最大，显著提高了排序精度。

图4 恐怖袭击网络重要度排名Top19的节点相似和

表2 节点重要度比较(1)

续表2

科研合作网络中网络的节点表示曾在网络科学领域发表过论文的科学家，连边表示合作关系。文中考虑无向无权网络，此数据集包含1 589个节点，2 742条边，其中128个孤立节点，共包含268个连通集，文中提取极大连通子图包含379个节点，974条边。采用基于不等概率叠加随机游走关键点识别算法选取重要性排名前5%的18个节点与度中心性、介数中心性、接近中心性、等概率叠加随机游走方法进行比较，结果如表3所示，文中提出的算法能够通过Top5%的节点两步转移覆盖节点率85%，低于介数中心性排序方法，高于节点度中心性、接近中心性和等概率叠加随机游走方法。如表5所示，文中方法排序结果与标准排序之间相似性次于度中心性，高于等概率叠加随机游走排序结果，能够有效地识别出网络中的关键节点。

USAir97网络节点表示机场，边表示航空路线，该数据集包含332个节点，2 126条边，通过中心性算法找到交通通畅性影响较大的机场，进行重点维护。表3通过比较不同中心性方法得到的Top10节点，不等概率叠加随机游走方法与其他中心性方法得到Top10的差异较小，与度中心性识别重要节点相同，介数中心性差异为4个，与接近中心性差异为3个，等概率叠加随机游走方法差异为1个。从表4可知，文中方法与SIR模型之间Kendall tau距离相似性明显高于其他中心性方法，证明了该方法的有效性，排序精度高于其他中心性方法。

表3 节点重要度比较(2)

表4 USAir97节点重要度比较

表5 各中心性算法与SIR模型Kendall tau

对比分析各算法时间复杂度，度中心性算法时间复杂度为O(n)，介数中心性时间复杂度为O(n3)，接近中心性、等概率叠加随机游走，文中算法时间复杂度为O(n2)。文中算法在时间复杂度一致的情况下，较等概率叠加随机游走方法关键点识别的准确性有很大提高。

4 结束语

针对复杂网络中关键点识别问题，提出了一种基于不等概率叠加随机游走的评估方法，引入Jaccard相似性指标进行不等概率随机游走，结合叠加游走计算相似和在无向网络中进行关键点识别，综合考虑节点间的相似性、两步转移到达节点、节点度信息及网络中所处位置等信息。实验证明，基于不等概率叠加随机游走相似和在不增加时间复杂度的情况下，可以较高精度有效地识别关键节点。综合实际网络特点，不等概率随机游走更好地考虑了随机游走特点。在一定程度上说明不等概率随机游走在无向网络关键点识别是有效的，下一步是将不等概率随机游走与点权相结合，并将其扩展到有向加权网络，进行更深入研究。