中国物理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. 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(孙昱)1, Pei-Yang Yao(姚佩阳)1, Lu-Jun Wan(万路军)2, Jian Shen(申健)1, Yun Zhong(钟赟)1   

  1. 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).

摘要: 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)