Research On Approximate Shortest Path Algorithm For Complex Network Based On K-core Region

The shortest path calculation has always been an important research content in complex networks.In recent years,with the deepening of research,the calculation and problem solving of many feature quantities in complex networks are more and more dependent on the calculation of shortest path.The classical algorithm is not suitable for calculating the complex network with large-scale nodes and edges in both the complexity of the algorithm and the efficiency.At present,some common approximation algorithms are not ideal and can not meet the needs of the shortest path calculation of complex networks for their applicability,efficiency and accuracy.Therefore,how to achieve the best balance between calculation delay,memory occupancy rate and accuracy and how to improve the network applicability has become the algorithm researchers who chase important goals.Based on the existing approximation algorithm,this paper proposes a shortest path approximation algorithm based on k-core division area.It maintains a high computational efficiency and accuracy in real large-scale social networks,Web social networks and Internet.First,the algorithm divides the network level into several k-shell subnet based on k-core,and then determines the importance of the nodes according to k-shell value sequence of the nodes.The k-shell subnet with different node importance are divided into high-level,margin-level and middle-level of the three areas,and finally in the calculation of the shortest path,for the high-level area,because the nodes size is small and even more dense edge,so the exact calculation of all the nodes of the shortest path;for the margin-level area,the node's degree is relatively small,k-shell as a node importance,each searching only search k-shell value is greater than or equal to the current node of the neighbor node,to limit the node search area purposes;for the middle-level area,because the edges of the including k-shell subnet is very dense,While perform super-node-convergence on the internal node of the k-shell subnet.In the search process only the edges of the center node of super node is used for the purpose of improving the search efficiency.The search process is the same as that of the margin-level.The algorithm uses k-core as the basis for network division and target guidance is more general.The use of the super-node-convergence process on k-shell subnet Significantly reduces the size of traversing nodes in the path search.Bidirectional search tree and priority queue technology to optimize and accelerate the path search process,greatly improving the algorithm's computational efficiency and accuracy.In this paper,the algorithm is experimented and analyzed by using the network datasets of different sizes in reality.The experimental data show that the algorithm is superior to CDZ algorithm in network applicability,computational efficiency and accuracy.For example,in the com-DBLP community network(scale is about 300,000 nodes,100 million edges of the undirected graph),the node on the shortest path of the average calculation time only tens of milliseconds,the correct rate can reach 99%.In different power law exponent of the scale-free network simulation model,the algorithm also showed a very good computing efficiency and applicability.