Tan Dingrong, Deng Ye, Xiao Yu, Wu Jun
Department of Systems Science, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China.
International Academic Center of Complex Systems, Beijing Normal University, Zhuhai 519087, China.
Chaos. 2024 Oct 1;34(10). doi: 10.1063/5.0226144.
Complex networks describe a broad range of systems in nature and society. As a fundamental concept of graph theory, the path connecting nodes and edges plays a crucial role in network science, where the computation of shortest path lengths and numbers has garnered substantial focus. It is well known that powers of the adjacency matrix can calculate the number of walks, specifying their corresponding lengths. However, developing methodologies to quantify both the number and length of shortest paths through the adjacency matrix remains a challenge. Here, we extend powers of the adjacency matrix from walks to shortest paths. We address the all-pairs shortest path count problem and propose a fast algorithm based on powers of the adjacency matrix that counts both the number and the length of all shortest paths. Numerous experiments on synthetic and real-world networks demonstrate that our algorithm is significantly faster than the classical algorithms across various network types and sizes. Moreover, we verified that the time complexity of our proposed algorithm significantly surpasses that of the current state-of-the-art algorithms. The superior property of the algorithm allows for rapid calculation of all shortest paths within large-scale networks, offering significant potential applications in traffic flow optimization and social network analysis.
复杂网络描述了自然界和社会中的广泛系统。作为图论的一个基本概念，连接节点和边的路径在网络科学中起着至关重要的作用，其中最短路径长度和数量的计算备受关注。众所周知，邻接矩阵的幂可以计算路径的数量，并指定其相应的长度。然而，开发通过邻接矩阵量化最短路径的数量和长度的方法仍然是一个挑战。在这里，我们将邻接矩阵的幂从路径扩展到最短路径。我们解决了所有节点对之间的最短路径计数问题，并提出了一种基于邻接矩阵幂的快速算法，该算法可以计算所有最短路径的数量和长度。在合成网络和真实世界网络上进行的大量实验表明，我们的算法在各种网络类型和规模上都比经典算法快得多。此外，我们验证了我们提出的算法的时间复杂度明显超过了当前的最先进算法。该算法的优越特性允许在大规模网络中快速计算所有最短路径，在交通流优化和社交网络分析中具有重要的潜在应用。
