Community Detection in Graphs: Granovetter's Theory, Louvain Algorithm, and Overlapping Communities with BigCLAM

Granovetter's weak‑tie theory is introduced to show that strong connections exist within tightly knit groups while weak connections bridge different groups, providing a sociological basis for community structures in graphs.

Edge Overlap is defined as the proportion of shared neighbors between two nodes (excluding the nodes themselves). An example calculation shows O ij = 1/3, and the metric is used to assess link strength in real datasets such as a European phone‑call network.

Community definition: a set of nodes with many internal edges and relatively few external edges. The Zachary Karate Club and NCAA football networks are used as illustrative examples of clear community partitions.

Modularity Q measures the quality of a partition. The formula compares the actual edge weight within communities to the expected weight in a null model that preserves the degree distribution. Q ranges from –1 to 1, with values between 0.3 and 0.7 indicating significant community structure.

The Louvain algorithm greedily maximizes modularity through two phases. In the first phase (Partitioning), each node is initially its own community; nodes are moved to neighboring communities if the move yields a positive ΔQ, iterating until no further improvement. In the second phase (Restructuring), super‑nodes representing communities are aggregated, and the process repeats until convergence.

To detect overlapping communities, the BigCLAM algorithm is presented. It builds a Community Affiliation Graph Model (AGM) where each node has affiliation strengths to multiple communities. The likelihood of the observed graph under the AGM is maximized via gradient descent, yielding affiliation weights that reveal overlapping community memberships.

The article concludes that community detection combines sociological insights (Granovetter), modularity optimization (Louvain), and probabilistic modeling (BigCLAM) to identify both non‑overlapping and overlapping structures in real‑world networks.