一种新的网络传播中最有影响力的节点发现方法*

胡庆成 尹龑燊 马鹏斐 高旸 张勇 邢春晓

(清华大学计算机系,信息技术研究院,清华信息科学与技术国家实验室,北京 100084)

(2013年1月25日收到;2013年3月25日收到修改稿)

1 引言

现实世界中的诸多系统都以复杂网络形式存在,比如互联网、社会系统、计算网络、生物网络和社交网络等.理解复杂网络的拓扑结构和功能是目前国际研究的热点.在很多科学领域中,都使用网中络用来节表点示代系表统人中,边成代员表之人间与的人关之系间,如的在联社系交.由网络于这些网络具有很高的复杂性,因此被称为“复杂网络(complex network)”[1-3],它已成为当前最重要的多学科交叉研究领域之一.在复杂网络中,找出最具影响力的节点[4-9]或意见领袖[10]在理论和现实应用中都有重大的意义,例如有效地控制疾病传播[11]、流言散布[12,13]、计算机病毒扩散,还可以传播新产品[14]、新思想[15]以推进社会化进程.

在社会网络分析中,常用“中心性(centrality)”来测量最有影响力的节点.文献[16,17]利用度中心性(degree centrality)来测量最有影响力的节点,在符合幂律的非均匀网络中,度数较大的hub节点的传播影响力应该相对较大,这也是目标免疫和熟人免疫策略的基本依据.文献[18]利用了介数中心性(betweenness centrality)来评价影响力,介数中心性是以经过某个节点的最短路径的数目来刻画节点的重要性.文献[19]提出PageRank算法来评价网页的重要性,它认为一个网页(节点)的重要性取决于其前向链接的数量与质量.文献[20,21]利用紧密度指标(closeness centrality)刻画某个节点到其他节点的难易程度.文献[22]提出通过K-shell(ks)[23]分解来确定最具有影响力的单源节点.

本文认为节点的影响力不只是由节点内部属性决定,而且其外部属性紧密相关,这与哲学范畴的内因和外因思想一致.内部属性如度数、紧密性、介数等中心化指标,外部属性如所属社区的大小、社区内关系紧密度等.社区[24,25]是一个有共同爱好的,或者位于一个共同地方的、或者同在某个工作场所的、或者具有家庭联系的群体[26].社区内的节点联系紧密,社区间的节点联系松散.

本文提出了KSC(K-shell and community centrality)指标模型.此模型不但考虑了节点的内部属性,而且还综合考虑了节点的外部属性,例如节点所属的社区特性等.然后利用SIR(susceptible-infected-recovered)模型对传播过程进行仿真,实验证明本文提出的方法可以更好地发现最具有影响力的节点.本文为这项具有挑战性研究提供了新的思想和方法.

2 相关研究

在社会网络中,发现最具有影响力的节点可以帮助我们有效地控制疾病传播、流言散布、计算机病毒扩散,还可以传播新产品、新思想以推进社会化进程.

图1 网络分析样例图

2.1 度中心化

度中心化[27,28]是一种最简单的方法,用于描述在静态网络中节点所产生的直接影响力.设网络G=(V,E)具有n=|V|个节点和m=|E|条边,节点v的度数是指与节点v连接的节点个数,用Cd(v)表示

其中d(v)称为该节点的度.如图1所示,尽管节点14度数最大为7,但作为初始节点,它最终的传播范围并不一定是最广泛的,因为它的邻居节点的度数都很小.

2.2 介数中心化

介数中心化刻画了网络中节点对于信息流动的影响力.节点v的介数[18]定义为

σst表示源节点s到目标节点t的最短路径数,σst(v)表示节点s经过节点v到目标节点t的最短路径数.

2.3 紧密度

紧密度[20,21]用于刻画节点到达其他节点的难易程度：

dG(s,t)表示源节点s到节点t的最短距离.

2.4 K-shell分解方法

