这个问题显然重要，但是2010年以前似乎一直没有成为受到复杂网络研究圈关注的问题，因为按照度(degree)，介数(betweenness centrality)这些指标进行排序，效果应该已经非常好了。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（2年引用才42次，远不如我最初的期望），不过有其深刻之处（感兴趣的读者可以参考陆君安老师http://blog.sciencenet.cn/blog-211414-541021.html和吕琳媛博士http://blog.sciencenet.cn/blog-329471-459892.html的评价）。后来，这两条路线都有很多改进的方法（从文章的引用和验证思路可以看出主要参考的是哪篇论文），然后逐渐融合成第一个问题。

最近有一些工作，分别就这两种方法提出了一些改进的策略和指标。就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.

[13] C. Nicolaides, L. Cueto-Felgueroso, M. C. Gonzalez, R. Juanes, A Metric ofInfluential Spreading during Contagion Dynamics through the Air TransportationNetwork, PLoS ONE 7 (2012) e40961.

[14] J.Borge-Holthoefer, Y. Moreno, Absence of influential spreaders in rumor dynamics,Physical Review E 85 (2012) 026116.

[15] J. Borge-Holthoefer, S. Meloni, B. Goncalves, Y. Moreno, Emergence ofInfluential Spreaders in Modified Rumor Models, Journal of Statistical Physics(2012) 1-11.

[16] J. Borge-Holthoefer, A. Rivero, Y. Moreno, Locating privileged spreaders onan online social network, Physical Review E 85 (2012) 066123.