Centrality of shortest paths: algorithms and complexity results

Date: Thursday 5th June 2025

Abstract

The centrality of a node is often used to measure its importance within a network's structure. Certain centrality measures can be extended to evaluate the importance of a group of nodes that share a common property or form a specific structure, such as a path. In this talk, we focus on identifying the most central shortest path. We demonstrate that the computational complexity of this problem depends on the centrality measure 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||V|^2\Delta(G))$, where $|V|$ represents the number of vertices in the network, $|E|$ is the number of edges, and $\Delta(G)$ denotes the maximum degree of the graph. Additionally, we show that this problem is NP-hard on a weighted graph. Furthermore, we demonstrate that finding the most betweenness-central shortest path can be solved in polynomial time, while finding the most closeness-central shortest path is NP-hard, irrespective of whether the graph is weighted or not. We also develop an algorithm for identifying the most betweenness-central shortest path with a running time of $O(|E|^2|V|^2)$ for both weighted and unweighted graphs. Finally, we present a numerical study of our algorithms on synthetic and real-world networks, comparing our results to those found in the existing literature.