引入m阶邻居节点的概念,提出了一种基于m阶邻居节点重要度贡献的复杂网络节点重要度方法,并引入α和γ两个参数,用于调节节点重要度评估对节点自身特性及m阶邻居节点的依赖程度。综合考虑了节点自身及1到m阶邻居节点的重要度贡献。为检验算法的有效性,采用ARPA网络拓扑并针对算法在不同m取值条件下的节点重要度情况进行了评估。评估结果显示,与度值法、介数法、节点删除法等评估方法相比,具有更高的评估精度,能显著地区分复杂网络中节点之间的重要性差异,能准确地确定网络中关键节点,保证节点重要度评估的准确性;此外,实验结果还揭示了一个重要动力学现象,即当邻居节点所考察的深度m值大于网络的平均路径长度L时,该方法可得到可靠且精度较高的评估结果。
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.
[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.
