TY - JOUR
T1 - Detecting a most closeness-central clique in complex networks
AU - Nasirian, Farzaneh
AU - Mahdavi Pajouh, Foad
AU - Balasundaram, Balabhaskar
N1 - Publisher Copyright:
© 2019 Elsevier B.V.
PY - 2020/6/1
Y1 - 2020/6/1
N2 - Centrality is a powerful concept for detecting influential components of a network applicable to various areas such as analysis of social, collaboration, and biological networks. In this study, we employ one of the well-known centrality measures, closeness centrality, to detect a group of pairwise connected members (a highly connected community known as a clique) with the highest accessibility to the entire network. To measure the accessibility of a clique, we use two metrics, the maximum distance and the total distance to the clique from other members of the network. Hence, we are dealing with two variants of the most central clique problem referred to as maximum-distance-closeness-central clique and total-distance-closeness-central clique problems. We study the computational complexity of these two problems and prove that their decision versions are NP-complete. We also propose new mixed 0–1 integer programming formulations and the first combinatorial branch-and-bound algorithms to solve these problems exactly. We show that our algorithmic approaches offer at least 83-fold speed-up on over 96% of benchmark instances in comparison to existing approaches.
AB - Centrality is a powerful concept for detecting influential components of a network applicable to various areas such as analysis of social, collaboration, and biological networks. In this study, we employ one of the well-known centrality measures, closeness centrality, to detect a group of pairwise connected members (a highly connected community known as a clique) with the highest accessibility to the entire network. To measure the accessibility of a clique, we use two metrics, the maximum distance and the total distance to the clique from other members of the network. Hence, we are dealing with two variants of the most central clique problem referred to as maximum-distance-closeness-central clique and total-distance-closeness-central clique problems. We study the computational complexity of these two problems and prove that their decision versions are NP-complete. We also propose new mixed 0–1 integer programming formulations and the first combinatorial branch-and-bound algorithms to solve these problems exactly. We show that our algorithmic approaches offer at least 83-fold speed-up on over 96% of benchmark instances in comparison to existing approaches.
KW - Clique
KW - Closeness centrality
KW - Exact algorithms
KW - NP-completeness
KW - Networks
UR - http://www.scopus.com/inward/record.url?scp=85076532758&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076532758&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2019.11.035
DO - 10.1016/j.ejor.2019.11.035
M3 - Article
AN - SCOPUS:85076532758
SN - 0377-2217
VL - 283
SP - 461
EP - 475
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -