# Centrality of shortest paths: Algorithms and complexity results

Article · Johnson Phosavanh, Dmytro Matsypura

- Archive id: arxiv:2401.08019
- Published: 2024-01-16
- Venue: INFORMS Journal on Computing 2025
- DOI: https://doi.org/10.1287/ijoc.2024.0945
- arXiv: https://arxiv.org/abs/2401.08019
- Citations: 0
- Source URL: https://arxiv.org/abs/2401.08019
- PDF: https://arxiv.org/pdf/2401.08019
- Provenance: arxiv

## Abstract

The degree centrality of a node, defined as the number of nodes adjacent to it, is often used as a measure of importance of a node to the structure of a network. This metric can be extended to paths in a network, where the degree centrality of a path is defined as the number of nodes adjacent to it. In this paper, we reconsider the problem of finding the most degree-central shortest path in an unweighted network. We propose a polynomial algorithm with the worst-case running time of $O(\|E\|\|V\|^2Δ(G))$, where $\|V\|$ is the number of vertices in the network, $\|E\|$ is the number of edges in the network, and $Δ(G)$ is the maximum degree of the graph. We conduct a numerical study of our algorithm on synthetic and real-world networks and compare our results to the existing literature. In addition, we show that the same problem is NP-hard when a weighted graph is considered. Furthermore, we consider other centrality measures, such as the betweenness and closeness centrality, showing that the problem of finding the most betweenness-central shortest path is solvable in polynomial time and finding the most closeness-central shortest path is NP-hard, regardless of whether the graph is weighted or not.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.