Detecting a most closeness-central clique in complex networks

Farzaneh Nasirian, Foad Mahdavi Pajouh, Balabhaskar Balasundaram

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)461-475
Number of pages15
JournalEuropean Journal of Operational Research
Volume283
Issue number2
DOIs
StatePublished - 1 Jun 2020

Keywords

  • Clique
  • Closeness centrality
  • Exact algorithms
  • NP-completeness
  • Networks

Fingerprint

Dive into the research topics of 'Detecting a most closeness-central clique in complex networks'. Together they form a unique fingerprint.

Cite this