K-shell给出了网络中节点重要性的一种粗粒化的划分,用Cks(v)表示.网络边缘节点的K-shell为1,然后往内像剥洋葱一样一层层进入网络的核心.首先去除网络中度数小于k的所有节点及其连边;如果在剩下的节点中仍有度值小于k的节点,那么就继续去除这些节点,直至网络中剩下的节点的度值不小于k.依次取k=1,2,3,···,就得到了该网络的K-shell分解.具体过程可参考图一.Kitsak等[22]实验研究表明,对于单个传播源感染率低的情形,度数大或者高介数的节点不一定是最有影响力的节点,而通过K-shell分解分析确定的网络核心节点(即K-shell值大的节点)才是最有影响力的节点;其研究表明,K-shell分解方法是一种比较好的影响力节点识别方法,可以更好地预测疾病等的传播.当传染病在网络的K-shell大的节点爆发时,病毒总是可以在网络核心通过许多种路径开始感染其他部分,无论该节点度数的大与小,这个结论都是有效的.这些通路的存在反过来也意味着如果以一个随机节点为源爆发疫情,有高K-shell值的节点更有可能早于其他节点被感染(疾病预测).

2.5 社区划分算法

社区[24,25]是一个有共同爱好的、或者位于一个共同地方的、或者同在某个工作场所的、或者具有家庭联系的群体[26].社区内的节点联系紧密,社区间的节点联系松散.社区划分(community detecting)的概念前期在Lin的论文[29]中提出.如图1,网络划分为4个社区(节点1—5,6—9,10—12,13—19).社区是复杂网络信息传播中最普遍和最重要的拓扑属性之一,信息在同一社区内传播迅速,而在社区之间传播缓慢.Kernighan-Lin(KL)算法[30]、快速Newman(FN)算法[31]和Guimera-Amaral(GA)算法[32]是经典的复杂网络社区划分算法.

本文使用了FN算法.FN算法是Newman提出的基于局部搜索的快速社区划分算法.其优化目标是极大化网络模块性(modularity)评价函数Q[26].FN算法属于聚合算法,它初始假定所有节点各自成为一个社区,然后每一步根据原有连接合并两个社区,计算Q值并记录下来,直到所有社区都被合并成为一个社区.最后根据记录下的Q值,找到最优的划分结果.

3 算法模型

我们认为节点的传播力不但与节点的内部自身属性有关,如度数、紧密度、介数、K-shell等,还与它的外部环境属性相关,如节点所处外部环境：社区大小,社区关联紧密度等.本文提出节点的影响力是由内因与外因同时决定的这一新颖思想和方法,即KSC中心化指标模型.模型符合哲学内因与外因对事物同样具有决定作用这一思想理念.

复杂网络G=(V,E)中,节点vo的KSC值定义如下：

其中 f internal(vo)为节点的内部影响力,f external(vo)为节点的外部影响力,α为内部影响因子,β为外部影响因子,且满足α+β=1,α和β可以根据实际网络结构与功能设定.

f internal(v o)定义如下：

其中,K(v)为节点内部属性值,可取度数、介数、紧密度和K-shell等节点自身属性,mv∈aVx(K(v))为归一化因子.

f external(v o)定义如下：

其中C为FN算法划分的社区集合,d(vo,c)为节点vo在社区c中的邻居节点的总个数,|c|为社区c的大小是归一化因子.

本文实验中α与β可以根据网络的拓扑结构设定;其中 finternal(vo)选取K-shell为内部属性,也可以为度数、紧密度和介数等,fexternal(vo)选取为社区属性,俗语“物以类聚,人以群分”说明社区内部节点之间有共同的兴趣爱好等,相似性更大.

表1给出了图1各节点的各种指标,如节点14度数最大,但是由于处在网络的边缘,所以最终影响力为2,而节点7虽然度数为6,但是它是其他几个社区连通的枢纽,结构洞[33,34]概念中重要节点.节点1—5虽然K-shell相同,但是节点1是2—5连接其他节点的桥接关系.从表1中可以看出各种方法得到的最具影响力节点排名各不相同.

表1 计算图一中节点的传播力

4 模型及实验分析

4.1 SIR模型

SIR模型在现实社会网络中已广泛应用于疾病传播、信息传播及谣言传播的研究.为了验证本文提出的模型,我们采用SIR模型[35-38]来模拟仿真传播过程,并将其结果与我们的模型实验结果做比较.

