{"id":"arxiv:2401.08019","kind":"article","title":"Centrality of shortest paths: Algorithms and complexity results","authors":["Johnson Phosavanh","Dmytro Matsypura"],"author_count":2,"year":2024,"published":"2024-01-16","venue":"INFORMS Journal on Computing 2025","cited_by":0,"doi":"10.1287/ijoc.2024.0945","arxiv_id":"2401.08019","nct_id":null,"source_url":"https://arxiv.org/abs/2401.08019","archive_url":"https://space-kitty.com/papers/arxiv:2401.08019","updated":"2025-04-30","pmid":null,"pmcid":null,"openalex_id":"W4417163915","pdf_url":"https://arxiv.org/pdf/2401.08019","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":null,"categories":["cs.DS","cs.CC","math.OC"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[{"slug":"algorithms-complexity","name":"Algorithms & Complexity Breakthroughs","domain_slug":"math-cs"}],"cited_in_dossiers":[]}