Finding groups with maximum betweenness centrality

Abstract

In this paper we consider the problem of identifying the most influential (or central) group of nodes (of some predefined size) in a network. Such a group has the largest value of betweenness centrality or one of its variants, for example, the length-scaled or the bounded-distance betweenness centralities. We demonstrate that this problem can be modelled as a mixed integer program (MIP) that can be solved for reasonably sized network instances using off-the-shelf MIP solvers. We also discuss interesting relations between the group betweenness and the bounded-distance betweenness centrality concepts. In particular, we exploit these relations in an algorithmic scheme to identify approximate solutions for the original problem of identifying the most central group of nodes. Furthermore, we generalize our approach for identification of not only the most central groups of nodes, but also central groups of graph elements that consists of either nodes or edges exclusively, or their combination according to some pre-specified criteria. If necessary, additional cohesiveness properties can also be enforced, for example, the targeted group should form a clique or a κ-club. Finally, we conduct extensive computational experiments with different types of real-life and synthetic network instances to show the effectiveness and flexibility of the proposed framework. Even more importantly, our experiments reveal some interesting insights into the properties of influential groups of graph elements modelled using the maximum betweenness centrality concept or one of its variations.

Keywords:

• betweenness centrality
• bounded-distance betweenness centrality
• group betweenness centrality
• most central groups
• mixed integer programming

Acknowledgements

The authors would also like to thank the Associate Editor and the anonymous reviewers for their comments, which greatly improved the clarity and exposition of the manuscript.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1. A vertex cover of a graph is defined as a subset of its nodes such that each edge of the graph is incident to at least one node of the subset [44].

Additional information

Funding

This material is based upon research supported by the U.S. Air Force Research Laboratory (AFRL) Mathematical Modeling and Optimization Institute and sponsored by AFRL/RW under agreement number FA8651-14-2-0002. The second author was also supported by the U.S. Air Force Summer Faculty Fellowship program and the grant from the Defense Threat Reduction Agency (DTRA) HDTRA1-14-1-0065. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of AFRL/RW or the U.S. Government.