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

abstract

  • 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.

published proceedings

  • Social Networks

altmetric score

  • 1

author list (cited authors)

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

citation count

  • 22

complete list of authors

  • Ertem, Zeynep||Veremyev, Alexander||Butenko, Sergiy

publication date

  • January 2016