从大规模有向网络中找出最有影响力的节点:利用簇系数 精选

从大规模有向网络中找出最有影响力的节点:利用簇系数 精选

已有 36849 次阅读 2013-11-12 09:42 |系统分类:论文交流| 网络, 影响力

 

从网络中寻找最有影响力的节点,最近几年是个有热门的话题,因为其理论和应用价值都很大。有兴趣的朋友,可以参考我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小组2012PNAS),但是说明问题更清楚,就是看所有度为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-HolthoeferMoreno指出,针对一般的谣言传播动力学,用coreness效果就不佳。其中使用的动力学是spreader-ignorant-stifler模型(这个模型也是Moreno2004年提出的,老人们应该还比较熟悉),这个模型中spreader遇到ignorant以一定概率传播,spreader遇到spreader或者stifler则以一定概率变成stifler。这个模型往细里看,还可以进一步分成两类:一类是每个spreader每个时间步随机选择一个邻居接触,就变成了熟悉的contact process;一类是每个spreader每个时间步原则上可以和所有邻居接触,但是是一个一个接触,一旦它变成了stifler,就停止,这就是truncated process。这两类效果也不相同。在上面的模型中,如果允许ignorant直接变成stifler,那么coreness和传播能力之间又变得明显相关了。Borge-Holthoefer等人还指出,在考虑了用户活跃性的情况下,活跃性的分布,活跃性的分配方式等等,都会对coreness与传播能力的相关性产生非常明显的影响。

 

转载本文请联系原作者获取授权,同时请注明本文来自周涛科学网博客。

链接地址:
https://blog.sciencenet.cn/blog-3075-741054.html

上一篇:
互联网科学中心理论组组会(欢迎川内同行莅临指导)

下一篇:
复杂网络研究的机遇与挑战

收藏