Centrality of Shortest Paths: Algorithms and Complexity Results

The centrality of a node is often used to measure its importance to the structure of a network. Some centrality measures can be extended to measure the importance of a path. In this paper, we consider the problem of finding the most central shortest path. We show that the computational complexity of this problem depends on the measure of centrality used and in the case of degree centrality, whether the network is weighted or not. We develop a polynomial algorithm for the most degree-central shortest path problem with the worst-case running time of $O(|E\Vert V{|}^2\mathrm{\Delta }(G))$, where | V | is the number of vertices, | E | is the number of edges, and $\mathrm{\Delta }(G)$ is the maximum degree of the graph. In addition, we show that the same problem is NP-hard on a weighted graph. Furthermore, we show that the problem of finding the most betweenness-central shortest path is solvable in polynomial time, whereas finding the most closeness-central shortest path is NP-hard, regardless of whether the graph is weighted or not. We also develop an algorithm for finding the most betweenness-central shortest path with a running time of $O(|E{|}^2|V{|}^2)$ on unweighted graphs and $O(|E{|}^2|V{|}^2+|V{|}^2\log (|V|))$ on graphs with positively weighted edges. To conclude our paper, we conduct a numerical study of our algorithms on synthetic and real-world networks and compare our results with the existing literature.

History: Accepted by Russell Bent, Area Editor for Network Optimization: Algorithms and Applications.

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0945) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0945). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.