从网络中寻找最有影响力的节点，最近几年是个有热门的话题，因为其理论和应用价值都很大。有兴趣的朋友，可以参考我8月份的博文“如何找到网络中的超级传播者”，里面列出了最近的主要文献。链接http://blog.sciencenet.cn/blog-3075-717780.html

现在我们处理的网络规模非常大，社交网络动辄就是上亿节点，所以局部化的算法往往实战效果好。这方面陈端兵等人提出过简单而有效的方法[Chen, D., Lü, L., Shang, M. S., Zhang, Y. C., & Zhou, T. (2012).Identifying influential nodes in complex networks. Physica A: StatisticalMechanics and its Applications, 391(4), 1777-1787]，方法虽然是针对无向网络的，但是很容易推广到有向网络。

最近，陈端兵、高辉、吕琳媛等人合作，进一步挖掘在局部结构中隐含的信息，从而再次提高有影响力节点挖掘的准确度[Chen, D. B., Gao, H., Lü, L., & Zhou, T. (2013). IdentifyingInfluential Nodes in Large-Scale Directed Networks: The Role of Clustering. PLOSONE, 8(10), e77455]。我们很多工作，不管是链路预测、个性化推荐还是节点影响力排序，都带着一个信念，就是对网络演化规律的深刻了解会帮助提出更好的算法。这篇文章也是从这个角度出发设计算法的。

我们注意到最近的两篇工作，[Mislove, A., Marcon, M., Gummadi, K. P.,Druschel, P., & Bhattacharjee, B. (2007, October). Measurement and analysisof online social networks. In Proceedings of the 7th ACM SIGCOMM conferenceon Internet measurement (pp. 29-42). ACM]和[Ugander, J., Backstrom, L., Marlow, C.,& Kleinberg, J. (2012). Structural diversity in social contagion. Proceedingsof the National Academy of Sciences, 109(16), 5962-5966]，暗示簇系数对于节点获取新的邻居似乎是不利的。着一个结论比较直观，因为簇系数大说明交往的圈子比较窄，可能这个圈子里面的朋友也就这么些了。我们首先做了一个非常干净的实验（精细化程度不如Kleinberg小组2012年PNAS），但是说明问题更清楚，就是看所有度为5的节点（簇系数各有不同），看看不同簇系数下，它们在给定时间段内吸收新节点的能力。如下图所示，非常明显，簇系数越大的节点，吸引新节点的能力越差（两个实验网络分别是arXiv:cond-mat/科学家合作网络，无向的；与短消息网络，有向的，后者很大）.

结合刚才的实证结果和以前关于clustering对传播动力学negative影响的研究，我们认为clustering coefficient大对于一个节点的影响力来说，是一个负面的因素（这里面逻辑其实有些不妥之处，但是这个嘛，有时候也很难说清楚，所以搞计算机的，都是hypothesis之后看效果，我们已经算比较爱讲故事来龙去脉的了），于是可以用这个clustering coefficient加权，当然，越大越不好。

具体的方法细节，包括如何利用SIR传播模型验证我们方法的有效性等等，都请参考全文链接：http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0077455。总之效果是有了明显提高，而且这个方法很快捷。上亿的网络上还当真没用过这个方法，但是千万级别的随便跑，我印象中文章里面用的网络也有900多万节点。

---- 特别强调，这些算法好坏受动力学影响很大，所以适用性(applicability)是个大问题----

---- 附上以前的讨论----

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