SIR模型中有三种状态,易感染状态S(susceptible),感染状态I(infected),免疫状态(recovered).当个体处于感染状态时,以β的概率感染处于易感染状态邻居个体,感染状态的节点以γ的概率恢复为免疫状态.

如果β值较大,节点传播能力很强,节点将很快感染整个网络,从而很难区分单个个体的重要性;较小的β能在有限时间内更好地显示出感染范围.本文中我们设定较小的β=0.04.

4.2 实验数据

考虑到不同的社会网络类型所代表不同的网络拓扑结构特性,我们选取了4个真实社会网络数据集[39]进行分析比较,表2给出各个网络的属性特征：1)Blogs网络数据[40],MSN博客空间中交流的关系网络;2)Netscience合著关系网络[41],选择了其中最大连通子图379个作者的关系网络;3)Router网络,数据是由Rocketfuel Project[42]收集的互联网中路由连接层级关系网络;4)Email网络[43],是洛维拉·依维尔基里大学成员邮件通信的关系网络.我们的模型也可应用于其他类型的复杂网络.

其中n是节点数,m为边数,〈k〉表示网络中平均度数据,max(k)为节点中最大度数,d为节点之间最短路径的平均数,max(Cks)为网络中最大的K-shell,C为整个复杂网络被划分的社区数.

表2 现实社会网络的属性情况

4.3 实验效果

我们应用章节4.1中所提到的SIR模型,对所提出的KSC指标与度、紧密性、介数和K-shell中心化指标进行了分析比较.实验模拟传播过程中,每次只选取网络中的一个节点作为初始传播节点,设定较短传播时间(t=10),对每个节点进行1000次重复实验取均值,最终感染与恢复的节点总数定义为影响力F(t).

图2 KSC模型中内部影响因子α与外部影响因子β取不同对传播影响力指标的影响分析

图2 表示了在KSC模型中选取不同的内部影响因子α与外部影响因子β(α+β=1)对结果的影响程度.哲学范畴中事物的运动和变化,是由它本身固有的内部矛盾引起的,又是同它所处的一定的外在条件相联系的,内因和外因在事物发展中的地位和作用是不同的.这与模型中内部影响因子α与外部影响因子β对传播影响假设完全一致.如在图2(c)中局部放大了最具影响力的前10位,当0≤α≤0.2,1≥β≥0.8,或1≥α≥0.8,0≤β≤0.2时可以看到,影响力曲线波动较大,影响力排名靠后的节点影响反而大.即只是单纯的考虑内部属性或外部属性对发现最具有影响的节点来说准确性,适用性较差.

经实验分析得出四种不同拓扑结构网络的内、外影响因子经验取值情况,如表3所示.可以看出在不同类型的网络结构中,内、外因所起的权重是不同的,本文实验中的α,β根据表3中取较好的经验值,这从另一方面证明了所提出模型的合理性及普遍性.

图3所表示的是在不同的网络中中心度指标与实际影响力之间的关系.

在Blogs网络中,度,K-shell,介数指标与影响力F(t)关系都不是很明显,例如在介数指标结果中,一些介数大的节点F(t)比一些介数很小的节点影响力还要低,但KSC指标可以较好地区分出最具影响力的节点.Email网络中,所有指标表现都较好,紧密度与KSC更为理想,这与网络的拓扑结构有关系.在Netscience网络中,介数衡量结果最差,紧密度,K-shell与节点F(t)影响力关系也不明显,KSC的效果要优于度数.在路由网络(Router)中K-shell与KSC结果接近,其他指标结果很难得到传播力较大的节点.总之,在不同的网络中传统的中心度指标各有优缺点,但是我们提出的KSC整体效果最好,都能有效地区分出最具有影响力的节点,通用性较强.

表3 内、外影响因子取值情况

图3 节点影响力分析比对,列代表5种不同中心化指标,行表示为4种不同的复杂网络环境,传播影响力F(t)(t=10),每个初始节点重复运行1000次取均值

