Centrality of shortest paths: algorithms and complexity results
Abstract: 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||V|^2\Delta(G))$, where $|V|$ is the number of vertices, $|E|$ is the number of edges, and $\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, while 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 to the existing literature.
Short bio: Dmytro Matsypura is an Associate Professor in the Discipline of Business Analytics at the University of Sydney Business School. His current research focus is on applications of convex and combinatorial optimisation in forecasting, graph theory, finance, transportation, and ecology.
Dr Matsypura received a bachelor's degree in Business Administration, with honours, in 1998, an MS degree in Information Systems, with honours, in 2000 from Kyiv Polytechnic Institute, and a Ph.D. degree in Management Science from the University of Massachusetts Amherst in 2006. In 2007, he joined the Discipline of Business Analytics at the University of Sydney.
Short bio: Dmytro Matsypura is an Associate Professor in the Discipline of Business Analytics at the University of Sydney Business School. His current research focus is on applications of convex and combinatorial optimisation in forecasting, graph theory, finance, transportation, and ecology.
Dr Matsypura received a bachelor's degree in Business Administration, with honours, in 1998, an MS degree in Information Systems, with honours, in 2000 from Kyiv Polytechnic Institute, and a Ph.D. degree in Management Science from the University of Massachusetts Amherst in 2006. In 2007, he joined the Discipline of Business Analytics at the University of Sydney.
Practical information
- Informed public
- Registration required
Organizer
- Prof. Daniel Kuhn