1. 引言
从自然界到人类社会、从生态关系到社会关系都存在着大量的复杂系统,这些常见的复杂系统大多是由一系列基本单元以及单元们之间的关系所组成的。这些基本单元以及单元们之间的关系被抽象成复杂网络的点和边。复杂网络分为有向无权的复杂网络、有向有权的复杂网络、无向有权的复杂网络和无向无权的复杂网络,复杂网络往往具有大量的节点,节点与节点之间有着复杂的联系,往往各个节点本身都是非线性系统,且许多复杂网络常呈现小世界性、无标度性、超家族性 [1] [2] 。复杂网络重要节点评估与识别是网络科学中一个重要的热点问题。
重要节点是相比于网络中的其他的节点而言能够在更大程度上影响网络结构与功能的一些特殊节点 [3] 。发现网络中的重要节点,有助于提升网络的鲁棒性和抗毁性,有助于对网络上的动力学行为进行控制和预测 [4] 。节点重要性评估在网络安全、信息传播、和疾病免疫等方面具有重大的实际应用价值。
经典度量复杂网络的方法有很多,有学者认为节点的度越大节点越重要,如度中心性、半局部中心性等;有方法认为位于几个链接区域的“桥点”很重要,如离心中心性、接近中心性、介数中心性等;有方法通过网络的连通性刻画节点的重要程度,如节点删除法、节点收缩法;还有方法基于随机游走的思想,认为一个节点被反复经过的概率越大越重要,如特征向量中心性、PageRank算法、LeaderRank算法、HITs算法等 [5] [6] 。特征向量中心性和累计提名方法一般用在无向网络中,PageRank算法和LeaderRank一般应用于有向网络中。HITs算法、自动信息汇集算法,SALSA 算法都考虑节点的双重角色:权威性和枢纽性,并认为两者相互影响 [3] 。这些算法只考虑到了节点或网络某一特定性质,没将节点和网络的多种性质进行融合考虑。
针对上面经典算法中出现的问题,许多学者都提出了方法。段杰明 [7] 提出了一种结合网络结构局域信息和标签扩散的节点排序算法。王凯莉等人 [8] 在k-shell分解法基础上考虑了节点自身壳值与其多阶邻居节点的壳值。马媛媛等人 [9] 提出了一种综合考虑节点的邻居数量和节点与邻居间亲密程度的节点重要度评估算法。张宪立等人 [10] 根据邻居节点的拓扑结构并结合万有引力定律,提出一种基于改进重力中心性的复杂网络节点重要性评估方法。胡钢等人 [11] 基于节点间的最优路径长度、最优路径数目和信息传播率定义节点间的传输能力,构建重要度传输矩阵,最后综合节点局部和全局属性来评估节点的重要度大小。李秋晖等人 [12] 提出了基于引力模型及相对路径数的节点重要度评估算法。以上文献在评估节点重要性时,未能充分考虑节点自身属性和网络拓扑结构对有向网络节点重要性的影响。
针对这些问题,本文提出了基于引力模型的随机游走节点重要性的评估方法。首先,通过调节节点出度和入度的比例做节点质量、以节点间相似值的倒数为引力模型中的距离、以节点间相对路径之比为引力模型系数,构造引力模型公式并度量网络节点间的相互作用力大小;其次,对形成的引力矩阵进行归一化得到可以随机游走的转移矩阵。本文提出的基于改进引力模型的随机游走复杂网络节点重要性评估的方法有以下优势和贡献:
一、该方法同时充分考虑了节点的出度和入度。连边的方向性反映节点的重要性,只考虑节点的连入边,不考虑节点的连出度,不符合现实,例如在信息传播中,一个节点只接受信息,不传播信息,该节点是不重要的。讨论节点合适的出度和入度比重对节点属性的影响。
二、完全基于复杂网络的结构信息,使节点间相关联度最大化。考虑网络结构对节点重要性的影响,在不同复杂网络中,该方法具有更强的适用性。
三、节点间的相对路径之比考虑了四阶路径之内的所有传播信息,充分考虑节点周围的局部信息,比只考虑节点间的最短路径得到的排序结果更准确。
2. 基于引力模型的随机游走算法
根据复杂网络的边是否有向,将网络分为有向网络和无向网路。构建有N个节点和M条边的有向无权网络模型,用图
表示,网络节点合集为
,网络节点边的合集为
,每条边的权重都为1。网络的邻接矩阵可以表示为
,当一条边从节点
指向节点
时,
;如果没有节点
指向节点
,则
。在有向网络中,节点的度根据节点边的方向分为出度和入度,
表示节点的入度,
表示节点的出度。
基于随机游走思想的方法,解决有向复杂网络图的不连通问题,保证算法的收敛效果,构建合适的转移矩阵,转移矩阵携带的信息对排序结果有重大的影响。为了准确的量化转移矩阵对节点重要性的影响,融合节点属性、节点局部信息与网络结构到引力模型中,构建两个节点的相互作用力,通过作用力之间的大小表达节点间相互转移的可能性,将任意两节点之间的相互力形成作用力矩阵,最后通过行归一化形成转移矩阵。给网络添加背景点,形成强连通图,保证随机游走成功。
2.1. 引力模型
根据万有引力模型 [13] [14] 知,一种物质对其他物质产生的作用力其实也就是这个物质在其自身周围产生特定的场。任意两个物质之间的引力关系为:
(1)
其中:M表示物质自身的为质量。r可以是两个物体之间的最短距离。G可以系数。
1) 确定质量M
节点的度 [10] 是与该节点直接相连接的其他节点的数目,在N个节点的无权无向网络中,节点
的度表示为:
(2)
在N个节点的有向无权网络中,节点
的出度和入度分别表示为:
(3)
(4)
其中:节点
的出度
表示从节点
出发到达邻居节点
的连边数;节点
的入度
表示从邻居节点
出发到达节点
的连边数。
其他经典随机游走的算法都只关注了节点的入度或出度,本文通过系数
调节节点的出度和入度同时对节点重要性的影响,生成衡量节点属性的新指标:综合度值,综合度值的计算公式为:
(5)
其中
表示有向网络中节点
的综合度,
表示调节节点出度与入度重要性的系数。
2) 确定距离r
改进的引力模型在分析节点间相互作用大小时,考虑节点与邻居间不同拓扑结构对节点的影响力不同,将节点间相似值的倒数作为引力模型的距离 [15] 。SimRank是一种有向图上基于图的拓扑结构信息来衡量任意两个对象间相似程度的模型,得到的节点相似值具有复杂网络全局的信息。该算法的基本思想是:如果两个对象被其相似的对象所引用,那么这两个对象也相似 [16] 。该算法的基本公式为:
(6)
其中
表示节点v的入度,
表示v的第i个邻居节点,c为衰减因子,且
,
表示两个节点的相似度。
3) 确定系数G
在分析节点间相互作用大小时,只考虑节点综合度数与节点间的相似性往往不够全面,节点间的距离是不可忽视的。李秋晖 [12] 等人在无向网络中考虑相对路径数,考虑二阶、三阶或更长阶的路径传递信息的能力。构造有向网络的作用力矩阵时,只能构造出边链接转移到邻居节点的作用力,在考虑节点通过一阶路径传递信息时,也要考虑到通过其他阶路径传递信息,不同路径传播信息的能力不同。通过这些相对路径数定义结构参数G:
(7)
其中:
表示节点
与
间长度为l的路径数目,N为网络节点数;
表示从节点
出发的所有
l阶路径数目,l阶路径数目用矩阵表示为
。
2.2. 确定转移矩阵和游走方式
本文重新定义网络中任意两节点间相互作用力大小为:
(8)
其中,
为节点
与节点
的SimRank相似值。其他符号表达同公式(5)与公式(7)。路径越长节点间信息传递越差,该算法只计算路径长度为1、2、3、4时的相对路径。由任意两点间的作用力生成作用力矩阵
。将作用力矩阵与有向网络的邻接矩阵对应元素相乘生成只有出边连接的矩阵
,再按行对矩阵进行归一化得到转移矩阵
,归一化后需要保证矩阵行的和为1,所以使用每个节点的对应值除以该节点所在矩阵的行和即可。
有向复杂网络上随机游走,可以选择与PageRank算法相同的方法,加入跳转参数;也可以选择LeaderRank算法 [17] [18] [19] 相同的方法,加入背景点。这两种方法都保证了图的强连通性,但是LeaderRank算法收敛速度更快,排序结果唯一,适用于大型复杂有向网络,排序的准确性和抗噪声能力较高。转移矩阵做随机游走时,选择添加背景点,同LeaderRank算法一样构造强连通图。
2.3. 算法流程与步骤
基于引力模型的随机游走算法主要的流程图如图1所示,该算法的步骤如下:
输入:有向无权复杂网络图G。
输出:每个节点重要性的排序结果
。
步骤一:为网络图添加公共点,并与每个节点双向链接,生成强连通图
。
步骤二:根据公式(5),计算强连通图
所有节点的综合度
,并通过调节
的取值,得到不同的综合度
。
步骤三:根据公式(6),计算强连通图
所有节点与其他节点的相似值,形成节点相似性矩阵
。
步骤四:根据公式(7),计算强连通图
所有节点与其他任意节点之间四阶路径之内的比,形成节点系数矩阵
。
步骤五:根据公式(8),将得到节点综合度
节点相似性矩阵
与节点系数矩阵
相结合得到节点间的作用力矩阵
。将生成的作用力矩阵
按行归一化,生成转移矩阵
。
步骤六:根据幂律法求转移矩阵的稳态分布
,将公共节点的稳态值平均分给其他节点,得到节点重要性的排序结果
。
3. 仿真实验与分析
3.1. 实验数据
检验基于改引力模型的随机游走算法对网络节点重要度的评估效果,本文选用四个真实网络数据进行相关实验。Enzymes-g1网络 [20] (简记为Enzymes)、Friendship-network-data-2013网络 [21] (简记为Friendship)、Celegans-Genetic网络和与CKM-Physicians-Innovation-Social网络 [22] (简记为Celegans、Physicians),数据均来源于网络数据库。表1为四个网络的基本统计特征,其中:N与M分别表示网络的节点数与边数;D为网络直径;
为网络的平均路径长度;
为网络的图密度;
为网络平均度;
为网络的平均聚类系数。