对于单个传播源的情形,最具有影响力的节点并非度数最大的节点或者介数最大的节点,而是K-shell最大的节点,这一结论在Kitsak等[22]已在《Nature Physics》指出.图4比较了KSC与K-shell的实验效果,KSC比K-shell增加了外部属性的影响因素.例如在Email网络中,当K-shell为10时,传播影响力F(t)(t=10)并不稳定,而且变化范围较大,并且影响力随着KSC值的增大呈现增大趋势.在4种复杂网络中明显可以看出当KSC一定时F(t)相对稳定,颜色变化范围较小.

图4 KSC与K-shell指标在4种不同复杂网络中的分析比较,横轴表示KSC的指标值,纵轴表示K-shell的指标值,颜色坐标代表SIR模型仿真出的实际影响力大小F(t)

图5 比较了KSC与介数的实验效果.可出看出在Email网络中,KSC与介数表现正向同步较好,都能较好地发出最具影响力的节点,但在其他三个网络环境中KSC表现明显优于介数指标.实验结果表明KSC方法明显优于已有的4种典型方法.由此可见,考虑节点的外部属性对于找出最有影响力的节点意义重大,且具有较强的通用性,验证了我们所提出模型的合理性与普遍性.

如图6所示,在Blogs网络中,KSC曲线的某一点(x,y),横坐标表示此点用KSC指标值得出的排名为x,纵坐标表示此点在SIR仿真的实际影响力为y.理论上,一个好的指标方法应该表现为向右倾斜单调下降的曲线.因为对于一个好的指标方法,如果某个节点按该指标得出的排名越靠后,其实际影响力F(t)应该随之减小.

从图6结果中分析,可以看到已有的4种典型方法在不同网络中影响力均有所波动,这些方法在不同网络中各有优劣,通用性不强,特别是在影响力前10中波动范围最为明显.指标值小的传播影响力反而比指标值大的传播影响力要大,特别是在Blogs网络中,已有的4种指标方法结果都不太精确,而我们提出的KSC指标几乎在所有的网络中都符合向右倾斜单调下降的理论曲线.

本实验充分论证了节点影响力不但由内部属性决定,而且还与其外部属性密切相关,说明我们提出的KSC模型的合理性及普遍适用性.

图5 KSC与介数指标在4种不同复杂网络中的分析比较,横轴表示KSC的指标值,纵轴表示介数的指标值,颜色坐标代表SIR模型仿真出的实际影响力大小F(t)

5 结论

在复杂网络中发现最具影响力的节点,可以帮助我们提高新知识、新产品的传播效率,同时可以有效地制定相应的策略来阻止疾病及谣言传播.复杂网络中鉴别最具影响力的节点一直以来是研究的热点与难点,我们提出了KSC中心化指标模型.实验选取现实生活中常见的四种复杂网络博客网、邮件网、路由网和科学合著网,通过SIR模型模拟节点传播过程,并对各种中心化指标得出的影响力进行排序分析,验证了方法的高效性和正确性.

与传统的度、紧密度、介数和K-shell方法相比,传统方法在不同网络中各有优劣,通用性不强.而我们提出的KSC模型综合考虑了节点的内部属性与外部属性,实验证明用此方法鉴别节点的影响力要精确得多,适用范围更大.我们所提出的模型为这项具有挑战性研究提供了新的思想和方法.

感谢审稿人对本文提出的宝贵意见和建议,使得文章逻辑更加完整合理.

[1]Watts D J,Strogatz SH 1998 Nature393 440

[2]Barab´asi A L,Albert R 1999 Science 286 509

[3]Barab´asi A L,Albert R,Jeong H,Bianconi G 2000 Science287 2115a

[4]Pastor-Satorras R,Vespignani A 2002 Phys.Rev.E 65 036104

[5]Kempe D,Kleinberg J,Tardos E 2003 Proc.9th ACM SIGKDD Intl.Conf.on Knowledge Discovery and Data Mining New Washington,DC,USA,August 24—27,2003 p137

[6]Gomez-Rodriguez M,Leskovec J,Krause A 2010 Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Washington,DC,USA,July 25—28,2010 p1019

[7]Budak C,Agrawal D,El Abbadi A 2011 Proceedings of the 20th International Conference on World Wide Web Hyderabad,India,March 28—April 1,2011 p665

[8]Mislove A,Marcon M,Gummadi K P,Druschel P,Bhattacharjee B 2007 Proceedings of the ACM SIGCOMM 2007 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications Kyoto,Japan,August 27—31,2007 p29

