科学网如何找到网络中的超级传播者

的评价）。后来，这两条路线都有很多改进的方法（从文章的引用和验证思路可以看出主要参考的是哪篇论文），然后逐渐融合成第一个问题。

最近有一些工作，分别就这两种方法提出了一些改进的策略和指标。就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]针对传染病借助航空网络传播的真实情况，考虑了网络交通的空间组织和层次结构，提出了名为空间传播中心性（geographic spreading centrality）的指标，该指标能够很好预测到哪些节点能够在传播中发挥更重要的结论。陈端兵等人最近一些比较系统的实验发现（尚未发表），如果一个节点的传播能力和度的函数关系可以调整，那么在不同的参数空间中，取得“胜利”的排序算法并不一致。尽管还是有规律可循，但是这个规律比较复杂。Borge-Holthoefer和Moreno指出[14]，针对一般的谣言传播动力学，用coreness效果就不佳。其中使用的动力学是spreader-ignorant-stifler模型（这个模型也是Moreno在2004年提出的，老人们应该还比较熟悉），这个模型中spreader遇到ignorant以一定概率传播，spreader遇到spreader或者stifler则以一定概率变成stifler。这个模型往细里看，还可以进一步分成两类：一类是每个spreader每个时间步随机选择一个邻居接触，就变成了熟悉的contact process；一类是每个spreader每个时间步原则上可以和所有邻居接触，但是是一个一个接触，一旦它变成了stifler，就停止，这就是truncated process。这两类效果也不相同。在上面的模型中，如果允许ignorant直接变成stifler，那么coreness和传播能力之间又变得明显相关了[15]。Borge-Holthoefer等人[15]还指出，在考虑了用户活跃性的情况下，活跃性的分布，活跃性的分配方式等等，都会对coreness与传播能力的相关性产生非常明显的影响。

唯一solid的结果是，Borge-Holthoefer等人[15]指出，在Twitter真实的传播事件中（西班牙骚乱事件），coreness和传播能力是明显正相关的。但是，这种正相关其实不值一提，因为深入实证分析显示[16]，coreness还不如度更能找到最容易导致大规模信息爆发的节点。尽管作者指出[16]，coreness也有一个好处，就是最大的coreness对应的节点多，所以一次就能找到很多个，在我看来，这实在称不上是一个好处。由于模型和实际存在距离，除了类似陈端兵做苦力，搞清楚背后细致的规律外，找到更多实证的线索是特别有价值的！

参考文献：

[1] M. Kitsak, L. K. Gallos, S. Havlin, F.Liljeros, L. Muchnik, H. E. Stanley, H. A. Makes, Identification of influentialspreaders in complex networks, Nature Physics 6 (2010) 888-893.

[2] L. Lu, Y.-C. Zhang, C. H. Yeung, T.Zhou, Leaders in Social Networks, the Delicious Case, PLoS ONE 6 (2011) e21202.

[3] J.-G. Liu, Z.-M. Ren, Q. Guo, Rankingthe spreading influence in complex networks, Physica A 392 (2013) 4154-4159.

[4] Q. Hu, Y. Gao, P. Ma, Y. Yin, Y. Zhang,C. Xing, A New Approach toIdentify Influential Spreaders in Complex Networks, LNCS 7923 (2013) 99-104.

[5] A. Zeng, C.-J. Zhang, Ranking spreaders by decomposing complex networks,Physics Letter A 377 (2013) 1031-1035.

[6] Q. Li, T.Zhou, L. Lu, D.-B. Chen, Identifying Influential Spreaders by WeightedLeaderRank, arXiv: 1306.5042.

[7] D.-B. Chen,R. Xiao, A. Zeng, Y.-C. Zhang, Path diversity improves the identification ofinfluential spreaders, arXiv: 1305.7480.

[8] K. Klemm, M.A. Serrano, V. M. Equiluz, M. S. Miguel, A measure of individual role incollective dynamics, Scientific Reports 2 (2012) 292.

[9] F. Bauer, J.T. Lizier, Identifying influential spreaders and efficiently estimating infectionnumbers in epidemic models: a walk counting approach, EPL 99 (2012) 68007.

[10] B. Hou, Y. Yao, D. Liao, Identifying all-around nodes for spreadingdynamics in complex networks, Physica A 391 (2012) 4012-4017.

[11] N. A. Christakis, J. H. Fowler, Social Network Sensors for Early Detectionof Contagious Outbreaks, PLoS ONE 5 (2010) e12948.

[12] X. Zhang, J. Zhu, Q. Wang, H. Zhao, Identifying influential nodes incomplex networks with community structure, Knowledge-Based Systems 42 (2013)74-84.