TY - JOUR
T1 - Finding clique clusters with the highest betweenness centrality
AU - Rysz, Maciej
AU - Mahdavi Pajouh, Foad
AU - Pasiliao, Eduardo L.
N1 - Publisher Copyright:
© 2018 Elsevier B.V.
PY - 2018/11/16
Y1 - 2018/11/16
N2 - 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.
AB - 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.
KW - Betweenness centrality
KW - Clique
KW - Combinatorial branch-and-bound
KW - NP-completeness
KW - Networks
UR - http://www.scopus.com/inward/record.url?scp=85048507430&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048507430&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2018.05.006
DO - 10.1016/j.ejor.2018.05.006
M3 - Article
AN - SCOPUS:85048507430
SN - 0377-2217
VL - 271
SP - 155
EP - 164
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -