基于节点信任度的复杂网络关键节点识别

王 斌,王亚云,盛津芳,孙泽军,2

1(中南大学 计算机学院，长沙 410083)2(平顶山学院 网络中心,河南 平顶山 467000)

1 引 言

复杂网络简化标识现实世界中的复杂系统,对复杂网络的研究能帮助人们对其深刻认知,了解内部动态演化及行为预测[1-3].复杂网络中存在部分节点,这些节点数量少,但是在整个网络的信息传播中扮演着关键的角色,称为关键节点.识别复杂网络中的关键节点是复杂网络研究领域中的一个重要方向[4],对现实中网络信息传播[5],传染病扩散[6],产品推广[7,8]等具有很高的实际价值,在一定程度上可以有效减少经济投入和避免经济损失[9].

近几十年来,从基于结构中心性,迭代细化中心性,到基于节点动态操作,复杂网络领域有很多识别关键节点的算法被提出,例如度中心性(Degree Centrality,DC)[10]算法通过统计网络中与节点直接相连的邻居节点个数作为判断节点重要性的依据.Chen等[11]考虑节点半局部信息,提出半局部中心性.介数中心性(Betweenness Centrality,BC)[12]描述了节点对网络中沿最短路径传输的信息流的控制能力,随机游走介数中心性认为在网络信息传播过程中最短路径比非最短路径重要.K-shell[13]算法通过层层剥离处于网络外层的节点,认为处于网络核心的节点具有较高的影响力.特征向量中心性通过统计节点的相邻节点的重要度作为该节点的关键性指标.PageRank[14]算法是特征向量中心性的变种[15],其是应用在Google搜索引擎中的网页排序算法.Lü[16]等提出的LeaderRank算法通过随机游走的思想识别关键节点,其在有向网络中表现良好.HITS[17]赋予每个节点权威值和枢纽值,二者相互影响以做为评价节点影响力的指标.以及其他基于节点删除和收缩的算法,如节点收缩法等.

上述算法从不同角度刻画了节点的影响力,有各自的优点,但也有一定的局限性,例如,DC是基于网络拓扑结构的最直观的算法,但是没有考虑节点的位置及周围节点的影响[18];k-shell在一些特殊的网络,如树形网络中,经常会分配给大量节点相同的Ks值;PageRank将自己的PR值平均分配给相邻节点,这与实际认知有偏差;BC和基于节点删除或收缩的算法时间复杂度很高,并且一些算法在不连通网络中效果欠佳,如节点删除法不能区分删除后使网络变得不再连通的节点的重要度[19].

另一方面,上述算法大部分都是基于网络的拓扑结构,没有考虑节点之间的属性信息,而网络结构在表达节点信息上具有一定的局限性.事实上,网络中节点之间的交互行为也可能会影响节点的重要性.例如在社交网络中,如果两个个体之间有更多的共同点,二者越相似,也就越信任对方,越倾向于交换更多信息;此外,如果某一个体与网络中较多个体之间有关联,那么在信息传播中,将信息传输给该个体将有利于信息流在整个网路中的快速扩散.文献[20] 考虑节点共同指向和指出的节点个数,提出了基于LeaderRank和节点相似性的关键节点识别算法.本文结合提出的节点信任度和PageRank算法构建一种关键节点识别算法TPR(Trust-PageRank),该算法综合考虑了网络本身的拓扑结构特性及节点之间的交互行为,避免因单一角度地刻画造成评价的片面性.在实验部分将TPR算法和DC,BC,PageRank,HITS算法应用在具体的真实网络并进行对比,结果表明TPR算法能合理有效地识别复杂网络的关键节点,并且可以有效区分重要度相当的节点.

2 基于信任度和PageRank的关键节点识别

2.1 基本思想

