Finding clique clusters with the highest betweenness centrality

Maciej Rysz, Foad Mahdavi Pajouh, Eduardo L. Pasiliao

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)155-164
Number of pages10
JournalEuropean Journal of Operational Research
Volume271
Issue number1
DOIs
StatePublished - 16 Nov 2018

Keywords

  • Betweenness centrality
  • Clique
  • Combinatorial branch-and-bound
  • NP-completeness
  • Networks

Fingerprint

Dive into the research topics of 'Finding clique clusters with the highest betweenness centrality'. Together they form a unique fingerprint.

Cite this