Shortest path counting in complex networks based on powers of the adjacency matrix

Area of Science:

• Graph theory
• Network science
• Computer science

Background:

• Complex networks are ubiquitous in nature and society.
• Shortest path calculations are fundamental in network science.
• Existing methods struggle to quantify both the number and length of shortest paths efficiently.

Purpose of the Study:

• To develop a fast algorithm for counting all-pairs shortest paths and their lengths.
• To extend the use of adjacency matrix powers beyond walk counting.

Main Methods:

• The study proposes an algorithm based on powers of the adjacency matrix.
• This method is designed to count both the number and length of all shortest paths.
• The algorithm addresses the all-pairs shortest path count problem.

Main Results:

• The proposed algorithm is significantly faster than classical methods on various network types and sizes.
• Experimental results demonstrate superior performance on synthetic and real-world networks.
• The algorithm's time complexity surpasses current state-of-the-art methods.

Conclusions:

• The developed algorithm enables rapid calculation of all shortest paths in large-scale networks.
• This offers potential applications in traffic flow optimization and social network analysis.
• The method provides an efficient solution for a long-standing challenge in network science.