Detecting large cohesive subgroups with high clustering coefficients in social networks

• A new clique relaxation, α cluster, is introduced.
• Structural properties of α clusters in social networks are investigated.
• Optimization methods for finding large α clusters are proposed.
• A clustering technique based on α clusters is developed.
• Results of numerical experiments with social networks are reported.

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.