中国物理B ›› 2009, Vol. 18 ›› Issue (9): 3783-3789.doi: 10.1088/1674-1056/18/9/028

• • 上一篇    下一篇

A self-organizing shortest path finding strategy on complex networks

沈毅, 裴文江, 王开, 王少平   

  1. School of Information Science and Engineering, Southeast University, Nanjing 210096, China
  • 收稿日期:2008-12-10 修回日期:2009-01-14 出版日期:2009-09-20 发布日期:2009-09-20
  • 基金资助:
    Project supported by the National Natural Science Foundation of China (Grant No 60672095), the National High-Tech Research and Development Program of China (Grant No 2007AA11Z210), the Doctoral Fund of Ministry of Education of China (Grant No 20070286004), the Natural Science Foundation of Jiangsu Province, China (Grant No BK2008281), the Science and Technology Program of Southeast University, China (Grant No KJ2009351), and the Excellent Young Teachers Program of Southeast University, China (Grant No BG2007428).

A self-organizing shortest path finding strategy on complex networks

Shen Yi(沈毅)†ger, Pei Wen-Jiang(裴文江), Wang Kai(王开), and Wang Shao-Ping(王少平)   

  1. School of Information Science and Engineering, Southeast University, Nanjing 210096, China
  • Received:2008-12-10 Revised:2009-01-14 Online:2009-09-20 Published:2009-09-20
  • Supported by:
    Project supported by the National Natural Science Foundation of China (Grant No 60672095), the National High-Tech Research and Development Program of China (Grant No 2007AA11Z210), the Doctoral Fund of Ministry of Education of China (Grant No 20070286004), the Natural Science Foundation of Jiangsu Province, China (Grant No BK2008281), the Science and Technology Program of Southeast University, China (Grant No KJ2009351), and the Excellent Young Teachers Program of Southeast University, China (Grant No BG2007428).

PDF (PC)

1167

赞

摘要： The shortcomings of traditional methods to find the shortest path are revealed, and a strategy of finding the self-organizing shortest path based on thermal flux diffusion on complex networks is presented. In our method, the shortest paths between the source node and the other nodes are found to be self-organized by comparing node temperatures. The computation complexity of the method scales linearly with the number of edges on underlying networks. The effects of the method on several networks, including a regular network proposed by Ravasz and Barabási which is called the RB network, a real network, a random network proposed by Ravasz and Barabási which is called the ER network and a scale-free network, are also demonstrated. Analytic and simulation results show that the method has a higher accuracy and lower computational complexity than the conventional methods.

Abstract: The shortcomings of traditional methods to find the shortest path are revealed, and a strategy of finding the self-organizing shortest path based on thermal flux diffusion on complex networks is presented. In our method, the shortest paths between the source node and the other nodes are found to be self-organized by comparing node temperatures. The computation complexity of the method scales linearly with the number of edges on underlying networks. The effects of the method on several networks, including a regular network proposed by Ravasz and Barabási which is called the RB network, a real network, a random network proposed by Ravasz and Barabási which is called the ER network and a scale-free network, are also demonstrated. Analytic and simulation results show that the method has a higher accuracy and lower computational complexity than the conventional methods.

Key words: complex networks, self-organization, the shortest path, thermal flux diffusion

中图分类号:  (Self-organized systems)

  • 05.65.+b
89.75.Fb (Structures and organization in complex systems) 89.75.Hc (Networks and genealogical trees)