《一种改进的基于信息传播率的复杂网络影响力评估算法-阮逸润.pdf》由会员分享，可在线阅读，更多相关《一种改进的基于信息传播率的复杂网络影响力评估算法-阮逸润.pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一种改进的基于信息传播率的复杂网络影响力评估算法阮逸润老松杨王竣德白亮侯绿林An improved evaluating method of node spreading influence in complex network based on informationspreading probabilityRuan Yi-Run Lao Song-Yang Wang Jun-De Bai Liang Hou L-Lin引用信息Citation: Acta Physica Sinica , 66, 208901 (2017) DOI: 10.7498/aps.66.208901在线阅读Vie
2、w online: http:/dx.doi.org/10.7498/aps.66.208901当期内容View table of contents: http:/ you may be interested in多层单向耦合星形网络的特征值谱及同步能力分析Synchronizability and eigenvalues of multilayer star networks through unidirectionally coupling物理学报.2017, 66(18): 188901 http:/dx.doi.org/10.7498/aps.66.188901网络集聚性对节点中心性指
3、标的准确性影响Effect of variable network clustering on the accuracy of node centrality物理学报.2016, 65(2): 028901 http:/dx.doi.org/10.7498/aps.65.028901两层星形网络的特征值谱及同步能力Synchronizability and eigenvalues of two-layer star networks物理学报.2016, 65(2): 028902 http:/dx.doi.org/10.7498/aps.65.028902基于联合矩阵分解的节点多属性网络社团检
4、测Community detection based on joint matrix factorization in networks with node attributes物理学报.2015, 64(21): 218901 http:/dx.doi.org/10.7498/aps.64.218901基于时滞耦合映像格子的多耦合边耦合网络级联抗毁性研究Study on cascading invulnerability of multi-coupling-links coupled networks based on time-delay coupledmap lattices model
5、物理学报.2014, 63(7): 078901 http:/dx.doi.org/10.7498/aps.63.078901万方数据物理学报Acta Phys. Sin. Vol. 66, No. 20 (2017) 208901一种改进的基于信息传播率的复杂网络影响力评估算法阮逸润1)y老松杨1)王竣德1)白亮1)侯绿林2)1)(国防科技大学,信息系统工程重点实验室,长沙410073)2)(国防大学联合勤务学院,北京100858)(2017年5月19日收到; 2017年7月4日收到修改稿)评价网络中节点的信息传播影响力对于理解网络结构与网络功能具有重要意义.目前,许多基于最短路径的指标,如
6、接近中心性、介数中心性以及半局部(SP)指标等相继用于评价节点传播影响力.最短路径表示节点间信息传播途径始终选择最优方式,然而实际上网络间的信息传播过程更类似于随机游走,信息的传播途径可以是节点间的任一可达路径,在集聚系数高的网络中,节点的局部高聚簇性有利于信息的有效扩散,若只考虑信息按最优传播方式即最短路径传播,则会低估节点信息传播的能力,从而降低节点影响力的排序精度.综合考虑节点与三步内邻居间的有效可达路径以及信息传播率,提出了一种SP指标的改进算法,即ASP算法.在多个经典的实际网络和人工网络上利用SIR模型对传播过程进行仿真,结果表明ASP指标与度指标、核数指标、接近中心性指标、介数中
7、心性指标以及SP指标相比,可以更精确地对节点传播影响力进行排序.关键词:复杂网络,传播影响力,信息传播率,传播路径PACS: 89.75.Fb, 89.75.Hc DOI: 10.7498/aps.66.2089011引言自然界中诸多的复杂系统都可以网络的形式存在,我们的生活被各种各样的网络所包围1-4,比如互联网、电力网络、社交网络和航空网络.科学界真正开启网络研究的热潮是在网络的无标度特性5和小世界特性6被发现之后.网络的无标度特性说明复杂系统内部存在严重的不均匀分布,不同节点对网络结构和功能的影响大不相同;而小世界特性表示网络中信息传递速度快,大部分节点通过少数几步就可以到达其他节点.当
8、前,越来越多的学者将研究的焦点放在网络节点个体的分析上,其中,如何准确识别网络节点的传播影响力是当前研究热点之一,该工作对于控制谣言在社交网络上的传播7;8、传染病控制9;10、设计有效广告投放策略进行病毒式营销等11-14具有非常重要的作用.目前已提出许多经典的中心性指标用于对节点的传播影响力进行排序,包括度中心性15、半局部度中心性16、特征向量中心性17;18、接近中心性19、介数中心性20、HITS21、PageRank22;23、LeaderRank24与H指数等25.其中度排序方法最为简单直观,但其精度有待进一步提高;半局部中心性指标有限地扩大了源节点领域的覆盖范围,在提高算法精度
9、的同时兼顾了算法的时间复杂度.Kitsak等26提出了K核分解算法,该算法通过逐步剥离网络外围度数小的节点,可以较为准确地识别网络中最有影响力的内核节点,但该方法对于网络整体节点的排序结果粒度较粗,节点间的传播影响力区分度不够.核数中心性指标27认为节点的影响力由其邻居在网络中的地位决定,节点与网络国家自然科学基金(批准号: 61302144, 61603408)资助的课题.通信作者. E-mail: 2017中国物理学会Chinese Physical Society http:/208901-1万方数据物理学报Acta Phys. Sin. Vol. 66, No. 20 (2017)
10、208901中K核值大的节点间存在的连接越多,则其影响力越大. Liu等28考虑多阶邻居节点的中心性,提出了一种邻域中心性指标用于评价节点影响力,发现算法排序效果并不总是随着邻居阶数的增大而变好.段杰明等29基于自规避随机游走思想,提出一种综合考虑网络结构局域信息和标签扩散的影响力排序算法. Liu等30综合考虑传染率、康复率和有限的时间步三个因素用于评价网络节点影响力.更多关于节点传播影响力排序方面的研究可以参见文献31-33.最近, Bao等34指出节点的传播影响力由节点与邻域节点间的最短路径数、最短路径长度以及传播概率决定,并基于此设计了一种半局部(SP)算法用于评价节点传播影响力.最短
11、路径表示节点间信息传播途径始终选择最优方式,然而实际上网络中的消息、谣言或者资讯等在节点间进行传播时并不会遵循最短路径,信息扩散的过程更类似于随机游走35.在集聚系数高的网络中,节点的局部高聚簇性有利于信息的有效扩散,若只考虑信息按最优传播方式即最短路径传播,则会低估节点信息传播的能力,从而降低节点影响力的排序精度.综合考虑节点与局域三步内邻居的有效可达路径及信息传播率,本文提出了一种SP指标的改进算法,即ASP算法.在多个真实世界网络和人工网络中的实验表明, ASP算法与SP指标、核数中心性指标、半局部度中心性指标以及介数中心性指标相比,更能准确评估节点的传播影响力.2相关研究假设无向网络G
12、 = (V;E)包含|V | = N个节点和|E| = M条边,其网络结构可用邻接矩阵A = (aij)NN表示,当节点i与节点j之间存在连接时, aij = 1,否则aij = 0.2.1度指标度排序方法最为简单直观15, ki表示节点i的邻居节点数:ki =j iaij; (1)式中 i表示节点i一跳邻域内的邻居.度指标反映了节点的直接影响力,信息从度越大的节点发起,网络中第一时间接收到该信息的节点数越多,但度指标忽略了邻居节点间的差异性,导致其排序精度不高.2.2接近中心性接近中心性(CC)反映了节点到达其他节点的难易程度19,可表示为CC_i = NNj=1dij; (2)式中dij为
13、节点i到节点j的距离, N代表网络节点总数.2.3介数指标介数指标(BC)以网络中经过某个节点的最短路径的数目来量化节点在网络中的地位20,定义为CB_i =s=i=tVnistgst ; (3)式中gst表示从节点s到节点t的最短路径数, nist表示其中经过节点i的最短路径数.2.4核数指标Bae和Kim27同时考虑节点度与邻居节点的K核值,提出了一种核数指标(Cnc)用于评价节点传播影响力.该指标定义为Cnc_i =j iK(j); (4)式中K(j)表示节点j的K核值.2.5 SP指标Bao等34从信息传播的角度分析认为,从网络中的某一节点i发起的信息要成功传递到另一个节点j,其概率由
14、节点i和j之间的最短路径数目、最短路径长度以及信息传播率决定,他们将网络平均度k的倒数近似为信息传播率,设计了SP指标用于评价节点传播影响力,表示为fSP_i =jinij (1/k)dij; (5)式中i表示与节点i距离小于等于网络半径的节点集合, nij表示节点i和节点j之间的最短路径数目, nij(1/k)dij近似表示节点i成功将信息传播至节点j的概率.208901-2万方数据物理学报Acta Phys. Sin. Vol. 66, No. 20 (2017) 2089012.6 ASP指标实际上,信息按照最短路径传播只是理想中的路由方式.从某一个节点i发起的信息要最终传递至另一个节点
15、j,信息传递的路径理论上可以是i和j之间的任一可达路径,因此在计算节点i将信息传播至节点j的可能性时,若只考虑最短路径,必然会降低算法的精度.以图1为例,由于只考虑最短路径,节点i和k将信息传递至节点a的概率都为3(1/k)3.依次计算信息从节点传递到其他邻域邻居的概率,最终得到节点i和k的SP指标值相等.然而直观上由于节点i的局部高聚簇性,节点i将信息传递至a的过程中相比于节点k具有更多的路径选择,因此可以推断节点i的传播影响力大于节点k.疾病传播模型(SIR模型)信息传播仿真实验也验证了我们的猜想.idkac befghj1.87901.89852.0635 1.89151.93951.6
16、7102.03501.6455 1.6330 1.59851.7840图1 11个节点组成的网络图,节点感染概率取 = 0:2(传播阈值 th = 0:3409)时在SIR模型上进行2000次独立仿真实验得到11个节点的信息传播影响力Fig. 1. A simple network with 11 nodes. The spread-ing inuence of each node is obtained by simulationon the SIR model over 2000 independent runs with= 0:2 ( th = 0:3409).基于以上分析,我们设计了S
17、P指标的改进算法,即ASP算法,其表达式为fASP_i =j ifASP_ij=j ilnl (1/k)l; 1 l 3; (6)式中fASP_ij表示节点i将信息传播至节点j的成功率, i表示节点i三步内的邻居节点集合, l表示节点i到节点j的可达路径的长度, nl表示节点i到节点j可达路径长度(不包括回路)为l的路径总数.Fowler和Christakis36认为节点的影响范围不仅限于直接相邻的节点,还能间接影响与邻居节点相邻的节点,三阶以内都可能产生影响,并提出了三阶影响力原则.同时由于(1/k)l随着l的增大会快速衰减,因此考虑所有的可达路径并不必要, ASP算法只将节点与邻域节点间长
18、度不大于3的可达路径纳入计算范围.对于一步邻居节点,fASP_ij =lnl (1/k)l= 1/k + |n(i) n(j)| (1/k)2+A3(i;j) - |n(i)| - |n(j)| + 1 (1/k)3 ; (7)表1 ASP算法框架Table 1. The framework of ASP algorithm.Input: adjacent matrix A= (aij)N N of social networkG = (V;E), |V | = N, |E| = MOutput: ASP(V)1 Input: A= (aij)N N2 Compute reachability
19、 matrix element A3 (i;j)3 For i = 1 to N4 For j = 1 to k1 (k1 is the number of 1-stepneighborhoods of node i)5 Compute the probability that the node i transmitsinformation to the node j6 fASP_ij = (1/k) + |n(i) n(j)| (1/k)2+A3(i;j) - |n(i)| - |n(j)| + 1 (1/k)37 End for8 For l = 1 to k2 (k2 is the nu
20、mber of 2-stepneighborhoods of node i)9 Compute the probability that the node i transmitsinformation to the node l10 fASP_il = |n(i) n(l)| (1/k)2 +A3(i;l) (1/k)311 End for12 For m = 1 to k3 (k3 is the number of 3-stepneighborhoods of node i)13 Compute the probability that the node itransmits informa
21、tion to the node m14 fASP_im = A3(i;m) (1/k)315 End for16 fASP_i = sum(fASP_ij) +sum(fASP_il)+sum(fASP_im)17 End for208901-3万方数据物理学报Acta Phys. Sin. Vol. 66, No. 20 (2017) 208901式中A代表网络邻接矩阵, A3(i;j)表示节点i与节点j之间长度为3的所有可达路径, A3(i;j) -|n(i)| - |n(j)| + 1为消除可达路径中的回路后剩下的路径数, |n(i) n(j)|表示节点i与节点j的共同邻居数,即长度为
22、2的路径数.对于二步邻居节点,fASP_ij = |n(i) n(j)| (1/k)2+ A3(i;j) (1/k)3 : (8)对于节点i的二步邻居节点j,节点i和节点j之间不存在长度为3且有回路的路径,因此节点i到节点j的可达路径数为A3(i;j).对于三步邻居节点,fASP_ij = A3(i;j) (1/k)3 : (9)以图1中节点i与节点c为例说明ASP计算过程.节点i到节点c路径长度为2的路径有3条,路径长度为3的路径有4条,根据ASP指标,可计算节点i成功传递信息至节点m的可能性为3(1/k)2 + 4(1/k)3,同理,可依次计算节点i传递信息至节点j;h;g与a的可能性,由
23、此得到节点i的影响力值.为降低计算复杂度, SP指标只考虑三步内的邻居节点.与SP指标相比, ASP指标多考虑了节点与一步邻居中长度为2和3的可达路径以及与二步邻居中长度为3的可达路径.尽管如此,通过表1中的算法框架依然可以看出,改进指标几乎不增加计算的复杂度.3评价标准为了衡量各种指标影响力排序结果的准确性,采用SIR模型37;38对传播过程进行模拟.在SIR模型中,节点存在三种状态: 1)易染状态S,个体易被感染,但还未被感染; 2)感染状态I,个体已经被感染; 3)恢复状态R,个体被感染后以概率 被治愈,治愈后对该疾病免疫,不再被感染.不失一般性,本文所有SIR模型实验都设 = 1.使用
24、SIR模型验证所提算法评价节点影响力的准确性.将网络中任意一个节点设为感染状态I,作为初始传播源,其余节点设为易感状态S,在每个时间步中,处于状态I的节点以传播率 尝试感染处于状态S的邻居节点,并且自身以概率 = 1恢复成状态R,重复此过程直至网络中没有处于状态I的节点.定义节点的实际传播影响力 (i) = 1MMm=1(i),其中M表示实验重复次数, (i)表示节点i作为传播源,一次传播实验中网络中处于状态R的节点总数.实验采用Kendall tau相关系数39;40衡量各指标排序结果的准确性,其表达式为(R1;R2) = nc - nd(nt - nu)(nt - nv); (10)式中R
25、1与R2表示n个节点的两种不同排序序列,nc和nd分别表示两种排列的同序对和异序对的个数, nt = n(n - 1)/2, nu =si=1ui(ui - 1)/2,nv =ti=1vi(vi - 1)/2. nu与nv分别针对序列R1与R2计算,以nu为例(nv的计算类推),将R1中的相同元素组成小集合, s表示序列R1中拥有的小集合数, ui表示第i个集合所包含的元素数.由不同的评估指标得到节点的影响力值序列,同时根据SIR模型传播过程得到各个节点影响节点数,按照相同次序构成另一等级序列,利用Kendall tau相关系数进行准确性计算, 值越高,表明评估指标的结果与SIR模型仿真结果越
26、接近,评估结果越准确.4真实数据集实验结果为了验证各指标评估节点传播影响力的效果,实验选取6个真实数据集,包括Word,Netscience41, Email42, Yeast43, Blog44和Router45,这些网络的拓扑结构统计特征如表2所列.其中, N与M分别表示网络节点数与连边数,C表示网络集聚系数, D为网络直径, 表示传播概率, th = k/k2表示传播阈值,其中k表示节点平均度, k2表示节点二阶平均度.表2 6个真实网络的拓扑参数Table 2. Topological parameters of six real networks.网络名N M th k C DWor
27、d 112 425 0.08 0.073 7.59 0.173 5Netscience 379 914 0.13 0.125 4.82 0.741 17Email 1133 5451 0.06 0.054 9.62 0.570 8Yeast 1458 1948 0.15 0.140 2.67 0.071 19Blog 3982 6803 0.08 0.073 3.42 0.284 8Router 5022 6258 0.08 0.073 2.49 0.033 15在6个真实网络数据集和3个模拟数据集上,比较提出的ASP指标与SP指标、度指标、核数指标、介数中心性指标以及接近中心性指标.图2描述
28、了不同网络中心性指标与实际影响力 (i)之间208901-4万方数据物理学报Acta Phys. Sin. Vol. 66, No. 20 (2017) 2089010 5 10 15 20 25 30 35 40 45 500246810 Degree0 5 10 15 20 25 30 3502468101214Degree0 20 40 60024681012 Degree0 1000 2000 30000246810 BC0 1 2 3 4 5 602468101214 BCNumber of SIR infected nodes/1041 2 3 4024681012 BCNumbe
29、r of SIR infected nodes/1050.3 0.4 0.5 0.60246810CC0.10 0.15 0.20 0.2502468101214CC0.10 0.15 0.20024681012 CC5 100246810 SP0 2 4 6 8 10 12 1402468101214SP0 20 40 60024681012SP0 50 100 150 200 250 3000246810iCnc0 20 40 60 80 10012014016002468101214Cnc0 20 40 60 80024681012Cnc0 5 10 15 20 250246810 AS
30、P0 5 10 15 20 25 3002468101214ASPNumber of SIR infected nodes Number of SIR infected nodes Number of SIR infected nodesNumber of SIR infected nodes Number of SIR infected nodes Number of SIR infected nodesNumber of SIR infected nodes Number of SIR infected nodes Number of SIR infected nodesNumber of
31、 SIR infected nodes Number of SIR infected nodes Number of SIR infected nodesNumber of SIR infected nodesNumber of SIR infected nodesNumber of SIR infected nodes Number of SIR infected nodes0 20 40 60024681012 ASP(a) (b) (c)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)图2六个真实网络中不同指标评估值与SIR模型
32、感染节点数的相关性(a) Word; (b) Netscience; (c) Yeast; (d) Email;(e) Blog; (f) RouterFig. 2. Correlation between dierent ranking values and number of SIR model infected nodes in six real-worldnetworks: (a) Word; (b) Netscience; (c) Yeast; (d) Email; (e) Blog; (f) Router.208901-5万方数据物理学报Acta Phys. Sin. Vol. 6
33、6, No. 20 (2017) 2089010 20 40 600102030405060 Degree0 40 80 120 160051015202530 Degree0 20 40 60 80 100 12005101520253035 Degree0 1 2 3 4 50102030405060 BCNumber of SIR infected nodes/1040 1.0 2.0 3.0 4.0051015202530 BCNumber of SIR infected nodes/1050.10 0.15 0.20 0.2505101520253035 CC0.2 0.3 0.40
34、102030405060 CC0.15 0.20 0.25051015202530 CC0 1 2 3 4 5 6 705101520253035 BCNumber of SIR infected nodes/1060 5 10 15 20 250102030405060 SP0 50 100 150051015202530 SP0 50 100 150 200 250 300 35005101520253035 SP0 100 200 300 400 500 6000102030405060 Cnc0 100 200 300 400 500 600051015202530Cnc0 50 10
35、0 150 200 250 300 35005101520253035 CncNumber of SIR infected nodes Number of SIR infected nodes Number of SIR infected nodesNumber of SIR infected nodes Number of SIR infected nodes Number of SIR infected nodesNumber of SIR infected nodes Number of SIR infected nodes Number of SIR infected nodesNum
36、ber of SIR infected nodes Number of SIR infected nodes Number of SIR infected nodesNumber of SIR infected nodes Number of SIR infected nodes Number of SIR infected nodes0 10 20 30 40 500102030405060ASP0 50 100 150 200 250 300 350051015202530ASP0 200 400 600 800 1000 120005101520253035 ASP(d) (e) (f)
37、(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)(i)图2六个真实网络中不同指标评估值与SIR模型感染节点数的相关性(续) (a) Word; (b) Netscience; (c) Yeast; (d)Email; (e) Blog; (f) RouterFig. 2. Correlation between dierent ranking values and number of SIR model infected nodes in six real-worldnetworks (continued): (a) Word; (b) N
38、etscience; (c) Yeast; (d) Email; (e) Blog; (f) Router.208901-6万方数据物理学报Acta Phys. Sin. Vol. 66, No. 20 (2017) 208901的相关性,相关程度越高,表明算法对节点传播影响力的测量越准确.由于节点的影响力由最终被感染的网络节点数量决定,因此为了正确评价节点的真实影响力,感染概率 的值不宜选得过大或过小,若 值过小,信息传播容易局限于节点邻域.相反,若 值过大,不论传染过程从哪个节点发起,整个网络都很快被感染,很难区分单个个体的影响力.为保证传播能够进行,实验设定感染概率 等于网络传播阈值 t
39、h, SIR实验独立运行1000次取平均结果.从图2可以看出,接近中心性和介数中心性指标与SIR影响节点数的相关性相对较弱,接近中心性与SIR影响节点数总体呈正相关,介数中心性的结果较为发散.这是因为社会化网络的社区化使得0 0.02 0.04 0.06 0.08 0.10 0.12 0.14 0.160.60.70.80.9Degree Cnc SP BCCC ASP Semilocal (a)0.06 0.08 0.10 0.12 0.14 0.16 0.18 0.200.20.30.40.50.60.70.80.9 (b)0 0.02 0.04 0.06 0.08 0.10 0.12 0
40、.14 0.160.60.70.80.9(c）0.06 0.08 0.10 0.12 0.14 0.16 0.18 0.20 0.220.40.50.60.70.80.9(d)0 0.02 0.04 0.06 0.08 0.10 0.12 0.14 0.160.30.40.50.60.70.80.9 (e)0.00 0.02 0.04 0.06 0.08 0.10 0.12 0.14 0.160.30.40.50.60.70.80.9 (f)图3 (网刊彩色)不同指标评估准确性对比(a) Word数据集; (b) Netscience数据集; (c) Email数据集; (d) Yeast数据
41、集; (e) Blog数据集; (f) Router数据集Fig. 3. (color online) Comparison of accuracy evaluation among various indices: (a) Word; (b) Netscience; (c) Email;(d) Yeast; (e) Blog; (f) Router.208901-7万方数据物理学报Acta Phys. Sin. Vol. 66, No. 20 (2017) 208901绝大多数节点的介数很小,通过介数进行影响力排序,节点间区分度不大,而实际上网络中介数相近的节点的传播能力存在较大差异. SP
42、指标、核数中心性和ASP指标的评估值与SIR影响节点数则呈现较强的正相关性,其中ASP指标的相关性结果比SP指标好,可见ASP指标在评价节点传播影响力时具有优势.在相关性实验中,信息传播率为网络传播阈值,实验结果只体现特定传播率下的相关性情况.为了更全面地评价各个指标在不同传播率下的排序准确性,设置传播率区间为| th|-7%;| th|+7%(若 th 0:07,传播率区间取为0:01;0:15),并且将 值作为准确性度量值进行实验,结果如图3所示.从图中可以看出,传播率较小时核数指标准确率普遍较高,这是由于核数指标考虑了节点度与核数,当传播率较小时,从源节点发起的SIR传播过程容易局限于局
43、部邻域,此时节点度越大感染到的节点也越多,核数指标正好适合这一情况.当传播率在传播阈值附近时,除了Router网络, ASP指标的准确性比其他指标高,这是因为传播率适中时,节点局部高聚簇性能够使节点获得更多的将信息扩散出去的途径, ASP指标充分考虑了这种因素.当传播率更大时,可以发现ASP指标的优势与SP指标相比在逐渐削弱,这是因为传播率大到一定程度时,信息可以轻易地扩散出去,此时节点的局部聚簇性对信息的扩散作用并不明显.在Router网络中,由于网络结构较为稀疏,节点间的冗余链接少,因此ASP指标与SP指标的实验结果相差不多.5模拟数据集上的实验结果除了真实数据集,实验还使用了Lancic
44、hinetii-Fortunato-Radicchi (LFR)46数据模型生成的人工数据集.通过设置不同的LFR参数,可以生成不同拓扑特征的网络结构.设置LFR参数如下:N = 2000, cmin = 20, cmax = 50, kmax = 30,= 0:1,其中N为网络节点数, cmin和cmax分别代表社区的最小和最大规模, kmax表示网络的最大度, 为混合参数.调整平均度k来调节网络的紧密程度,分别生成k = 5, 10, 15的三个网络数据集.三个模拟数据集上的实验结果如图4所示,实验结果证明随着网络稀疏性与信息传播率的变化,ASP指标与SP指标对节点影响力排序的相对准确性也
45、发生变化.在k = 5与k = 10的LFR数据集中,传播率较小时, SP指标略优于ASP指标,这个结果与真实数据集上的原因类似,都是因为传播率偏小时节点的真实影响力接近于度;当传播率更大时, ASP指标相比其他指标有明显的优势.尤其在集聚程度高的网络中,如图4(c)所示, ASP指标在不同传播率下比SP指标更具有优势.0 0.02 0.04 0.06 0.08 0.10 0.12 0.14 0.160.20.30.40.50.60.70.80.9 (a)0 0.02 0.04 0.06 0.08 0.10 0.12 0.14 0.160.40.50.60.70.80.91.0(b)Degre
46、e Cnc SPBC CC ASP0 0.02 0.04 0.06 0.08 0.10 0.12 0.14 0.160.40.50.60.70.80.9(c)图4 (网刊彩色) LFR模拟数据集上各指标影响力排序准确性对比(a) k = 5; (b) k = 10; (c) k = 15Fig. 4. (color online) Comparison of accuracy eval-uation among dierent centralities on three LFRdatasets: (a) k = 5; (b) k = 10; (c) k = 15.208901-8万方数据物理学
47、报Acta Phys. Sin. Vol. 66, No. 20 (2017) 2089016考虑不同阶次内的邻居对算法排序结果的影响最后比较了ASP算法考虑不同阶次内邻居时的排序效果,考虑到(1/k)l随着l的增大会快速衰减,因此对于4阶及4阶以上的邻居,只将其最短路径纳入计算范围.结果如图5所示,算法效果并不总是随着阶次的提高而变好,大多在3阶处取得最优.可见考虑更高阶的邻居,只会增大算法的计算复杂度,对算法精度的提升帮助并不大,因此ASP算法只将节点与邻域节点间三步内的邻居纳入计算范围.1 2 3 4 5 6 70.30.40.50.60.70.80.9WordNetscienceYea
48、stEmailBlogRouter图5 (网刊彩色)不同阶次内邻居对算法排序结果的影响(S表示算法中邻居节点的最高层级)Fig. 5. (color online) The eect of neighbors in dif-ferent orders on the results of algorithm sorting (Srepresents the highest order of neighbor nodes in thealgorithm).7结论准确度量复杂系统中节点的传播影响力,对于控制流言在网络中的传播、预防网络攻击、设计有效的广告投放策略等具有现实意义.综合考虑节点与三步内邻居间的有效可达路径以及信息传播率,本文提出了一种SP指标的改进算法, ASP算法.在同样只考虑三步内邻居的条件下,与SP指标相比, ASP指标几乎不增加算法复杂度.在多个真实数据集和人工数据集上的实验证明,本文提出的指标可以在更广的信息传播率下取得更为准确的排序结果.本文算法对于理解节点局部聚簇性对节点传播影响力的影响具有一定