Evaluation Method of Importance for Nodes in Complex Networks Based on Importance Contribution
ZHANG Xiping1,2, LI Yongshu1, LIU Gang1, WANG Lei1
1. Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University, Chengdu 610031, China; 2. Chongqing University of Posts and Telecommunications Software Engineer College, Chongqing 400065, China
Abstract：We introduce the concept of m-order neighbors and propose an evaluation method of vital node for complex networks based on importance contribution of m-order neighbors.Two parameters α and γ are defined for adjusting the dependences of node importance evaluation on the node itself and m-order neighbors. This method considers the importance contribution of the node itself and m-order neighbors. In order to characterize the efficiency of this method, ARPA network is adopted to evaluate the node importance with different values of m. The results shows that, compared with the degree method, betweenness method and node deletion method, our algorithm is more precise to evaluate the node importance, which can observably distinguish the importance discrepancy of the nodes on the complex networks and precisely extract the vital nodes. Meanwhile, the results also reveal an important dynamic phenomenon that when the value of m is more than the average path length L of the network, our method can derive reliable and high precise evaluation results.
张喜平, 李永树, 刘刚, 王蕾. 节点重要度贡献的复杂网络节点重要度评估方法[J]. 复杂系统与复杂性科学, 2014, 11(3): 26-32.
ZHANG Xiping, LI Yongshu, LIU Gang, WANG Lei. Evaluation Method of Importance for Nodes in Complex Networks Based on Importance Contribution[J]. Complex Systems and Complexity Science, 2014, 11(3): 26-32.
[1] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393:440-442. [2] Barabási A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286:509-512. [3] Boccaletti S, Latora V, Moreno Y, et al. Complex networks:structure and dynamics[J]. Phys Rep, 2005, 424:175-30. [4] Newman M E J. Networks:an Introduction[M]. Oxford:Oxford University Press, 2010:23-45. [5] Albert R, Barabási A L. Statistical mechanics of complex networks[J]. Rev Mod Phys, 2002, 74（1):47-97. [6] Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45:167-256. [7] Strogatz S H. Exploring complex networks[J]. Nature, 2001, 410（6825):268-476. [8] Holme P, Saramäki J. Temporal networks[J]. Phys Rep, 2012, 519（3):97-125. [9] 刘刚, 李永树. 基于引力场理论的复杂网络路由选择策略研究[J]. 物理学报, 2012, 61（24):248901. Liu Gang, Li Yongshu. Routing strategy for complex networks based on gravitation field theory[J]. Acta Phys Sin, 2012, 61（24):248901. [10] 周漩, 张凤鸣, 李克武, 等. 利用重要度评价矩阵确定复杂网络关键节点[J]. 物理学报, 2012, 61（5):050201. Zhou Xuan, Zhang Fengming, Li Kewu, et al. Finding vital node by node importance evaluation matrix in complex networks[J]. Acta Phys Sin, 2012, 61（5):050201.[11] Carlson J M, Doyle J. Highly optimized tolerance:robustness and design in complex systems[J]. Phys Rev Lett, 2000, 84（11):2529-2532. [12] Carlson J M, Doyle J, Complexity and robustness[J], PNAS, 2002, 99（Suppl.1):2539-2545. [13] 刘刚,李永树,杨骏,等. 对偶图节点重要度的道路网自动选取方法[J]. 测绘学报,2014,43（1):97-104. Liu gang,Li Yongshu,Yang Jun,et al.Auto-selection method of road networks based on evaluation of node importance for complex traffic network[J].Acta Geodaetica et Cartographica Sinica,2014,43（1):97-104. [14] Murray S, Mark W. Knotty-centrality:finding the connective core of a complex network[J]. PLoS ONE, 2012, 7（5):e36579. [15] Brin S, Page L. The anatomy of a large-scale hyper textual web search engine[J]. Computer Networks and ISDN Systems, 1998, 30（1-7):107-117. [16] Kleinberg J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM, 1999, 46（5):604-632. [17] Restrepo J R, Ott E, Hunt B R. Characterizing the dynamical importance of network nodes and links[J]. Phys Rev Lett, 2006, 97（9):094102. [18] Barthelemy M. Betweenness centrality in large complex networks[J]. Eur Phys J B, 2004, 38（2):163-168. [19] Lohmann G, Margulies D S, Horstmann A, et al. Eigenvector centrality mapping for analyzing connectivity patterns in fMRI data of the human brain[J]. PloS One, 2010, 5（4):e10232. [20] Jin J, Xu K, Xiong N, et al. Multi-index evaluation algorithm based on principal component analysis for node importance in complex networks[J]. IET Networks, 2012, 1（3):108-122. [21] Zhang J, Xu X K, Li P, et al. Node importance for dynamical process on networks:a multiscale characterization[J]. Chaos, 2011, 21（1):016107. [22] 陈勇, 胡爱群, 胡啸. 通信网中节点重要性的评价方法[J]. 通信学报, 2004, 25（8):129-134. Chen Yong, Hu Aiqun, Hu Xiao. Evaluation method for node importance in communication networks[J]. J China Institue Commum, 2004, 25（8):129-134. [23] 赵毅寰, 王祖林, 郑晶, 等. 利用重要性贡献矩阵确定通信网中最重要节点[J]. 北京航空航天大学学报, 2009, 35（9):1076-1079. Zhao Yihuan, Wang Zulin, Zheng Jing, et al. Finding most vital node by node importance contribution matrix in communication networks[J]. J Beijing University of Aeronautics and Astronautics, 2009, 35（9):1076-1079. [24] Freeman L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40（1):35-41. [25] Crucitti P, Latora V, Porta S. Centrality in networks of urban streets[J]. Chaos, 2006, 16（1):015113.
