Finding the most degree-central walks and paths in a graph

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 concepts 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 work, we study 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 neighbourhood.

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. In contrast to the most central shortest path problem, we demonstrate that these problems are NP-hard. To solve these problems, we derive two types of linear MIP formulations that rely on two interpretations of a walk: a sequence of visited vertices 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. Moreover, we illustrate that the high-quality heuristic solutions can be used to warm-start a MIP solver and improve its performance. 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.

Dmytro Matsypura is an Associate Professor in Business Analytics at the University of Sydney Business School. His current research interests are in convex and combinatorial optimisation with applications in machine learning, network science, finance, and ecology. He is the author of many research articles and several book chapters.

Dr. Matsypura received a bachelor’s degree in Business Administration in 1998 and a master’s degree in Information Systems with honours in 2000 from Kyiv Polytechnic Institute. He also received 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.

Видео Finding the most degree-central walks and paths in a graph канала OPTIMA ARC