Table 1. Basic statistical characteristics of network
表1. 网络的基本统计特征
本文采用三个常用的指标评估节点的重要性,即强连通性、弱连通性、脆弱性。其中在评判网络的连通性时既要考虑子团的数量,也需要考虑最大连通子团的节点数量。仿真实验证明两个问题:第一,改进的算法比PageRank算法、LeaderRank算法、HITs算法具有更高的准确性;第二,不同出度和入度比值对节点综合度有影响,从而影响重要节点的排序结果,选取不同的
值是为了找到比较合适的取值范围,由公式(5)知,
取值不同,作用力大小不同,节点重要性的排序结果也不同,寻找
的最佳取值范围。表2为计算节点重要性时
的取值。
3.2. 强连通性评估指标
若G为有向图,若G中存在一条以节点
为起点,节点
为终点的有向路P,则称从节点
到节点
是可达的。如果G的任何两个顶点都是相互可达的,则称图G是强连通的 [23] [24] [25] ,图G被称为强连通图。非强连通有向图的极大强连通子图,称为强连通分量(strongly connected components),如果一个强连通分量中不再能加入任何一个顶点,则这个强连通分量是一个极大强连通分量。确定非强连通有向图每一个强连通分量的节点数,按节点的个数确定强连通分量的规模。则极大强连通率计算公式为:
(9)
其中:n表示网络的节点数,
表示删除部分节点后剩余网络中规模最大的强连通分量的节点数。GS越小,说明极大强连通分量的节点越少,网络被破坏的越厉害,节点排序结果的准确性越高。

