Finding groups with maximum betweenness centrality via integer programming with random path sampling

One popular approach to access the importance/influence of a group of nodes in a network is based on the notion of centrality. For a given group, its group betweenness centrality is computed, first, by evaluating a ratio of shortest paths between each node pair in a network that are “covered” by at least one node in the considered group, and then summing all these ratios for all node pairs. In this paper we study the problem of finding the most influential (or central) group of nodes (of some predefined size) in a network based on the concept of betweenness centrality. One known approach to solve this problem exactly relies on using a linear mixed-integer programming (linear MIP) model. However, the size of this MIP model (with respect to the number of variables and constraints) is exponential in the worst case as it requires computing all (or almost all) shortest paths in the network. We address this limitation by considering randomized approaches that solve a single linear MIP (or a series of linear MIPs) of a much smaller size(s) by sampling a sufficiently large number of shortest paths. Some probabilistic estimates of the solution quality provided by our approaches are also discussed. Finally, we illustrate the performance of our methods in a computational study.