Abstract
In network science, the shortest path is often the primary metric for connectivity. However, real-world systems, such as urban transportation, frequently rely on alternative, longer routes. This paper argues that treating path length as a distribution provides a more comprehensive understanding of network resilience and accessibility. We introduce a $k$-th order approximation to calculate the expected path length, demonstrating that this value converges even when considering only a few steps beyond the shortest path. Our findings, validated on theoretical and empirical networks, suggest that "true" connectivity can be captured without the computational burden of exhaustive path-finding.
Introduction
Graph theory typically prioritizes efficiency, focusing on the shortest path between nodes. While optimal for routing internet packets, this approach often fails to capture the nuances of human behavior in complex environments like cities. Commuters may avoid the shortest route due to congestion, safety, or environmental factors.
Existing metrics like the Communicability Index utilize "walks"—sequences of nodes that allow repetitions. However, human movement is better modeled by "paths," which visit each node at most once. While counting walks is computationally trivial using adjacency matrices, counting all paths is an NP-complete problem. This paper proposes a methodology to bridge this gap by analyzing the distribution of paths within a limited deviation from the shortest route.
Methodology
To manage the complexity of path-finding, we propose a $k$-th order approximation. Instead of an exhaustive search, we analyze paths of length $s + k$, where $s$ is the shortest path length and $k$ represents the additional edges allowed.
Computational Approach
- Depth-Limited Search (DLS): We employ DLS to identify all paths up to a specified length, mitigating the factorial growth of path counts in large networks.
- Expected Path Length ($E[l']$): We calculate the mean length of the path distribution. This metric serves as a robust indicator of how "reachable" a node is when considering alternatives.
- Analytical Benchmarking: For complete graphs ($C_n$), we derive combinatorial formulas to validate our algorithmic results.
Datasets
The proposed framework was tested on two distinct structures:
- Complete Graph ($C_{10}$): A 10-node theoretical model where every node pair is connected, used to verify analytical solutions.
- Zachary’s Karate Club Graph: A classic social network ($N=34$, $M=78$) representing friendships in a university club. This dataset is a standard benchmark for testing connectivity and community detection.
Key Insights and Results
The Convergence Phenomenon
A critical finding is the divergence between walk and path behavior. As shown in Figure 1, the number of walks grows exponentially with length. In contrast, the number of paths in non-complete graphs eventually decreases because the constraint of not repeating nodes limits the available trajectories as they approach the size of the network.
Because the number of long paths eventually drops, the expected path length ($E[l']$) reaches a "saturation point." This implies that researchers can obtain a stable measure of connectivity by looking only a few steps ($k$) beyond the shortest path, rather than solving the full NP-complete problem.
Empirical Observations in the Karate Club
In the Karate Club network, we observed that for the path between nodes 0 and 1, the shortest path is 1. While 37 walks of length 3 exist, only 13 are valid paths. The longest possible path between these nodes is 18 edges. Our analysis identified Node 16 as the most "unapproachable" node, possessing the highest mean path length and mode—an insight that might be overlooked if one only considers shortest-path metrics.
Conclusion
This paper demonstrates that the path length distribution offers a richer perspective on network connectivity than single-scalar metrics. By introducing the "delta measure"—the difference between expected and shortest path lengths—we show that path-based indices converge to a constant value, unlike walk-based indices which grow indefinitely. Future research will apply these indices to large-scale urban mobility data, specifically examining how environmental risks like flooding influence path selection and network resilience.
Summary updated