PageRank算法最初由万维网网页排序产生,它的有效性不是基于难以测量的内在结构,而是其感知有效性和易于理解的哲学:不是根据对象难以衡量的自身质量进行排序,如网页的实用性,而是将每个链接理解为潜在的投票来挖掘网络中隐藏的综合特征[21].目前PageRank算法不仅是谷歌及其他搜索引擎的核心,而且被用在各种网络环境中对数据进行排名.PageRank算法认为网页的重要性依赖于与它相邻的页面重要性.如果一个网页有很多来自其他重要页面的链接,那么该网页也有较高的重要性.算法初始时,每个网页拥有一个初始的PR值,通过不断迭代达到稳定状态.在这个过程中,每个网页以一个随机概率跳转到相邻网页,以额外概率跳转到所有网页,节点vi的PageRank值定义为:

(1)

α为跳转概率,一般会取α=0.85.

在PageRank算法中,网页将自己的PR值平均分配给相邻节点,但是在实际网络中节点之间交换信息的概率及信息量很大程度上并不仅仅是平均分配.在网络的信息传播中,为了叙述简便,在此假设其中只有一个节点需要将信息传播到网络中,为使信息尽可能以较快的速率传输到所有节点,该节点应将信息扩散到与其相邻的所有节点,并且对于自己比较“信任”的节点会扩散更多的信息,直到网络中所有节点的信息达到比较均衡的状态,或者算法达到一定的迭代次数,这和我们在现实中的认知是一致的.

本文中,网络由G=(V,E)表示,其中V表示网络的节点集,E表示节点的边集.网络G的邻接矩阵为A={aij},在无向网络中,如果节点vi与vj之间有连边,则aij=1.n=|V|是网络中节点个数,m=|E|为网路中边的个数.表1给出了下文将要用到的符号列表.

表1 符号列表
Table 1 List of symbol

2.2 Trust-PageRank关键节点识别

2.2.1 相似性比例

在现实生活的社交网络中,如果两个个体有共同的爱好,那么他们在某种程度上会有一定的相似性,交互的频率也会较多,也即,相互之间会交换更多的信息.相反,如果个体之间没有任何交集,那么个体之间的相似性比较小,相应地会以很小的频率交互.

假设节点vi和vj的爱好集为H(i)和H(j),则节点vi与节点vj的相似性s(i,j)为:

s(i,j)=|H(i)∩H(j)|

(2)

如图1(a)所示的网络中,节点v,1,2,3,4的爱好集合分别为H(v),H(1),H(2),H(3),H(4).

H(v)={basketball,pingpong,run},

H(1)={basketball,run},

H(2)={pingpong},

H(3)={tennis},

H(4)={run}.

则,

s(1,v)=|H(1)∩H(v)|=|{basketball,run}|=2,

s(2,v)=|H(2)∩H(v)|={pingpong}|=1,

s(3,v)=|H(3)∩H(v)|=|φ|=0,

s(4,v)=|H(4)∩H(v)|=|{run}|=1.

如果定义节点vi与其邻居节点的相似性之和Si为:

(3)

则图1(a)中节点v与其所有邻居节点的相似性之和为Sv=2+1+1=4.

如果把节点的每一个爱好集合看做一个相邻节点集,如图1(b)所示,那么节点的相似性就由节点的共同邻居节点决定:如果两个节点的邻居节点越相似,那么这两个节点也就越相似.另外,公式(2)只是为了便于简要说明节点的相似性依赖于其邻居节点的相似性的思想,用以计算相似性值过于简化.本文采用了另一种计算相似性的算法:SimRank算法.

SimRank[22]算法认为两个节点的相似性取决于其邻居节点,若其邻居节点越相似,则二者越相似.基本的SimRank算法公式为:

(4)

其中,C是一个衰减因子,为常数,C∈[0,1],一般情况下,如果N(a)或N(b)为空集,为了避免公式(4)出现除数为0的情况,会定义s(a,b)=0.定义网络节点的初始相似性为:

(5)

SimRank和PageRank算法类似,都是采用迭代计算,且s(a,b)=s(b,a).由于在本实验中计算的是相似性比例,因此,常数C的值对实验结果并无影响,在此本文取C=1.

