Beyond Modularity: Uncovering Social Structures via Clique Correlation

TL;DR

Researchers have developed a new lens for viewing social communities by focusing on cliques (fully connected subgraphs) rather than individual edges. By building a bipartite graph and analyzing correlation coefficients, this method bypasses the "resolution limit" of standard Modularity, ensuring small, tightly-knit groups aren't swallowed by larger ones.

The Problem: The "Short-Sightedness" of Modularity

For years, Modularity (Q) has been the gold standard for partitioning networks. However, it possesses a fundamental flaw: the resolution limit. In a massive network, Modularity optimization often fails to "see" small communities, even if they are perfect cliques. It treats every edge with equal weight in its global calculation, which often leads to the heteroscedasticity problem—where high-degree nodes mask the subtle correlation of smaller groups.

The Insight: Cliques as the Atom of Community

The authors argue that in a social context, individuals don't just connect; they form cliques (groups of 3 or 4 people who all know each other). These cliques are the true building blocks of a community.

1. The Vertex-Clique Bipartite Graph

The method transforms a standard graph $G$ into a bipartite graph $X$.

• Partition A: The original vertices.
• Partition B: The cliques discovered in the network (e.g., all triangles and 4-node cliques).
• Edges: A link exists if a vertex is a member of a specific clique.

Fig 1: Transformation from a standard network (a) to a vertex-clique bipartite graph (b).

2. From Covariance to Correlation

The authors demonstrate that Modularity is actually a special case of Covariance. However, covariance is sensitive to node degree. By using Correlation Coefficients (normalized covariance), they rescaled the similarities between nodes to a range of $[-1,+1]$. This normalization is the "secret sauce" that allows the algorithm to detect small communities regardless of the total network size.

Methodology: Spectral Clustering with a Twist

The core process involves:

1. Weighting: Larger cliques are given slightly more weight (using $f(k)={\alpha }^k$) because a 4-person clique is a stronger social signal than a simple edge (2-person clique).
2. Matrix Decomposition: Performing an eigenvector decomposition on the correlation matrix $R$.
3. K-Means: Using the leading eigenvectors (guided by the largest eigengap) to cluster vertices.

Experimental Results: Breaking the Limit

In the "clique-circle" benchmark—a test specifically designed to trigger the resolution limit—standard spectral methods merged smaller cliques together. The Clique Correlation method (cor-cliques) successfully identified the distinct groups, maintaining high Normalized Mutual Information (NMI) even when group structures became obscure.

Fig 2: Comparison of algorithms (cor-cliques vs. spinglass, fastgreedy) as the number of inter-group links ($z_o$) increases.

In real-world tests:

• Karate Club: It perfectly split the 34 nodes into the two historically correct factions.
• Jazz Musicians: It found 4 distinct communities of band-mates where other methods often produced fragmented or overly-broad results.

Critical Analysis & Conclusion

Takeaway

The shift from edge-based to clique-based correlation provides a much-needed higher-order perspective. By focusing on how vertices share membership in cliques, the algorithm naturally preserves the "core" of communities that Modularity often ignores.

Limitations

The primary bottleneck is computational: finding all maximal cliques is a known NP-hard problem. While the authors limit the search to $k=4$ to keep complexity at $O(n^2)$, this might miss larger structural features in extremely dense networks.

Future Work

The authors suggest that this framework could be extended to overlapping communities by replacing K-means with Fuzzy C-means, allowing nodes to belong to multiple cliques—a more realistic representation of human social life.