Figure 2. Change of strong connectivity after removing different node numbers
图2. 移除不同节点数极大强连通率的变化情况
图2所示为四个真实网络的极大强连通率GS在不同攻击条件下随节点删除数目的变化情况。容易看出:在Enzymes网络中,改进算法的排序结果对网络的攻击效果明显好于其他经典算法。在Friendship网络中,删除排序前10到前25的节点,依据LR算法和改进算法的排序结果造成极大强连通率的变化是很相似的,但是删除前20个节点到前50个节点时,
取值0.35、0.45、0.55、0.65、0.75、0.85、0.95 的改进算法的排序结果造成极大强连通率的下降都要比其他算法快。在Celegans网络,
大部分取值的排序结果的准确性都要比其他经典算法好。在Physicians网络中,虽然删除前5到前25个节点时,改进算法的极大强连通率比其他算法高,但是删除前20个节点到前50个节点时,改进算法的极大强连通率比其他算法低,且下降的速度也比较快,改进算法呈现出较好的准确性。
复杂网络进行仿真实验中,网络移除节点后会破碎成零散的网络,这些零散的网络数量表明了网络的破碎程度,所以在评判网络的连通性时也要考虑子团的数量。强连通分量数越多,说明网络破碎的越厉害,算法的效果越好。图3所示为四个真实网络在不同攻击条件下,随节点删除数目的变化网络破碎成具有强连通性子网络数量情况。因为
取值比较多,图例不能很好的在图形中显示,每删除10个节点,从左到右的小条形图分别表示为
取值0.05、0.15、0.25、0.35、0.45、0.55、0.65、0.75、0.85、0.95的改进、leaderRank算法、PageRank算法、HITs的枢纽值和权威值排序结果造成的子网络数量。在Enzymes网络、Celegans网络和Physicians网络中,
大部分取值的排序结果形成的强连通分量数都多于其他算法。Friendship网络在删除前20个节点时,排序效果与经典算法相似,但删除前40或前50个节点时,改进的算法显示出较好的准确性。