基于节点相似性可以得到相似性比例.

定义1.节点vi占节点vj的相似性比例Rs(i,j)为:

(6)

图1(b)中节点v的邻居节点集合Nv={1,2,3,4,5,6,8},节点v与其所有邻居节点相似性之和为Sv=s(1,v)+s(2,v)+s(3,v)+s(4,v)+s(5,v)+s(6,v)+s(8,v),则节点1占节点v的相似性比例为Rs(1,v)=s(1,v)/Sv,其他节点与此类似.

图1 节点爱好集图及节点相似性网络Fig.1 Hobby sets and the network of nodes′ similarity

2.2.2 相邻度比例

网络中一个节点的度越大,其与周围节点接触的范围越大.如果一个节点需要进行信息传播,那么将信息传播给度值较大的邻居节点将有助于网络中信息流的扩散,但并不是片面的只将信息传播给度值最大的节点.如图2所示,节点v的相邻节点1,2,3,4中,节点1的度值最大.如果节点v只将信息传播给度值最大的节点1,那么区域b,c和d将得不到任何传输的信息.为使信息能尽可能以最大速率到达网络中的所有节点,本文综合考虑节点及相邻节点的度值提出相邻度比例.

定义2.节点vi占节点vj的相邻度比例Rd(i,j)为:

(7)

其中,di表示节点vi的度,图2展示了节点邻居集合及其相邻度比例.

2.2.3 节点信任度

网络中节点之间的信任度由节点基于属性信息的相似性比例和基于拓扑结构的度比例组成.

定义3.节点vj对vi的信任度Tij为:

Tij=(1-k)Rs(i,j)+kRd(i,j)

(8)

k∈[0,1],本文中,定义k与PageRank算法中的跳转概率α相等,即k=α.

图2 节点相邻度比例Fig.2 Degree-ratio of nodes

2.2.4 Trust-PageRank算法

结合PageRank算法提出基于节点信任度的Trust-PageRank算法.从节点信任值来看,网络中的信息流动时节点会将信息按信任度分配给相邻节点,同时信任度越大的邻居节点将会得到更多的信息.通过将节点信任度引入到PageRank算法中识别关键节点.

表2 基于信任度的关键节点识别算法

Table 2 Algorithm identifying influential nodes based on trust-value

Input:G=(V,E)Output:rankList1 forallvs∈Vdo2 Initializethenetworkandcountthesetofadjacentnodesofvs;3 endfor4 forallconnectednodesvu,vv∈Vdo5 Initializethesimilaritys(vu,vv)ofvuandvvusingthefor-mula(5);6 endfor7 forallvi∈Vdo8 foralladjacentnodesvjofvi,do9 ifvi=vjthen10 s(vi,vj)=1;11 else12 Statisticthesimilaritiess(vm,vn)betweenneigh-bornodesofvi,vjwithvm∈Nvi,vn∈Nvjandthengets(vi,vj)usingtheformula(4);13 endif14 simRatioMap.put((vi,vj),s(vi,vj));15 endfor16 endfor17 forallvt∈Vdo18 CalculateTPRtbasedonsimRatioMapandtheratioofde-greeObtainedatthefirstofthealgorithmusingtheformula(9);19 rankList.put(vt,TPRt);20 endfor21 rankList.sort();

定义4.网络中节点vi的影响力指标TPRi为:

(9)

其中,Tij为由公式(8)得出的节点vj对节点vi的信任度,n为网络中节点个数,α为跳转概率,N(i)为节点vi的邻居节点集合,di表示节点vi的度.本文实验取α=0.85.

算法通过对输入的网络数据进行初始化,迭代计算得到节点相似性集,根据相似性集合和初始化集合计算相似性比例和相邻度比例,进而得到节点之间的信任度,再结合PageRank计算网络中各个节点的TPR指标值.算法具体步骤如表2所示.

3 实验分析

3.1 数据集

