超级网络邻居

这个问题显然重要，但是2010年以前似乎一直没有成为受到复杂网络研究

圈关注的问题，因为按照度(degree)，介数(betweennesscentrality）这些指

标进行排序，效果应该已经非常好了.2010年8月，Kitsak等人[1］第一次系统

分析了这个问题。他们指出度和介数往往不能很精确描述一个节点的传播能力，

而利用k-core分解，一个节点的核数更好刻画了节点的传播能力。为了定义节

点的传播能力，Kitsak等人考虑了两个模型：在SIR模型中，一个节点i的传

播能力被定义为i为初始感染节点，平均传播的范围;在SIS模型中，一个极点

i的传播能力被定义为（稳态下）i被感染的概率.Kitsak等人也考虑了传播源

不止一个节点的情况,并给出了讨论，但是这个问题在他们的文章中并没有得到

很好的解决。Kitsak的工作影响很大，3年来引用200多次.很奇怪的是，这篇

文章我第一次读，觉得是一篇烂文章；后来读第二次，觉得有些意思；最近再拿

出来细读，觉得很有水平——这可能就是所谓的有长期影响的论文，并非应景之

作。

我们在2011年6月发表了一篇论文[2]，这篇论文的出发点和Kitsak等人不同，

是提出了一种新的排序算法LeaderRank，可以看作是PageRank的一种较大的改

进—-因为完全变成了没有参数的算法。除了比较鲁棒性、稳定性等等指标，为

了体现相比于PageRank的优势,我们考虑了由LeaderRank排序在前面的节点在

传播方面的能力是否强于由PageRank排序在前面的节点.这里使用的是传染能

力有限的SIR模型，衡量方式是看以一组节点为初始源，最终能够感染的节点数

目。遗憾的是，由于当时的出发点完全不是找超级传播者,所以没有引用Kitsak

的文章,比较方法也大不一样,现在看起来是应该引用的.这篇文章影响力不如

Kitsak后来,这两条路线都有很多改进的方法（从文章的引用和验证思路可以看

出主要参考的是哪篇论文)，然后逐渐融合成第一个问题。

最近有一些工作，分别就这两种方法提出了一些改进的策略和指标。就k核分解

的方法而言,刘建国等人[3]指出coreness相同的节点传播能力差距可能很大,

并提出了一种可以给出具有相同coreness的节点的传播能力排序，从而较

Kitsak等人的方法[1]有所进步。Hu等人［4]结合k—shell中心性和社区结构

提出了一个改良的指标，在SIR模型上进行了验证，较Kitsak等人的方法略佳.

曾安和张成军[5］考虑到了k核分解的剩余度，提出了一种改进的策略.就

LeaderRank而言，李倩等人［6］提出了含权的LeaderRank方法，较原来的结

果略有提高。陈端兵等人从局部传播路径的多样性出发，认为目标节点所有邻居

的度越是均匀，传播的效果越好，所以把邻居度序列的熵引入到了节点重要性的

刻画来。针对SIR模型，这个思路只有当一个节点传播的时候，每单位时间所接

触的邻居数目是该节点度的亚线性函数的时候才成立.

针对普适的线性动力学系统，也就是节点状态矢量的一阶导数可以写成由网络结

构和动力学参数决定的矩阵（不含时）左乘当前节点状态矢量，Klemm等人［8]

提出了利用该矩阵特征根决定的一个衡量节点在相应动力学重要性的指标（就是

矩阵最大特征值的右特征矢量中对应于每一个节点的值)。这个指标普适性很强,

但是有效性的验证还非常有限。和Klemm等人的思路类似,Bauer和Lizier［9]

通过计算疾病传播的所有可能路径，来对一个节点在SIS和SIR模型中的传播能

力进行评估——当然，通过一些近似的方法，可以降低计算量，否则这个算法实

在只能是停留在概念上。即便如此，目前还看不到Bauer和Lizier方法的优点，

因为原始的方法太慢，节省时间的方法似乎效果提高不显著。最近一个比较非主

流的工作是，Hou等人[10］考虑了多种节点中心性指标,提出了一个“综合的”

指标，这个指标更加稳定，也能够更好挖掘高传播能力的节点。他们也用SIR

模型进行了验证。

这个问题之所有重要，是因为上面提到的方法除了刻画传播过程和传播能力，还

可以应用到级联、交通、渗流、博弈、同步、控制（特别是牵制控制）等等领域，

这里就不一一介绍了。即便就传播来讲,也还可以有其他用途，譬如用来做首要

免疫对象的挖掘，传染病早期预警的社会传感器的搜寻（通过监控观察一小撮人，

早期并准确预知传播的趋势)，等等［11］.

目前这方面研究存在的最大的问题就是研究结果的适用范围-—很多看起来很棒

