Algorithm for complex network diameter based on distance matrix  

作　　者：CHEN Bin ZHU Weixing LIU Ying 

机构地区：[1]Institute of Command Information System, PLA University of Science and Technology [2]College of Computer Science and Engineering, Sanjiang University [3]Institute of Field Engineering, PLA University of Science and Technology

出　　处：《Journal of Systems Engineering and Electronics》2018年第2期336-342,共7页系统工程与电子技术（英文版）

基　　金：supported by the National Natural Science Foundation of China(61273210)

摘　　要：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.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.

关 键 词：complex network network diameter distance matrix 

分 类 号：N945[自然科学总论—系统科学] TN01[电子电信—物理电子学]