本文选择9个真实网络及1个非真实网络进行算法有效性验证,分别包括Email网络,Euroroad电子道路网络,US Power Grid美国电力网络,Protein和PDZBase蛋白质网络,Polbooks美国政治书网络,Football足球俱乐部网络等.各个网络详细信息如表3所示.

表3 数据集
Table 3 Data sets

网络|v||E|kmaxCCKite10183.660.578Zachary34784.5888170.588Polbooks1054418.4250.488Football11561310.661120.403PDZBase2122422.283210.013Email113354519.622710.254Euroroad117414172.414100.02Propro187022772.356560.153Protein313361493.9251290.106PowerGrid494165942.669190.107

其中,|v|和|E|分别表示网络中的节点和边的数量,和kmax表示网络节点的平均度和最大度,CC为网络平均聚类系数.

3.2 评价指标

3.2.1 SIR模型

本文采用SIR模型[23]评价TPR算法的性能及有效性.在SIR模型中,所有节点共有3种状态:

1)易感染状态S:处于该状态的节点会被其他节点感染;

2)感染状态I:感染节点会以β的概率感染其他节点,并以γ的概率恢复到免疫状态;

3)免疫状态R:由感染状态恢复,不具有感染其他节点的能力,并且不能再次被感染.评价实验进行多次迭代,进行t步感染,每次迭代时选择一个节点作为种子节点.将最终t步感染后网络中感染节点及恢复节点的平均数量做为该节点的传播能力,记为F(t).定义节点vi的SIR传播重要性Ki为：

(10)

其中Nite为迭代次数,本文中Nite=100,nI和nR分别为感染节点和恢复节点的数量.

3.2.2 Kendall系数

Kendall相关系数[24]用于测量多列等级变量的相关性,定义为:

(11)

其中,C,D分别代表两个排序序列集合中一致和不一致的数量,N表示统计对象个数.τ∈[-1,1],τ取值越大,表示二者相关性越强.τ=0说明二者相互独立;τ=-1,表示二者排序相关性相反.

3.3 有效性分析

本文首先以小型风筝网络Kite[25]及跆拳道Zachary网络为例初步验证算法的有效性,网络如图3所示.将TPR算法应用在Kite及Zachary网络中识别其关键节点,得出网络中的Top-10节点,并将其结果与DC,BC,PageRank,HITS算法进行对比,结果如表4所示.

图3 两个小型网络Fig.3 Two small-scale networks

从表4中可以看出对于对称的风筝网络,各个算法排序结果都比较合理,TPR算法识别的关键节点排序与DC一致,此外TPR相对于PageRank算法认为节点6和8比节点2排名靠前,是因为节点2的TPR值主要由其邻居节点1,3贡献,而节点1,3的TPR指标值都比较小;此外节点2的度数较小,并且其与节点3的相似性相比节点3的其他邻居节点(节点4,5)并不占优势;而节点6的(或节点8)邻居节点排名均比较靠前,并且其度数和相似性与周围邻居节点相比无明显差别.

Zachary网络中,TPR算法选择的Top-10节点基本与其他算法一致,仅在排序上有部分差异.DC,PageRank,TPR认为前10个重要节点为节点1,2,3,4,9,14,24,32,33,34,BC算法认为节点6,20比节点4,24重要,HITS算法认为节点31比节点24重要.

在进行SIR传播验证时,由于在实际中节点的扩散能力在初始传播时更为重要[11],因此,本文只将节点进行10步(即t=10)感染传播,而不是等待整个网络的感染传播达到稳定状态.

首先,每次迭代中感染节点以0.3的概率感染其邻居节点,并以1的概率恢复到免疫状态,即β=0.3,γ=1.将TPR算法和DC,BC,PageRank,HITS算法进行对比,这些中心性算法计算的各个网络的节点中心性值与经过10步SIR传播计算的节点传播重要性统计结果如图4所示.

