Detecting large cohesive subgroups with high clustering coefficients in social networks Academic Article uri icon


  • © 2016 Elsevier B.V. Clique relaxations are used in classical models of cohesive subgroups in social network analysis. Clustering coefficient was introduced more recently as a structural feature characterizing small-world networks. Noting that cohesive subgroups tend to have high clustering coefficients, this paper introduces a new clique relaxation, α-cluster, defined by enforcing a lower bound α on the clustering coefficient in the corresponding induced subgraph. Two variations of the clustering coefficient are considered, namely, the local and global clustering coefficient. Certain structural properties of α-clusters are analyzed and mathematical optimization models for determining α-clusters of the largest size in a network are developed and validated using several real-life social networks. In addition, a network clustering algorithm based on local α-clusters is proposed and successfully tested.

altmetric score

  • 1

author list (cited authors)

  • Ertem, Z., Veremyev, A., & Butenko, S.

citation count

  • 13

publication date

  • July 2016