Ranking important nodes in complex networks by simulated annealing

doi:10.1088/1674-1056/26/2/020201

中国物理B ›› 2017, Vol. 26 ›› Issue (2): 20201-020201.doi: 10.1088/1674-1056/26/2/020201

• GENERAL • 下一篇

Ranking important nodes in complex networks by simulated annealing

Yu Sun(孙昱), Pei-Yang Yao(姚佩阳), Lu-Jun Wan(万路军), Jian Shen(申健), Yun Zhong(钟赟)

1 Information and Navigation College, Air Force Engineering University, Xi'an 710077, China;
2 Air Traffic Control and Navigation College, Air Force Engineering University, Xi'an 710077, China

收稿日期:2016-07-15 修回日期:2016-10-31 出版日期:2017-02-05 发布日期:2017-02-05
通讯作者: Pei-Yang Yao E-mail:suny.z@qq.com
基金资助:
Project supported by the National Natural Science Foundation of China (Grant No. 61573017) and the Natural Science Foundation of Shaanxi Province, China (Grant No. 2016JQ6062).

Ranking important nodes in complex networks by simulated annealing

Yu Sun(孙昱)¹, Pei-Yang Yao(姚佩阳)¹, Lu-Jun Wan(万路军)², Jian Shen(申健)¹, Yun Zhong(钟赟)¹

1 Information and Navigation College, Air Force Engineering University, Xi'an 710077, China;
2 Air Traffic Control and Navigation College, Air Force Engineering University, Xi'an 710077, China

Received:2016-07-15 Revised:2016-10-31 Online:2017-02-05 Published:2017-02-05
Contact: Pei-Yang Yao E-mail:suny.z@qq.com
Supported by:
Project supported by the National Natural Science Foundation of China (Grant No. 61573017) and the Natural Science Foundation of Shaanxi Province, China (Grant No. 2016JQ6062).

摘要/Abstract

摘要： In this paper, based on simulated annealing a new method to rank important nodes in complex networks is presented. First, the concept of an importance sequence (IS) to describe the relative importance of nodes in complex networks is defined. Then, a measure used to evaluate the reasonability of an IS is designed. By comparing an IS and the measure of its reasonability to a state of complex networks and the energy of the state, respectively, the method finds the ground state of complex networks by simulated annealing. In other words, the method can construct a most reasonable IS. The results of experiments on real and artificial networks show that this ranking method not only is effective but also can be applied to different kinds of complex networks.

关键词: complex networks, node importance, ranking method, simulated annealing

Abstract: In this paper, based on simulated annealing a new method to rank important nodes in complex networks is presented. First, the concept of an importance sequence (IS) to describe the relative importance of nodes in complex networks is defined. Then, a measure used to evaluate the reasonability of an IS is designed. By comparing an IS and the measure of its reasonability to a state of complex networks and the energy of the state, respectively, the method finds the ground state of complex networks by simulated annealing. In other words, the method can construct a most reasonable IS. The results of experiments on real and artificial networks show that this ranking method not only is effective but also can be applied to different kinds of complex networks.

Key words: complex networks, node importance, ranking method, simulated annealing

中图分类号: (Combinatorics; graph theory)

02.10.Ox

89.20.Ff (Computer science and technology) 89.75.Fb (Structures and organization in complex systems)

孙昱, 姚佩阳, 万路军, 申健, 钟赟. Ranking important nodes in complex networks by simulated annealing[J]. 中国物理B, 2017, 26(2): 20201-020201.

Yu Sun(孙昱), Pei-Yang Yao(姚佩阳), Lu-Jun Wan(万路军), Jian Shen(申健), Yun Zhong(钟赟). Ranking important nodes in complex networks by simulated annealing[J]. Chin. Phys. B, 2017, 26(2): 20201-020201.

参考文献 21

