Centrality of Shortest Paths: Algorithms and Complexity Results
研究了寻找最中心最短路径的问题，发现其计算复杂性取决于中心性度量，对度中心性在无权图上给出多项式算法，在加权图上证明为NP难，对介数中心性给出多项式算法，对接近中心性证明为NP难。
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 [Formula: see text], where | V | is the number of vertices, | E | is the number of edges, and [Formula: see text] 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 [Formula: see text] on unweighted graphs and [Formula: see text] 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/ .