Finding the most degree-central walks and paths in a graph: Exact and heuristic approaches

Dmytro Matsypura, Alexander Veremyev, Eduardo L. Pasiliao and Oleg A. Prokopyev

European Journal of Operational Research, 2023, vol. 308, issue 3, 1021-1036

Abstract: In network analysis, node centrality is used to quantify the importance of a node to the structure of the network. One of the most natural and widely used centrality measures is degree centrality, defined as the number of nodes adjacent to a given node. A simple generalization of this concept that arises in many real-life applications is to consider the centrality of node groups, including subgraphs with specific connectivity properties. In this paper, we consider the problem of finding the most central walk in a network, where the centrality of the walk is given by the size of its immediate neighborhood. We begin with the problem of finding the most central shortest path and show that this problem can be solved in polynomial time. We then focus on finding other types of most central walks, such as general walks, trails, paths, and induced paths of some pre-defined length. We demonstrate that in contrast to the most central shortest path problem, these problems are NP-hard. We propose two types of linear MIP formulations to solve these problems exactly that rely on two interpretations of a walk: a sequence of visited nodes and a sequence of traversed edges. In addition, we develop two heuristic algorithms and demonstrate their effectiveness by comparing them with the exact solutions obtained using MIPs; we also exploit heuristic solutions to warm-start the MIP solver. Finally, we test our solution approaches using synthetic and real-life networks in an extensive computational study, which allows us to provide some interesting insights and observations.

Keywords: Networks; Degree centrality; Group centrality; Network analysis; Mixed-integer programming (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722009419
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:308:y:2023:i:3:p:1021-1036

DOI: 10.1016/j.ejor.2022.12.014

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().