在Email网络(图4(a))中,DC,PageRank,HITS及TPR算法能很好地表现出节点重要度与SIR传播重要度指标正相关的特征,且DC,PageRank,TPR算法中节点分布集中,线性程度更好,而BC的中心性指标值分布整体比较分散.Euroroad网络(图4(b))中,各个算法都能表现正相关性特性,但是TPR及PageRank算法节点分布集中且正相关性特征明显,DC不能区分度数相同的节点,BC不能很好地表现中心性值与节点传播能力的正相关性(其图中节点大多集中在介数值较小即横坐标轴左侧处),HITS算法中对于部分SIR传播重要度值较大的节点,其HITS中心性指标值相对较低.DC,PageRank,HITS及TPR算法在Protein网络(图4(c))中结果表现相似,BC算法中节点分布相对分散.几种算法在Power Grid网络(图4(d))中表现结果中同Euroroad网络相似.从上述实验结果图来看,在Email,Euroroad,Protein网络中,TPR算法计算的中心性指标值与SIR模型得到的节点传播重要度线性一致性相比其他算法较好或相当,即对于SIR模型识别的重要度相当的节点,TPR算法也认为这些节点重要度差别不大.在Power Grid网络中,HITS算法的线性一致性优于TPR算法.

表4 网络Top-10节点
Table 4 Top-10 nodes of kite and zachary

排序KiteDCBCPageRankHITSTPR排序ZacharyDCBCPageRankHITSTPR17377713413434124444421341134355555333333333349299943333335107101010523222263936364932932761028673224144886638891424414928822914209329101111110246143124

图4 网络不同中心性值与SIR传播力对比Fig.4 Figure comparing between central-value and the propagation of SIR

其次,为了评估每个算法识别出的排名靠前的关键节点的感染能力,本文选取DC,BC,PageRank,HITS算法和TPR算法分别识别出的前10个关键节点作为种子节点,设定β=0.3,γ=1,进行20步传播,并对此进行100次迭代,最后统计传播结束后网络中感染节点和恢复节点的总数,以此来表示各个算法选出的前10个节点的传播能力,结果如图5所示.

可以看出,在Email(图5(a))和Protein(图5(c))网络中各个算法识别的Top-10节点传播能力相当,且t<5时,DC,BC,PageRank,TPR算法感染曲线斜率相当,HITS算法线性斜率略小于其他算法.在Euroroad网络(图5(b))中,各个算法识别的Top-10节点在20步传播之后,网络中处于感染和恢复状态的节点数及种子节点感染速率均为TPR>DC>PageRank> HITS> BC.在Power Grid网络(图5(d))中,DC识别的Top-10节点传播能力较强,各个算法的Top-10节点感染节点数量和感染增速分别为DC> TPR> PageRank> BC> HITS和DC> TPR> PageRank> HITS> BC.上述实验结果中,0

图5 感染和恢复节点的数量增长图Fig.5 Growth graph of infected and recovered nodes

表5 kendall相关性系数
Table 5 Kendall′s coefficient

数据算法DCBCPageRankHITSTPRPolbooks0.687350.282750.645970.517240.67356PDZBase0.269170.461660.299840.409830.46589Football0.113630.132570.215900.189390.30681Propro0.410730.411470.399700.140080.54318

4 结 论

本文考虑网络拓扑结构及节点属性信息提出节点相邻度比例及相似性比例,综合提出节点信任度,并结合PageRank提出基于节点信任度的复杂网络关键节点识别算法Trust-PageRank.实验部分,首先将TPR算法应用在风筝网络和跆拳道网络中初步验证了算法的有效性.为了评估TPR算法识别关键节点的准确度及感染能力,本文另选择8个真实网络,利用SIR模型及kendall相关性系数评估网络中节点的传播速率和能力.将DC,BC,PageRank,HITS和TPR算法识别出的各个网络的关键节点,与利用SIR模型得到的结果进行对比,并计算各个对比算法识别出的前30%的关键节点与SIR模型排序结果的相关性系数,结果显示TPR算法能有效地识别关键节点,并且在SIR初始传播和识别重要度相当的节点方面有一定的优势.