Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 271, Issue 1, Pages 155-164Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2018.05.006
Keywords
Networks; Betweenness centrality; Clique; NP-completeness; Combinatorial branch-and-bound
Funding
- Air Force Research Laboratory
- AFRL Mathematical Modeling and Optimization Institute
Ask authors/readers for more resources
This article introduces and studies the most betweenness-central clique problem, which involves finding a clique cluster of maximum betweenness centrality in a connected network. This problem allows one to extend the traditional notion of finding a single most influential (or central) member, to one of identifying central groups whose members collectively satisfy a structural property that is meaningful relative to the underlying system. Among others, betweenness-central cliques find application in corporate, social, communication, power grid, and biological network analysis. In this study, the betweenness centrality measure adopted to define our problem is based on the summation of the percentages representing the ratio of the shortest paths between every pair of vertices in a network that intersect a given clique. The decision version of this problem is proven to be NP-complete, and it is shown that an optimal solution to this problem is either a maximal clique, or contained in a maximal clique with the same objective value. We also propose an analytical upper bound for the betweenness centrality of any maximal clique containing a given clique, and employ it to develop a combinatorial branch-and-bound algorithm for solving this problem. Computational performance of the proposed algorithm is then compared with that of a mixed integer programming technique on a test-bed of randomly generated graphs and real-life power-law networks. (C) 2018 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available