《一种有效的基于三角结构的复杂网络节点影响力度量模型-韩忠明.pdf》由会员分享，可在线阅读，更多相关《一种有效的基于三角结构的复杂网络节点影响力度量模型-韩忠明.pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、物理学报Acta Phys. Sin. Vol. 65, No. 16 (2016) 168901一种有效的基于三角结构的复杂网络节点影响力度量模型 韩忠明1)2)y陈炎1)李梦琪1)刘雯1)杨伟杰1)1)(北京工商大学计算机与信息工程学院,北京100048)2)(食品安全大数据技术北京市重点实验室,北京100048)(2016年5月10日收到; 2016年6月15日收到修改稿)度量复杂网络中的节点影响力对理解网络的结构和功能起着至关重要的作用.度、介数、紧密度等经典指标能够一定程度上度量节点影响力, k-shell和H-index等指标也可以应用于评价节点影响力.然而这些模型都存在着各自的局
2、限性.本文基于节点与邻居节点之间的三角结构提出了一种有效的节点影响力度量指标模型(local triangle centrality, LTC),该模型不仅考虑节点间的三角结构,同时考虑了周边邻居节点的规模.我们在多个真实复杂网络上进行了大量实验,通过SIR模型进行节点影响力仿真实验,证明LTC指标相比于其他指标能够更加准确地度量节点的传播影响力.节点删除后网络鲁棒性的实验结果也表明LTC指标具有更好效果.关键词:复杂网络,节点影响力,三角结构,关键节点PACS: 89.75.Hc DOI: 10.7498/aps.65.1689011引言复杂网络的结构、功能以及两者间的联系一直以来都是网络科
3、学的一个重要研究领域1 4,识别复杂网络中高影响力节点对于复杂网络中的结构、传播以及同步等机理有着重要的理论意义5 7,对理解网络中信息、疾病和谣言等传播和控制、新产品的市场推广营销等应用有着非常实用的价值8;9.度量复杂网络节点影响力从网络科学的诞生起就获得了研究者的大量关注,最直观的指标是度中心性(degree centrality)10.度中心性能一定程度上度量节点的影响力,然而度中心性并没有考虑节点在网络中所处的位置和邻居节点的影响力.度值相同的两个节点,若其中一个节点的邻居节点影响力都很大,另一个都很小,则这两个节点的影响力显然差异很大. Chen等11结合节点的度和其邻居节点的度提
4、出了局部中心性(local cen-trality),该指标对节点影响力的度量效果较之度有了很大的提高.闵磊等12认为度中心性只有在传播率较小的情况下才有较好的影响力度量效果,通过对当前节点的邻居节点度的累加进一步扩展了节点度,提出了扩展度(exdegree)指标. Fowler和Christakis13提出的三度影响力原则认为节点不仅可以影响与节点直接相邻的节点,还能间接影响与邻居节点相邻的节点,三度以内都可能产生影响.基于节点度的指标忽略了节点间的结构和节点在网络中所处的位置.介数中心性和紧密中心性是复杂网络中两种经典的中心性指标,介数中心性(betweenness cen-trality
5、)14定义为网络中任意两个节点之间的最短路径经过该节点的次数,介数中心性描述的是信息国家自然科学基金(批准号: 61170112)、教育部人文社会科学研究基金项目(批准号: 13YJC860006)和北京市教委科学研究面上项目(批准号: KM201410011005)资助的课题.通信作者. E-mail: 2016中国物理学会Chinese Physical Society http:/168901-1物理学报Acta Phys. Sin. Vol. 65, No. 16 (2016) 168901在网络中传播时经过节点的繁忙程度,若移除介数大的节点,则可能会造成网络拥堵,不利于信息在该网络
6、中的传播.紧密中心性(closeness central-ity)15则能够表达节点到达网络其他节点的快慢程度,节点的紧密度越大,则其与网络中其他所有节点平均路径长度越短.复杂网络中节点的群聚现象16引起了研究节点影响力的相关学者的大量关注,并从节点的聚类系数与网络的社团结构两个角度去研究节点影响力,节点的聚类系数可以反映节点的邻居节点间联系的紧密程度. Chen等17则从节点获取新邻居节点的能力角度验证了聚类系数对节点影响力的作用.许多真实网络存在着明显的群聚现象通过社团划分算法3可以把网络中的节点划分到多个社团中,在多个社团之间起到桥梁作用的节点其影响力较大,研究者18通过结合节点所连接的
7、社团数量和传统中心性指标来挖掘网络中最有影响力的节点,此类算法的缺点是依赖于社团划分,算法复杂度较高,且在社团数量较少的网络中效果不明显.研究者19;20在影响力度量模型中引入结构洞理论来挖掘连接多个群体的影响力大的节点.然而,此类算法对于一些存在联系紧密的多个核心节点的网络影响力度量效果并不好. Zhang等21提出了一种VoteRank算法用来识别网络中多个最具影响力的节点,并将这些节点作为种子节点能使影响力在大范围内传播.基于随机游走的影响力度量典型方法有PageRank22, HITS23以及LeaderRank等6.针对PageRank存在排序结果不惟一的缺陷, Li等6对此改进并提
8、出了LeaderRank算法.在原有网络上增加一个对所有节点双向连接的节点,解决了排序不惟一的问题,并利用排序结果找到网络最具影响力的节点. Li等24通过加权对LeaderRank算法进行了改进. HITS算法同时考虑节点的中心和权威性的排序方法.基于随机游走的影响力方法用邻居节点来刻画节点的影响力,在避免噪声的同时却忽略了节点自身的性质. Kitsak等25对社交网络研究时发现高介数或者度值大的节点不一定是最有影响力的节点.并利用k核分解将节点在位置上从边缘层到核心层分为不同的核数层,认为核心节点(核数值较大的节点)才是影响力大的节点25;26.然而,由于网络中可能有局部联系很紧密的小团体
9、,核数值较大的节点未必是网络的核心节点,多个核数值相同的节点影响力也有可能差距很大.研究者27;28针对此问题进行了改进, H指数是常见的评价学者或期刊影响力的指标, L等29研究发现H指数在度量复杂网络中节点传播影响力有很好的效果,并且证明了度、H指数以及核数之间的关联,且H指数对节点影响力的度量比核数有了明显的提升.综合分析节点影响力研究的相关成果,可以看出好的影响力度量指标必须同时考虑节点在网络中所处的位置和节点周边邻居节点的规模大小.三角结构(triangle)是复杂网络中的一种重要结构特征,但利用三角结构度量节点影响力研究却很少见, Kitsak等25通过k-shell分解去寻找网络
10、中的核心节点,认为网络中的核心区域节点之间通常连接更加紧密,网络边缘区域节点连接则相对稀疏.三个节点两两相互连接,形成一个稳定的三角结构.三角结构具有很高的稳定性.节点与其邻居节点间的三角结构数量多少可以衡量其与邻居节点之间的紧密程度,节点与其邻居节点形成的三角结构数量越多,则他们连接越紧密.然而只考虑节点与其邻居节点之间的结构并不能体现节点所处团体的规模大小,三度影响力等理论认为节点不仅可以影响其邻居节点,还能有效影响邻居节点的邻居节点,为了更加精确度量节点的影响力,还需要考虑邻居节点的度信息,这样能避免局部紧密小团体成为“伪核心”的问题.基于以上思想,本文结合节点与邻居节点之间的三角结构和
11、邻居度提出了一种新颖的节点影响力度量指标(local trianglecentrality, LTC),该指标同时考虑了节点与邻居节点的结构和数目特征. LTC具有简单、快速、有效的特性,能够用来在大规模网络上快速计算节点的影响力,在此基础上通过排序可以挖掘出复杂网络中最具影响力的节点.2 LTC影响力度量模型用无向图G = (VE)表示复杂网络的拓扑结构, V是图G中节点的集合E是边的集合jV j = n,jEj = m,分别表示图G中有n个节点和m条边,节点v的度可表示为k(v) =u2Vev;u,其中ev;u =8xj且xi yj,或xi xj且xi yj则认为这两个元素是不一致的;若x
12、i = xj且xi = yj这两个元素既不是一致的也不是不一致的.肯德尔相关系数 定义为(X;Y) = C D(1/2)n(n 1);其中C代表XY任意两个元素对中拥有一致性元素对的数量, D代表XY中不一致的元素对的数量, 的取值范围在 11之间,当 为1时认为两个序列完全正相关, 取时不相关, 取 1时完全负相关.3.4数据集为了客观评价模型的有效性和适用性,我们选取了7个公开的不同规模的复杂网络数据集.Karate网络为空手道俱乐部网络, Jazz网络是一个爵士音乐合作网络, Facebook网络为科学家合作网, Netscience网络为原始公开数据集网络中的最大联通子集, Email
13、网络为洛维拉 依维尔基里大学成员之间的邮件交互网络, Blog网络为MSN博客空间中博主之间的交流网络, CA-HepPH网络为高能物理领域科学家合作网络.表4所示为实验采用的各真实复杂网络的基本特征,其中n为真实复杂网络的节点数量, m为边的数量, k为平均度, d为平均距离, c为节点的平均聚类系数, c为SIR模型中节点的感染率.表4真实网络的基本特征Table 4. The basic characteristics of the real networks.Network n m k d c cKarate 34 78 4.588 2.408 0.571 0.147Jazz 198
14、2742 27.697 2.235 0.617 0.026Facebook 324 2218 13.691 3.054 0.466 0.048Netscience 379 914 4.823 6.042 0.741 0.142Email 1133 5451 9.622 3.606 0.22 0.056Blog 3982 6803 3.417 6.227 0.284 0.078CA-HepPH 12008 118521 19.74 5.212 0.611 0.0074实验结果与分析4.1节点影响力度量指标和真实传播影响力相关性分析首先通过3.1节中的SIR模型对真实复杂网络中单个节点的传播影响力
15、进行仿真实验,然后比较168901-5物理学报Acta Phys. Sin. Vol. 65, No. 16 (2016) 168901节点的各指标值与节点的传播影响力相关性.实验中在模拟节点的传播过程时,取单个节点作为初始传播源,经t时间后达到稳态(即整个网络中不存在处于感染态的节点),用F(t)表示单个节点的实际传播影响力, F(t)表示网络中处于免疫态的节点的数量.对于单个节点重复独立实验1000次, F(t)的最终取值为1000次实验的均值.图3是不同指标在真实网络上与节点传播影响力F(t)的关系,纵坐标为F(t)的值,横坐标为归一化后的指标值.其中核数、H指和LTC指标未作归一化.如
16、图3(a)图3(f)所示,在Facebook网络中节点的LTC值和H指标值相对于其他指标与节点的真实影响力的相关性更高,度值、介数值和核数大的节点其真实影响力并不一定大.如图3(g)图3(i)所示,在Netscience网络中除了LCT指标外其他指标都出现了两个问题:指标值大的节点真实影响力却很小,和相同指标值的多个节点真实影响力差异较大.如图3(m)图3(r)所示,在Email网络中只有核数指标效果较差,其他指标效果表现较好.在Email网络中核数最大的节点真实影响力并不是最大,类似结果在图3(v)Blog网络中也明显体现. Email网络的节点平均聚类系数较小,故网络中的核心节点并不是连接
17、最紧密的节点,而LTC指标不仅考虑了节点邻居节点的紧密程度,且考虑周边节点的规模大小,因此适用于不同特性的复杂网络.在Email网络中,只有度和LTC指标能够找到真实影响力最大的节点.从真实网络的实验结果上可以看出,度中心性、紧密中心性、核数、H指以及LTC指标和节点的传播影响力大致都呈现出正相关的趋势,即指标值越大,节点的真实传播能力越强.而介数和节点的传播影响力之间的相关性并不强,且介数值较大的节点其传播影响力并不一定大,在多个网络中都存(a) Facebook (b) Facebook (c) Facebook(d) Facebook (e) Facebook (f) Facebook(
18、g) Netscience (h) Netscience (i) Netscience0.055 10 15 5 10 15 20 25 0 0.2 0.4 0.6 0.8 1.0Degree Betweenness ClosenessCloseness H-index LTCDegree Betweenness Closeness0.10 0.15 0.0500.02 0.04 0.06 0.08 0 0.10 0.20 0.30 0.40 0.12 0.16 0.20 0.240.10 0.15 0.25 0.30 0.35 0.40 0.452015Ft1052015Ft1052015F
19、t1052015FtFt1052015Ft1052015Ft105161412810642Ft161412810642Ft161412810642图3节点影响力与6种指标的相关性Fig. 3. The correlation between the inuence of nodes and the six indexes.168901-6物理学报Acta Phys. Sin. Vol. 65, No. 16 (2016) 168901(j) Netscience (k) Netscience (l) Netscience(m) Email (n) Email (o) Email(p) Emai
20、l (q) Email (r) Email(s) Blog (t) Blog (u) Blog(v) Blog (w) Blog (x) Blog5 10 15 20 25 0 0.2 0.4 0.6 0.8 1.00 0.2 0.4 0.6 0.8 1.0Closeness H-index LTCDegree Betweenness ClosenessCloseness H-index LTCDegree Betweenness ClosenessCloseness H-index LTC2 3 4 5 6 7 8 2 3 4 5 6 7 8 0.020 0.04 0.06 0.08 0.1
21、00.25 0.30 0.35 0.400.012 4 6 8 102 4 6 8 10 12 142 3 4 5 6 70.03 0.05 0 0.01 0.02 0.03 0.040.01 0.02 0.03 0.04 0 0.1 0.2 0.3 0.16 0.18 0.20 0.22 0.24 0.26FtFt16141281064240302010FtFt4030201030252010155Ft30252010155FtFt16141281064240302010FtFt4030201030252010155Ft30252010155FtFt16141281064240302010F
22、tFt4030201030252010155Ft30252010155图3节点影响力与6种指标的相关性(续)Fig. 3. The correlation between the inuence of nodes and the six indexes (Continued).168901-7物理学报Acta Phys. Sin. Vol. 65, No. 16 (2016) 168901在类似问题.同样度数和核数较大的节点的传播能力也不一定很强,在Facebook和Netscience网络中存在多个度数较大传播影响力却很小的节点,核数值较大节点影响力却很低的现象在Email和Blog网络中尤
23、为明显,网络中局部连接过于紧密的小团体的存在导致其核数较大但真实影响力却很小的现象在此处得到了很好的验证.然而在LTC指标中则不存在这个问题,因为其不仅考虑了节点与周边节点的联系紧密程度,还考虑了周边邻居节点的规模大小.此外,观察Netscience和Blog网络上的结果,度中心性、紧密中心性、核数和H指数这四个指标存在一个共同问题,指标值相同的多个节点,其传播影响力却拥有很大的差异,紧密中心性和H指数指标在不同网络表现优劣不同,在Facebook和Email网络中表现较好,其他网络则较差.在图3中4个网络上, LTC值相同的多个节点其影响力差异很小, LTC指标和单个节点真实影响力表现出良好
24、的线性相关性,比其他指标效果更好.表5详细列出了度中心性、紧密中心性、核数、H指以及LTC指等指标与节点的传播影响力F(t)的肯德尔系数,肯德尔系数越大说明节点的指标与真实网络中的传播影响力相关性越强,也就表明指标的影响力度量效果越好.从表中可以看出LTC指标在所有网络中拥有最佳或接近最佳效果. H指数相对于核数有了明显的提高,仅次于LTC介数的效果最差.肯德尔系数的结果表明LTC在不同网络上的适用性最好.表5在6种不同规模真实网络中,节点影响力与各指标的肯德尔相关系数 Table 5. Kendall correlation coecient values in six real netwo
25、rks with dierent scale.网络Netscience Facebook Jazz Email Blog CA-HepPHDegree 0.611 0.789 0.824 0.787 0.595 0.719Betweenness 0.389 0.365 0.469 0.63 0.58 0.403Closeness 0.343 0.717 0.725 0.813 0.485 0.704Coreness 0.563 0.769 0.797 0.81 0.576 0.667H-index 0.609 0.814 0.858 0.818 0.589 0.566LTC 0.831 0.8
26、81 0.912 0.866 0.767 0.6894.2影响力度量指标差异分析为了进一步分析LTC与各指标影响力度量效果差异性,将LTC与介数中心性和H指数分别在4个代表网络上的单个节点影响力进行了对比性分析.图4所示是LTC与介数中心性的对比结果.图4横坐标代表节点LTC指标值,纵坐标为对比指标值,颜色坐标代表节点通过SIR仿真实验获取的传播影响力大小.如图4(a),图4(b)和图4(d)所示在Facebook,Netscience和Blog网络中介数值最大的节点的真实影响力并不是最大,甚至比较小.并且介数值相近的不同节点其影响力变化范围较大.而在4个网络中, LTC指标最大的节点影响力都
27、是最大,并且LTC值相近的节点影响力变化都很稳定.在Email网络中,节点平均聚类系数较小,网络中节点的群聚现象不明显.如图4(c)所示,节点的介数和LTC指标表现出高度的一致性,节点影响力度量效果都较好.综合在4个网络中的表现, LTC指标对节点影响力度量效果更好.图5所示是LTC与H指数的对比结果.如图5(a)和图5(c)所示,在Facebook和Email网络中LTC和H指数的效果都很好.如图5(b)所示,在Netscience网络中, H指数为8的多个节点影响力波动范围较大.如图5(d)所示,在Blog网络中H指数值最大的节点影响力并不是最大,而LTC度量出高影响力的个体节点处于网络的
28、核心位置,所以与传播影响力具有较高的一致性,波动很小.因此, LTC指标对节点影响力的度量效果比H指数更加精确.168901-8物理学报Acta Phys. Sin. Vol. 65, No. 16 (2016) 168901(a) Facebook (b) Netscience(d) Blogc) Email20.017.515.012.510.07.55.02.51412108642322824201612844035302520151050.150.400.350.300.250.200.150.100.0500.100.050.0400.0350.0300.0250.0200.0150
29、.0100.00500 0.2 0.4LTC0.6 0.8 1.0 0 0.2 0.4LTC0.6 0.8 1.00 0.2 0.4LTC0.6 0.8 1.00 0.2 0.4LTC0.6 0.8 1.00.300.250.200.150.100.0500BetweennessBetweennessBetweennessBetweenness图4 (网刊彩色) LTC和介数在4个代表网络中的影响力度量效果对比Fig. 4. (color online) Eect comparison of LTC and Betweenness in 4 representative networks.(a
30、) Facebook (b) Netscience(d) Blogc) Email20.02520151052514876543212108642201510517.515.012.510.07.55.02.51412108642322824201612844035302520151050 0.2 0.4LTC0.6 0.8 1.0 0 0.2 0.4LTC0.6 0.8 1.00 0.2 0.4LTC0.6 0.8 1.00 0.2 0.4LTC0.6 0.8 1.0H-indexH-indexH-indexH-index图5 (网刊彩色) LTC和H指数在4个代表网络中的影响力度量效果对比
31、Fig. 5. (color online) Eect comparison of LTC and H-index in 4 representative networks.168901-9物理学报Acta Phys. Sin. Vol. 65, No. 16 (2016) 1689014.3鲁棒性分析复杂网络中节点的影响力不仅体现在节点的传播能力上,对于一些网络通过攻击网络中的少量节点可以使整个网络分崩离析最终“瘫痪”.因此,移除节点对于网络鲁棒性的影响也是衡量节点影响力的一个重要方面.通过移除网络中部分节点,考虑网络结构的变化来衡量被移除的那部分节点的重要性.网络的变化越大,说明这部分节点
32、越重要.用不同指标对节点影响力进行降序排序,然后按序移除i/n比例的节点,用 (i/n)表示网络剩余节点中属于最大联通集的比例.若 (i/n)值越小,说明网络中孤立的单个节点或小团体越多,则移除i/n比例的那部分节点越重要.与节点的传播影响力度量方式不同,度量节点对网络鲁棒性的重要性更加倾向于介数值大的那些在网络中处在“繁忙”位置的节点,移除网络中处于紧密连接位置的节点并不会造成网络的分裂,而移除那些“桥梁”节点会使整个网络分裂为多个部分,导致网络崩溃.此时节点与邻居节点之间的三角结构数量无疑起到的作用是负面的.根据上述分析,我们对LTC指标中的参数进行修正, (2)式中S(x) = (1 +
33、x) 1,即一个节点与其邻居节点之间三角结构数量越多,则移除这个节点对于网络的破坏性越小. 的取值为0,与节点的传播能力不同,邻居节点的度值此时起到的作用并不明显,在度量节点的位置重要性时并不需要考虑邻居节点的度值.画出i/n与 (i/n)在二维坐标上的曲线,从而可以分析节点移除后的影响33.图6所示为不同规模和不同节点平均聚类系数的4个真实复杂网络中按各指标降序排序后,按序移除(i/n)比例的节点与剩余节点中占网络中最大联通集的比例 (i/n)关系,图6横坐标表示移除比例,纵坐标表示 (i/n)值.(a) FacebookLTCDegreeBetweennessH-indexClosenes
34、sCoreness LTCDegreeBetweennessH-indexClosenessCorenessLTCDegreeBetweennessH-indexClosenessCorenessLTCDegreeBetweennessH-indexClosenessCoreness1.01.00.80.80.60.60.40.40.20.20tin1.00.80.60.40.20tin1.00.80.60.40.20tin1.00.80.60.40.20tinin0 1.00.80.60.40.2in01.00.80.60.40.2in0 1.00.80.60.40.2in0(b) Jazz
35、(d) Email(c) Netscience图6 (网刊彩色)移除i/n比例节点与剩余节点中最大联通集的比例关系图Fig. 6. (color online) Ratio of giant component to remaining nods after removing i/n nodes on four repre-sentative networks.如图6(a)所示, Facebook网络中LTC指标在移除10%部分左右节点后, (i/n)值率先迅速下降,而其他指标要移除30%左右才开始明显下降,说明在Facebook网络中LTC指标对节点重要性的度量效果比其他指标更好,所识别的大
36、影响力节点对网络的鲁棒性影响更加显著.如图6(b)所示,在Jazz网络中和在Facebook网络中拥有类似的结果.但是在移除网络中接近一半数量的节点后, (i/n)值才会开始下降, Jazz网络自身的鲁棒性较好,网络中的核心节点的数量较多.如图6(c)所示,在168901-10物理学报Acta Phys. Sin. Vol. 65, No. 16 (2016) 168901Netscience网络中只需要移除很少的一部分节点该网络就已经四分五裂. Netscience网络的鲁棒性较差,其网络核心节点较少,且一旦这部分节点遭到攻击整个网络就会瘫痪.在Netscience网络中,度、介数和LTC指
37、标的节点影响力度量要比H值、核数和接近中心性指标要好.Email网络的规模相对于其他3个网络规模较大,但是其平均聚类系数却最低.如图6(d)所示,在Email网络中各指标效果较为接近.由于平均聚类系数较小,整个网络中节点连接较为稀疏,因此攻击网络中少量节点并不能够立即使网络陷入瘫痪.在其他真实网络中,实验结果与这4个代表网络情况类似.综合分析实验结果,在多个真实网络上,介数和LTC指标都拥有较好的节点影响力度量效果,介数和LTC指标能够很好地挖掘网络中的核心节点和连接不同团体的“桥梁”节点.然而介数的算法时间复杂度要远大于LTC指标.度中心性在不同网络中效果差异较大,在Netscience和E
38、mail网络中度中心性的效果能够接近LTC指标和介数的效果,而在Facebook和Jazz网络中度中心性的效果较差,度中心性在不同网络中的适用性较差.其他指标在所有网络中效果都不如前者,所以LTC指标相比于其他指标能够更加快速、准确地识别复杂网络中高影响力的节点.5结论度量复杂网络中节点影响力是复杂网络研究的一个关键科学问题.本文巧妙地利用三角结构这一局部特征去区分节点在网络中的全局位置.核心区域通常由多个联系紧密的节点组成,而边缘区域节点之间连接则相对稀疏.节点与其邻居节点形成的三角结构数量越多,则他们连接越紧密,三角结构数量能反映节点在网络中所处的位置.同时为了避免将“伪核心”(局部联系紧
39、密的小团体)视为核心区域,进一步考虑邻居节点的度,即节点所处位置的周边环境,在此基础上提出了一种新颖的节点影响力度量指标LTC.在多个公开真实复杂网络上进行了大量实验,通过SIR模型验证了LTC指标对节点的传播影响力度量更准确,且时间复杂度较低,可以应用于大规模复杂网络.通过节点删除法对三角结构在度量节点对整个网络鲁棒性的重要程度上所起作用进行了探索,节点删除法的实验结果也表明了LTC指标具有较好效果.分析多个节点影响力和传播的关系时,多个影响力大的节点同时作为种子节点进行感染时,感染范围可能会有重叠区域,所以如何结合节点影响力和网络结构分析多个节点的影响力,从而使得影响力最大化是进一步的研究
40、方向.参考文献1 Watts D J, Strogatz S H 1998 Nature 393 4402 Barabsi A L, Albert R 1999 Science 286 5093 Newman M E J, Girvan M 2004 Phys. Rev. E 69 0261134 Klemm K, Serrano M , Eguluz V M, Miguel M S2012Sci. Rep. 2 2925 Motter A E, Lai Y C 2002 Phys. Rev. E 66 0651026 L L Y, Zhang Y C, Yeung C H, Zhou T 2
41、011 PloS One6 e212027 Pei S, Makse H A 2013 J. Stat. Mech. Theory Exp. 2013120028 Pastor-Satorras R, Vespignani A 2002 Phys. Rev. E 650361049 Morone F, Makse H A 2015 Nature 524 6510 Bonacich P 1972 J. Math. Sociol. 2 11311 Chen D, L L, Shang M S, Zhou T 2012 Physica A: Stat.Mech. Appl. 391 177712 M
42、in L, Liu Z, Tang X Y, Chen M, Liu S Y 2015 ActaPhys. Sin. 64 088901 (in Chinese) 闵磊,刘智,唐向阳,陈矛,刘三女牙2015物理学报64 08890113 Fowler J H, Christakis N A 2008 BMJ 337 a233814 Newman M E J 2005 Social Networks 27 3915 Sabidussi G 1966 Psychometrika 31 58116 Palla G, Barabsi A L, Vicsek T 2007 Nature 446 6641
43、7 Chen D B, Gao H, L L Y, Zhou T 2012 PloS One 8e7745518 Zhao Z Y, Yu H, Zhu Z L, Wang X F 2014 Chin. J.Comput. 37 753 (in Chinese) 赵之滢,于海,朱志良,汪小帆2014计算机学报37 75319 Su X P, Song Y R 2015 Acta Phys. Sin. 64 020101 (inChinese) 苏晓萍,宋玉蓉2015物理学报64 02010120 Han Z M, Wu Y, Tan X S, Duan D G, Yang W J 2015Ac
44、ta Phys. Sin. 64 058902 (in Chinese) 韩忠明,吴杨,谭旭升,段大高,杨伟杰2015物理学报64 05890221 Zhang J X, Chen D B, Dong Q, Zhao D B 2016 arXiv1602 0007022 Berkhin P 2005 Internet Mathematics 2 7323 Kleinberg J M 1999 JACM 46 60424 Li Q, Zhou T, L L Y, Chen D B 2014 Physica A: Stat.Mech. Appl. 404 4725 Kitsak M, Gallos
45、 L K, Havlin S, Liljeros F, Muchnik L,Stanley H E, Makse H A 2010 Nat. Phys. 6 88826 Pei S, Muchnik L, Andrade J J S, Zheng Z M, HernnA M 2014 Sci. Rep. 4 554727 Liu J G, Ren Z M, Guo Q 2013 Physica A: Stat. Mech.Appl. 392 4154168901-11物理学报Acta Phys. Sin. Vol. 65, No. 16 (2016) 16890128 Zeng A, Zhan
46、g C J 2013 Phys. Lett. A 377 103129 L L Y, Zhou T, Zhang Q M, Stanley H E 2016 Nat.Commun. 7 1016830 Hethcote, Herbert W 2000 SIAM Rev. 42 59931 Pastor S R, Castellano C, Van M P, Vespignani A 2015Rev. Mod. Phys. 87 92532 Shu P, Wang W, Tang M, Do Y 2015 Chaos 25 06310433 Iyer S, Killingback T, Sund
47、aram B, Wang Z 2013 PloSOne 8 e59613An ecient node inuence metric based on triangle incomplex networks Han Zhong-Ming1)2)y Chen Yan1) Li Meng-Qi1) Liu Wen1) Yang Wei-Jie1)1)(Beijing Technology and Business University, Beijing 100048, China)2)(Beijing Key Laboratory of Big Data Technology for Food Sa
48、fety, Beijing 100048, China)( Received 10 May 2016; revised manuscript received 15 June 2016 )AbstractInuential nodes in large-scale complex networks are very important for accelerating information propagation,understanding hierarchical community structure and controlling rumors spreading. Classic centralities such as degree,betweenness and closeness, can be used to measure the node inuence. Other systemic metrics, such as k-shell andH-index, take network structure into account to identify inuential nodes. However, these methods suer some drawbacks.For example, bet