Figure 3. Change of the number of subnetworks with different node numbers removed
图3. 移除不同节点数子网络数量的变化情况
总体来看,改进算法在极大强连通率和强连通分量数两个评估指标中都表现出较高的准确性,且大部分的
取值的改进算法都表现出较好的准确性。
3.3. 弱连通性评估指标
将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图 [25] [26] 。在对复杂网络进行攻击的仿真实验中,网络受到攻击后会破碎成零散的网络子图,按节点的个数确定弱连通分量的规模。则极大弱连通率计算公式为:
(10)
其中:n表示网络的节点数,
表示删除部分节点后剩余网络中规模最大的弱连通分量的节点数。GW越小,说明极大弱连通分量的节点越少,网络被破坏的越厉害,节点排序结果的准确性越高。

Figure 4. Change of maximal weak connectivity with different node numbers removed
图4. 移除不同节点数极大弱连通率的变化情况
图4所示为四个真实网络的极大弱连通率GW在不同攻击条件下随节点删除数目的变化情况。容易看出:在Friendship、Celegans网络中,改进的算法对网络的攻击效果明显好于其他经典的算法。在Enzymes网络中,删除排序前20的节点,依据HITs权威值和改进算法的排序结果造成极大弱连通率的变化是很相似的,但是删除前20个节点到前50个节点时,
取值0.65、0.75、0.85、0.95的改进算法的排序结果造成极大弱连通率的下降都要比其他算法快。但在Physicians网络,改进算法的极大弱连通率比其他算法高,改进效果略次于其他三个网络。但总体上,改进算法的排序结果表现出更高的准确性。
与强连通性评估指标相同,在评判网络的连通性时也要考虑符合弱连通性子团的数量,弱连通分量数越多,说明网络破碎的越厉害,算法的效果越好。因为
取值比较多,图例不能很好的在图形中显示,图5每种颜色和顺序的条形图表示的算法与图3一致。在Enzymes网络、Celegans网络和Friendship网络中,
大部分取值的排序结果形成的弱连通分量数多于其他算法,算法表现出较高的准确性。Physicians网络只有在在删除前20和30个节点时,排序效果与经典算法相似,但删除前10、40或前50个节点时,改进的算法又显示出较好的准确性。

Figure 5. Change of the number of subnetworks with different node numbers removed
图5. 移除不同节点数子网络数量的变化情况
总体来看,改进算法在极大弱连通率和弱连通分量数两个评估指标中都表现出较高的准确性,且大部分的
取值的改进算法都表现出较好的准确性。
3.4. 脆弱性评估指标
使用网络的连通性衡量网络中节点失效或者遭受攻击后引起的整个网络连通度的下降,也可以使用脆弱性衡量网络中节点失效或者遭受攻击后引起的整个网络系统性能的下降。节点脆弱性系数 [7] V是网络效率的变化情况,计算公式如下:
(11)
其中,E表示未删除节点时的网络效率,i表示网络中的节点,
表示移除节点
后的网络效率。
重要节点之所以能够在网络结构方面发挥关键性作用,不仅是节点度数的优势,也是与网络中其余节点间存在的拓扑关系。移除重要节点必定给网络结构造成更大的伤害,这可以通过节点脆弱系数来表现。脆弱性系数越大,表示节点移除后对网络的破坏力度越大。图6比较了经典算法与改进算法的节点脆弱系数的实验效果,横坐标n表示的是移除节点的个数,纵坐标p(n)表示的是节点脆弱系数值。节点脆弱系数值随移除节点数n的变化在四个网络中,都证实了改进算法表现出更高的准确性和有效性。大部分的
取值的改进算法都表现出较好的准确性。

Figure 6. Change of vulnerability coefficient after removing different nodes
图6. 移除不同节点脆弱系数的变化情况
4. 结束语
将节点自身属性、节点间的相似性和节点间的相对路径比到引力模型中,构造引力矩阵,再通过行归一化构造转移矩阵,利用LeaderRank算法中的方法构造强连通网络,保证稳态分布。在利用节点的综合度计算节点自身属性时,调节出度和入度的参数
,因此,在验证改进算法比其他经典算法有更高准确性时,也确定最优的参数
。研究结果表明,相比较PageRank算法、leaderRank算法和HITs算法,改进的算法具有更高的准确性。通过观察四个真实网络在三种评估指标中的结果可知,当
取值0.25到0.65时,四个网络的强连通分量数和弱连通分量数几乎是最高的,并且极大强连通率和极大弱连通率的变化幅度也比较大;节点脆弱系数也比较高。因此,
取值0.25到0.65时,改进的算法表现出更高的准确性。
基金项目
全国统计科学研究项目(No. 2020LY080)。
NOTES
*通讯作者。