[9]Yuan W G,Liu Y,Cheng J J 2013 Acta Phys.Sin.62 038901(in Chinese)[苑卫国,刘云,程军军2013物理学报62 038901]

[10]Weng J,Lim EP,Jiang J,He Q 2010 Proceedingsof the Third International Conferenceon Web Search and Web Data Mining,WSDM 2010 New York,NY,USA,February 4—6,2010 p261

[11]Xu D,Li X,Wang X F 2007 Acta Phys.Sin.56 1313(in Chinese)[许丹,李翔,汪小帆2007物理学报56 1313]

[12]Naveed N,Gottron T,Kunegis J,Alhadi A C 2011 Proceedingsof the 20th ACM International Conference on Information and Knowledge Management Koblenz,Germany,June 14—17,2011 p1

[13]Gu Y R,Xia L L 2012 Acta Phys.Sin.61 238701(in Chinese)[顾亦然,夏玲玲2012物理学报61 238701]

[14]Swamynathan G,Wilson C,Boe B,Almeroth K,Zhao B Y 2008 Proceedings of the First Workshop on Online Social Networks ACM New York,USA,August 18,2008 p1

[15]Mislove A,Marcon M,Krishna PG,Druschel P,Bhattacharjee B 2007 Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement(IMC’07)ACM New York,USA,October 24—26,2007 p29

[16]Albert R,Jeong H,Barabasi A L 2000 Nature406 378

[17]Pastor-Satorras R,Vespignani A 2001 Phys.Rev.Lett.86 3200

[18]Freeman L C 1977 Sociometry 40 35

[19]Brin S,Page L 1998 Comput.Netw.ISDNSyst.30 107

[20]Opsahl T,Agneessens F,Skvoretz J2010 Soc.Networks32 245

[21]Sabidussi G 1966 Psychometrika 31 581

[22]Kitsak M,Gallos L K,Havlin S,Liljeros F,Muchnik L,Stanley H E,Makse H A 2010 Tech.Rep.Phys.Soc.1001 5285

[23]Carmi S,Havlin S,Kirkpatrick S,Shavitt Y,Shir E 2007 Proc.Natl.Acad.Sci.USA 104 p1150

[24]Girvan M,Newman M EJ2002 Proc.Natl.Acad.Sci.USA 99 7821

[25]Fortunato S2010 Phys.Rep.486 75

[26]Newman M EJ,Girvan M 2004 Phys.Rev.E 69 026113

[27]Freeman L C 1979 Social Networks1 215

[28]Sabidussi G 1966 Psychometrika 31 581

[29]Lin K 1970 Bell Syst.Tech.J.49 291

[30]Newman M EJ2004 Phys.J.B 38 321

[31]Newman M EJ2004 Phys.Rev.E 69 066133

[32]Guimera R,Amaral L A N 2005 Nature 433 7028

[33]Burt R 2004 Am.J.Soc.110 349

[34]Granovetter M 1973 Am.J.Soc.78 1360

[35]Roy M Anderson,Robert M May 1992 Infectious Diseasesof Humans:Dynamicsand Control.(New York：Oxford University Press)p66

[36]Diekmann O,Heesterbeek JA P 2001 Mathematical Epidemiology of Infectious Diseases：Model Building,Analysisand Interpretation(New York：Wiley Seriesin Mathematical&Computational Biology)

[37]Hethcote H W 2000 Soc.Industr.Appl.Math.42 599

[38]Bernoulli D,Blower S 2004 Rev.Med.Virol.14 275

[39]Chen D B,Lu L Y,Shang M S,Zhang Y C,Zhou T 2012 Physica A 391 1777

[40]Xie N 2006 M.S.Dissertation(Bristo：University of Bristol)

[41]Newman M EJ2006 Phys.Rev.E 74 36104

[42]Spring N,Mahajan R,Wetherall D,Anderson T 2004 Acm.Sigcomm.Comp.Commu.Rev.32 3

[43]Guimer`a R,Danon L,D´ıaz-Guilera A,Giralt F,Arenas A 2003 Phys.Rev.E 68 065103