[1]	Sheikhahmadia A, Nematbakhsha M A and Shokrollahi A 2015 Physica A 436 833
[2]	Zhao J, Yu L, Li J R and Zhou P 2015 Chin. Phys. B 24 058904
[3]	Yu Y and Fan S H 2015 J. Inform. Comput. Sci. 12 1281
[4]	Singh A, Kumar R and Singh Y N 2015 Acta Phys. Polon. B 46 305
[5]	Nie T Y, Guo Z, Zhao K and Lu Z M 2016 Physica A 453 290
[6]	Hu P, Fan W L and Mei S W 2015 Physica A 429 169
[7]	Liu J, Xiong Q Y, Shi W R, Shi X and Wang K 2016 Physica A 452 209
[8]	Du Y X, Gao C, Hu Y, Mahadevanc S and Deng Y 2014 Physica A 399 57
[9]	Liu Z H, Jiang C, Wang J Y and Yu H 2015 Knowledge-Based Systems 84 56
[10]	Yang Y Y and Xie G 2016 Inform. Process. Manag. 52 911
[11]	Hu J T, Du Y X, Mo H M, Wei D J and Deng Y 2016 Physica A 444 73
[12]	Xu Y J, Gao Z, Xiao B, Meng F Y and Lin Z Q 2013 Proc. IEEE International Conference on Broadband Network & Multimedia Technology, November 17-19, 2013, Guilin, China, p. 105
[13]	Wang P, Yu X H, Lv J H and Chen A M 2014 Proc. IEEE International Symposium on Circuits and Systems, June 1-5, 2014, Melbourne, Australia, p. 1267
[14]	Hu F, Liu Y H and Jin J Z 2014 Proc. International Symposium on Distributed Computing and Applications to Business, Engineering and Science, November 24-27, 2014, Xianning, China, p. 138
[15]	Ventresca M, Harrison K R and Ombuki-Berman B M 2015 Lecture Notes in Computer Science 9028 164
[16]	Xiao Q 2016 Tehnički Vjesnik 23 397
[17]	Metropolis N, Rosenbluth A W, Rosenbluth M N, Teller A H and Teller E 1953 J. Chem. Phys. 21 1087
[18]	Burke E K and Kendall G 2005 Search methodologies: introductory tutorials in optimization and decision support techniques (New York: Springer) p. 187
[19]	Pablo G and Leon D 2003 Advances in Complex Systems 6 565
[20]	Han C F and Liu L 2009 Proc. IEEE International Conference on Engineering Management and Service Science, September 20-22, 2009, Wuhan, China, p. 2
[21]	Hidefumi S 2012 Proc. IEEE World Congress on Computational Intelligence, June 10-15, 2012, Brisbane, Australia, p. 1

Ranking important nodes in complex networks by simulated annealing

Ranking important nodes in complex networks by simulated annealing

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 21

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Analysis of cut vertex in the control of complex networks[J]. 中国物理B, 2023, 32(2): 28902-028902.
[2]	Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding[J]. 中国物理B, 2023, 32(1): 18903-018903.
[3]	Ai-Xia Feng(冯爱霞), Qi-Guang Wang(王启光), Shi-Xuan Zhang(张世轩), Takeshi Enomoto(榎本刚), Zhi-Qiang Gong(龚志强), Ying-Ying Hu(胡莹莹), and Guo-Lin Feng(封国林). Characteristics of vapor based on complex networks in China[J]. 中国物理B, 2022, 31(4): 49201-049201.
[4]	Yahan Deng(邓雅瀚), Zhongkai Mo(莫中凯), and Hongqian Lu(陆宏谦). Robust H_∞ state estimation for a class of complex networks with dynamic event-triggered scheme against hybrid attacks[J]. 中国物理B, 2022, 31(2): 20503-020503.
[5]	Hongwei Zhang(张红伟), Ran Cheng(程然), and Dawei Ding(丁大为). Finite-time synchronization of uncertain fractional-order multi-weighted complex networks with external disturbances via adaptive quantized control[J]. 中国物理B, 2022, 31(10): 100504-100504.
[6]	Gui-Qiong Xu(徐桂琼), Lei Meng(孟蕾), Deng-Qin Tu(涂登琴), and Ping-Le Yang(杨平乐). LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks[J]. 中国物理B, 2021, 30(8): 88901-088901.
[7]	Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Complex network perspective on modelling chaotic systems via machine learning[J]. 中国物理B, 2021, 30(6): 60506-060506.
[8]	杨远志, 胡敏, 黄泰愚. Influential nodes identification in complex networks based on global and local information[J]. 中国物理B, 2020, 29(8): 88903-088903.
[9]	闫小丽, 崔亚鹏, 倪顺江. Identifying influential spreaders in complex networks based on entropy weight method and gravity law[J]. 中国物理B, 2020, 29(4): 48902-048902.
[10]	石勇, 李博, 龙文. Pyramid scheme model for consumption rebate frauds[J]. 中国物理B, 2019, 28(7): 78901-078901.
[11]	朱世钊, 王玉青, 汪秉宏. Theoretical analyses of stock correlations affected by subprime crisis and total assets: Network properties and corresponding physical mechanisms[J]. 中国物理B, 2019, 28(10): 108901-108901.
[12]	庞明宝, 黄玉满. Coordinated chaos control of urban expressway based on synchronization of complex networks[J]. 中国物理B, 2018, 27(11): 118902-118902.
[13]	王兴元, 王宇, 秦小蒙, 李睿, Justine Eustace. Detecting overlapping communities based on vital nodes in complex networks[J]. 中国物理B, 2018, 27(10): 100504-100504.
[14]	郑志刚, 钱郁. Dominant phase-advanced driving analysis of self-sustained oscillations in biological networks[J]. 中国物理B, 2018, 27(1): 18901-018901.
[15]	邵桂芳, 朱梦, 上官亚力, 李文然, 张灿, 王玮玮, 李玲. Structural optimization of Au-Pd bimetallic nanoparticles with improved particle swarm optimization method[J]. 中国物理B, 2017, 26(6): 63601-063601.