借助引力模型,发现网络中的关键节点
周涛  |  2019-06-14  |  科学网  |  682次阅读

由于真实网络的异质性,节点在网络结构和功能上发挥的作用差异巨大。关键节点就是那些能够在更大程度上影响网络的结构与功能的一些特殊节点。准确挖掘网络中的关键节点,可以帮助我们更好地控制信息的传播、抑制疫情的爆发、精准投放商品广告、预测热门研究成果、发现重要致病基因等等。目前,大部分挖掘网络关键节点的方法都是基于网络结构化信息的,可粗略地分为基于邻居的中心性和基于路径的中心性[1]。其中,基于邻居的中心性的代表为:度中心性[2]H-指数[3]以及k-core分解方法[4]等;基于路径的中心性的代表为:接近中心性[5]和介数中心性[6]等。

 

受到万有引力公式启发,最近,汪秉宏教授研究组[7]提出了一种综合考虑节点邻居信息和路径信息的引力方法,其中节点的corenessk-core分解之后的shell值)被看做节点的质量。类似地,我们也提出了一种综合考虑节点邻居信息和路径信息的引力模型来评估网络节点的重要性[8]。度大的节点往往有更大的影响力,除此,节点对其邻近节点的影响更大。基于上述事实,我们可以将节点的度看作物体的质量,将节点间的最短距离看作物体间距离。这样,我们就可以利用节点与其他节点间的相互作用力来描述节点的影响力。很明显,有更多邻居且与大部分邻居都比较近的节点具有更强的影响力。

 

在此基础上,为了提高计算效率并且消除累积误差[9],我们通过只考虑截断半径内的节点间距离提出了局部引力模型。实验结果表明引力模型、局部引力模型以及[7]所提出的引力方法在识别节点的影响力方面要远远好于只考虑节点单一信息的经典方法(如度中心性、H-指数、k-core分解、介数中心性、接近中心性等),尤其是局部引力模型[8]G+方法[7]表现更优。因为局部引力模型是一种局部方法(只需要节点的度及r阶邻居信息即可),而G+方法是全局方法,从这个意义上讲,局部引力模型还更有优势。

 

截断半径的确定是局部引力模型一个亟需解决的问题,幸运地是,我们发现局部引力模型的最优截断半径近似于网络平均路径长度的一半,这使得在计算资源有限地情况下,我们可以通过该经验公式快速地预估最优截断半径的值。由于大部分真实网络具有小世界性质[10],因此最优截断半径一般不会很大。

 

[1] Lü, L., Chen, D., Ren, X. L., Zhang, Q. M., Zhang, Y. C., & Zhou, T. Vital nodes identification in complex networks. Physics Reports, 650, 1-63 (2016).

[2] Bonacich, P. Factoring and weighting approaches to status scores and clique identification. Math. Sociol., 2, 113–120 (1972).

[3] Lü, L., Zhou, T., Zhang, Q. M. & Stanley, H. E. The H-index of a network node and its relation to degree and coreness. Nat. Commun., 7, 10168 (2016).

[4] Kitsak, M. et al. Identification of influential spreaders in complex networks. Nat. Phys., 6, 888–893 (2010).

[5] Freeman, L. C. Centrality in social networks conceptual clarification. Soc. Networks, 1, 215–239 (1979).

[6] Freeman, L. C. A set of measures of centrality based on betweenness. Sociometry, 40, 35–41 (1977).

[7] Ma, L. L., Ma, C., Zhang, H. F. & Wang, B. H. Identifying influential spreaders in complex networks based on gravity formula. Physica A, 451, 205–212 (2015).

[8] Li, Z., Ren, T., Ma, X. Q., Liu, S. M., Zhang, Y. X. & Zhou, T. Identifying influential spreaders by gravity model. Scientific Reports, 9, 8387 (2019).

[9] Chen, D., Lü, L., Shang, M. S., Zhang, Y. C. & Zhou, T. Identifying influential nodes in complex networks. Physica A, 391, 1777–1787 (2012).

[10] Watts, D. J. & Strogatz, S. H. Collective dynamics of ‘small-world’ networks. Nature, 393, 440–442 (1998).

 

论文免费下载链接:

https://www.nature.com/articles/s41598-019-44930-9





文章原载于作者的科学网文章,所述内容属作者个人观点,不代表本平台立场。
本文经过系统重新排版,阅读原内容可点击 阅读原文