的结果，其实只是对一部分网络有用(网络特征对这个排序效果的影响分析不

够），或者只是对一部分动力学有用。举个例子来说，Kitsak等人的方法[1］

在包含社区网络结构的网络中似乎效果不佳[12],而这类网络需要新的节点传播

能力排序策略［4,12]。对于一些真实的需要考虑空间地里效应的系统，原来的

传统方法也存在不足。Nicolaides等人[13］针对传染病借助航空网络传播的真

实情况，考虑了网络交通的空间组织和层次结构，提出了名为空间传播中心性

（geographicspreadingcentrality)的指标，该指标能够很好预测到哪些节点

能够在传播中发挥更重要的结论。陈端兵等人最近一些比较系统的实验发现（尚

未发表)，如果一个节点的传播能力和度的函数关系可以调整,那么在不同的参数

空间中，取得“胜利”的排序算法并不一致。尽管还是有规律可循，但是这个规

律比较复杂。Borge—Holthoefer和Moreno指出［14]，针对一般的谣言传播动

力学，用coreness效果就不佳。其中使用的动力学是

spreader-ignorant-stifler模型（这个模型也是Moreno在2004年提出的,老

人们应该还比较熟悉），这个模型中spreader遇到ignorant以一定概率传

播,spreader遇到spreader或者stifler则以一定概率变成stifler。这个模型

往细里看，还可以进一步分成两类：一类是每个spreader每个时间步随机选择

一个邻居接触，就变成了熟悉的contactprocess；一类是每个spreader每个

时间步原则上可以和所有邻居接触，但是是一个一个接触，一旦它变成了

stifler,就停止,这就是truncatedprocess.这两类效果也不相同。在上面的模

型中，如果允许ignorant直接变成stifler，那么coreness和传播能力之间又

变得明显相关了［15］。Borge-Holthoefer等人［15］还指出，在考虑了用户

活跃性的情况下,活跃性的分布，活跃性的分配方式等等，都会对coreness与传

播能力的相关性产生非常明显的影响。

唯一solid的结果是，Borge-Holthoefer等人［15］指出，在Twitter真实的

传播事件中（西班牙骚乱事件），coreness和传播能力是明显正相关的.但是，

这种正相关其实不值一提，因为深入实证分析显示［16]，coreness还不如度更

能找到最容易导致大规模信息爆发的节点。尽管作者指出[16]，coreness也有

一个好处，就是最大的coreness对应的节点多，所以一次就能找到很多个，在

我看来，这实在称不上是一个好处。由于模型和实际存在距离，除了类似陈端兵

做苦力,搞清楚背后细致的规律外，找到更多实证的线索是特别有价值的!

参考文献：

[1]，L.K。Gallos,,os,L。Muchnik,H.E。

Stanley,H。A。Makes，Identificationofinfluentialspreadersincomplex

networks，NaturePhysics6（2010）888—893。

［2］,Y。—C。Zhang,,,LeadersinSocialNetworks,

theDeliciousCase，PLoSONE6（2011)e21202.

［3］J.—G。Liu,Z。-M。Ren,,Rankingthespreadinginfluence

incomplexnetworks,PhysicaA392(2013)4154—4159.

[4］,Y。Gao,P。Ma,，Y。Zhang,,ANewApproachtoIdentify

InfluentialSpreadersinComplexNetworks,LNCS7923(2013）99—104.

[5］A。Zeng,C。-J。Zhang，Rankingspreadersbydecomposingcomplexnetworks，

PhysicsLetterA377（2013）1031-1035.

[6］Q。Li,T。Zhou,，D.—B。Chen，IdentifyingInfluential

SpreadersbyWeightedLeaderRank，arXiv:1306。5042.

[7］D。—B。Chen,R。Xiao，,Y.—，Pathdiversityimproves

theidentificationofinfluentialspreaders,arXiv:1305。7480。

［8]K。Klemm,M.A。Serrano,z，M。S。Miguel，Ameasure

ofindividualroleincollectivedynamics,ScientificReports2(2012）

292.

[9］，，Identifyinginfluentialspreadersand

efficientlyestimatinginfectionnumbersinepidemicmodels：awalk

countingapproach,EPL99（2012）68007。

[10］B。Hou，,，Identifyingall-aroundnodesforspreadingdynamics

incomplexnetworks,PhysicaA391(2012）4012—4017。

［11]N。A。Christakis,J。，SocialNetworkSensorsforEarlyDetectionof

ContagiousOutbreaks,PLoSONE5(2010)e12948.

[12］,J。Zhu,,，Identifyinginfluentialnodesincomplex

networkswithcommunitystructure,Knowledge—BasedSystems42(2013)74-84.

[13]C。Nicolaides，—Felgueroso,ez,,AMetric

ofInfluentialSpreadingduringContagionDynamicsthroughtheAir

TransportationNetwork,PLoSONE7（2012）e40961.

[14］J。Borge-Holthoefer，Y。Moreno，Absenceofinfluentialspreaders

inrumordynamics,PhysicalReviewE85(2012)026116。

［15］J。Borge—Holthoefer,,B。Goncalves，Y。Moreno,Emergence

ofInfluentialSpreadersinModifiedRumorModels,JournalofStatistical

Physics(2012）1-11。

［16］-Holthoefer，，，Locatingprivileged

spreadersonanonlinesocialnetwork,PhysicalReviewE85（2012)066123.