Study On The Shortest Path For Dynamic Complex Network

With the development of information technology,human society has gradually entered the era of complex networks.In reality,various interpersonal relationships,road traffic,and interconnected communications networks can be abstracted into complex networks,and with the gradual deepening of complex network research,a large number of the network characteristics are gradually discovered,and many of the analysis and research related to these network characteristics are based on the shortest path of the network,such as the betweenness of the node,the average radius of the network,the information dissemination of the network,the navigation of urban roads,and the transmission of disease.Issues such as communication,interpersonal relationships,etc.are all closely related to the shortest path of the network.The shortest path research of complex networks is mainly based on static network and dynamic network.The shortest path research based on static network already has many classical algorithms,such as Dijkstra algorithm,Floyd-Warshall algorithm and Bellman-Ford algorithm,etc..Although the shortest path of the network can be accurately obtained,the time complexity is so high that not suitable for the large complex network,and not suitable for calculate the complex networks' characteristics such as betweenness centrality and closeness centrality based on the shortest path.After then a series of solving methods suitable for the shortest path of large-scale complex networks are putting forward,such as restricted area search method,target guiding method,hierarchical dividing method,local large-area center point and other methods,are simplified to approximate calculate the shortest path.These research in solving shortest paths based on static networks obtained better results.In the real world,with the increasing scale of the network,complex networks are becoming more and more dynamics and randomness.In order to solve the shortest path of dynamic complex networks and network characteristics better,a series of approximate calculating algorithms have been putted forward in recent years.Such as dynamic shortest path tree algorithm,distributed algorithm,graph index structure algorithm,heuristic algorithm,improved A* algorithm,etc.,but these algorithms do not consider the structural characteristics of complex networks fully,and its computational complexity Higher.Based on the existing algorithms,this paper proposes an improved dynamic-complex network shortest path approximation algorithm,which combines the degree of nodes and the aggregation coefficient to redefine the measurement method of the local area center point,so as to obtain the local area center point more accurately.At the same time,the concept of regional relay nodes is proposed,which can effectively split or merge the divided regions in dynamic change,reduce the impact of local dynamic changes on the overall changes,and accelerate the approximate calculate of the shortest path.In this paper,the proposed algorithm is tested and analyzed by generating simulation networks of different scales.By comparing the shortest path approximation method between proposed in this paper and the method before improvemented,the proposed method is more accurate.At in the same time,comparing with the shortest path approximation algorithm of representative dynamic complex networks,it can be seen that the proposed method has lower computational complexity and can obtain better short-path approximation results.