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

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.