Journal of Systems Engineering and Electronics ›› 2018, Vol. 29 ›› Issue (2): 336-342.doi: 10.21629/JSEE.2018.02.14

• Systems Engineering • Previous Articles     Next Articles

Algorithm for complex network diameter based on distance matrix

Bin CHEN1,2,*(), Weixing ZHU1(), Ying LIU3()   

  1. 1 Institute of Command Information System, PLA University of Science and Technology, Nanjing 210007, China
    2 College of Computer Science and Engineering, Sanjiang University, Nanjing 210012, China
    3 Institute of Field Engineering, PLA University of Science and Technology, Nanjing 210007, China
  • Received:2017-01-03 Online:2018-04-26 Published:2018-04-27
  • Contact: Bin CHEN E-mail:156735905@qq.com;fly_fox_2008@139.com;13913867236@139.com
  • About author:CHEN Bin was born in 1979. He is a Ph.D. and an associate professor in People's Liberation Army University of Science and Technology. In 2008, he graduated from this university. After graduation, he has been engaged in related scientific research and teaching work. He participated in the National High Technology Research and Development Program ("863" Program) of China (capabilities requirements analysis technology about large-scale complex system, 2007AA01Z126), the National Natural Science Foundation of China (analysis and verification for command and control system capability requirements model, 61273210) and other army key projects. He published more than 30 academic papers in this research field on authoritative domestic or foreign journals or international academic conferences. His research interests are complex system and complex network. E-mail: 156735905@qq.com|ZHU Weixing was born in 1978. He is a doctor and a lecturer in PLA University of Science and Technology. His research interest is algorithm design. In 2012, he graduated from this university. After graduation, he has been engaged in related scientific research. He has published more than ten academic papers in this research field on authoritative domestic or foreign journals or international academic conferences. E-mail: fly_fox_2008@139.com|LIU Ying was born in 1977. She is a doctor and a lecturer in PLA University of Science and Technology. Her research interest is complex system. In 2008, she graduated from this university. After graduation, she has been engaged in related scientific research and teaching work. She has published more than 20 academic papers in this research field on authoritative domestic or foreign journals or international academic conferences. E-mail: 13913867236@139.com
  • Supported by:
    the National Natural Science Foundation of China(61273210);This work was supported by the National Natural Science Foundation of China (61273210)

Abstract:

The network diameter is an important characteristic parameter of a complex network. Calculation for a large-scale complex network's diameter has been an important subject in the study of complex networks. If the network diameter is calculated directly, the problem mainly exists in efficiency for searching and counting the shortest paths. If the network diameter is calculated indirectly by studying the statistical function about the relationship between the network diameter and parameters affecting the diameter, the problems not only exist in the efficiency of statistic, but also exist in the function which may be not applicable to all kinds of networks. An algorithm for the complex network diameter based on the k order distance matrix is proposed with a matrix multiplication approach, and a mathematical proof for the algorithm correctness is given as well. Furthermore, some relevant propositions and deductions for reducing the complexity of this algorithm are put forward. With a good theoretical basis and a simple calculation process, this algorithm can be used to calculate the diameter of a large-scale complex network with small-world effect more accurately and efficiently. Two cases about the advanced research projects agency (ARPA) network model and the Chinese airline network model are adopted to verify the effect of this algorithm.

Key words: complex network, network diameter, distance matrix