基于传输效率矩阵的复杂网络节点重要度排序方法

摘要: 为了提高网络节点重要度评估的准确性，应用复杂网络理论，通过分析非邻接节点对节点重要度评估产生的重要影响，提出了一种基于网络传输效率矩阵的节点重要度排序方法.该方法综合了节点的局部重要性和全局重要性，弥补了节点重要度贡献只依赖于邻接节点的不足.在ARPA网络上对连续移除重要节点的连锁故障进行了仿真.结果表明，相比于节点重要度评价矩阵法，采用本文方法在移除最重要的2个节点后网络的最大连通子图规模降低了23.8%，该结果进一步验证了本文方法的准确性.
- 复杂网络 /
- 效率矩阵 /
- 重要度贡献 /
- 节点度
Abstract: In order to improve the accuracy of the node importance evaluation in complex networks, a novel evaluation method based on efficiency matrix was proposed through analysis of the impact of non-adjacent nodes on the node importance evaluation by using the complex network theory. This method combined both the local and global node importance comprehensively, and overcame the limitations of depending on just the adjacent nodes in the node importance evaluation. The cascading failures by removing important nodes on the ARPA network show that when the top 2 important nodes are removed, the size of the biggest subgraph based on the proposed method falls by 23.8% compared with that based on the node importance evaluation method, which further verifies the accuracy of the proposed method.
- complex networks /
- efficiency matrix /
- importance contribution /
- degree

HTML全文

参考文献(12)

CALLAWAY D S, NEWMAN M E J, STROGATEZ S H, et al. Network robustness and fragility: percolation on random graphs[J]. Phys. Rev. Lett., 2000, 85(25): 5468-5471.

BRIN S, PAGE L. The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks ISDN Systems, 1998, 30: 107-117.

KLEINBERG J M. Authoritative sources in a hyperlinked environment//Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA' 98, Society for Industrial and Applied Mathematics. Philadelphia:, 1998: 668-677.

CORLEY H W, SHA D Y. Most vital links and nodes in weighted networks[J]. Operations Research Letters, 1982, 1(4): 157-160.

NARDELLI E, PROIETTI G, WIDMAYER P. Finding the most vital node of a shortest path[J]. Theoretical Computer Science, 2001, 296(1): 167-177.

陈勇, 胡爱群, 胡啸. 通信网中节点重要性的评价方法[J]. 通信学报, 2004, 25(8): 129-134. CHEN Yong, HU Aiqun, HU Xiao. Evaluation method for node importance in communication networks[J]. Journal of China Institute Communications, 2004, 25(8): 129-134.

谭跃进, 吴俊, 邓宏钟. 复杂网络中节点重要度评估的节点收缩方法[J]. 系统工程理论与实践, 2006, 26(11): 79-83. TAN Yuejin, WU Jun, DENG Hongzhong. Evaluation method for node importance based on node contraction in complex networks[J]. Systems Engineering: Theory Practice, 2006, 26(11): 79-83.

CHEN Duanbing, LV Linyuan. SHANG Mingsheng, et al. Identifying influential nodes in complex networks[J]. Physica A, 2012, 391(4): 1777-1787.

陈静, 孙林夫. 复杂网络中节点重要度评估[J]. 西南交通大学学报, 2009, 44(3): 426-429. CHEN Jing, SUN Linfu. Evaluation of node importance in complex networks[J]. Journal of Southwest Jiaotong University, 2009, 44(3): 426-429.

赵毅寰, 王祖林, 郑晶, 等. 利用重要性贡献矩阵确定通信网中最重要节点[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]. Journal of Beijing University of Aeronautics and Astronautics, 2009, 35(9): 1076-1079.

周漩, 张凤鸣, 李克武, 等. 利用重要度评价矩阵确定复杂网络关键节点[J]. 物理学报, 2012, 61(5): 1-5. ZHOU Xuan, ZHANG Fengming, LI Kewu, et al. Finding vital node by node importance evaluation matrix in complex networks[J]. Acta Physica Sinica, 2012, 61(5): 1-5.

段凡丁. 关于最短路径的SPFA快速算法[J]. 西南交通大学学报, 1994, 29(2): 207-212. DUAN Fanding. A faster algorithm for shortest-ptath-SPFA[J]. Journal of Southwest Jiaotong University, 1994, 29(2): 207-212.

施引文献

附加材料(0)

访问统计