Source-linked AI summary
Communities in Networks
Mason A. Porter, Jukka-Pekka Onnela, Peter J. Mucha
TL;DR
Community detection is challenging because the preferred definition of a community is often domain-specific. This survey organizes available methods, applications, and open problems while emphasizing links to statistical physics and computational optimization, and concludes that substantial work remains despite extensive technical advances.
Problem
Community detection lacks a universally preferred formulation because what constitutes a community is often domain-specific.
Method
The paper surveys community-detection concepts, methods, applications, and open problems through connections to statistical physics and computational optimization.
Results
The survey highlights an extensive suite of techniques and applications, including local methods such as k-clique percolation and studies of evolving and biological network communities.
Takeaways & Limitations
Community detection is an interdisciplinary area of network science with many technical advances but substantial open work remaining.
Takeaways & Limitations
The discussion assumes connected network components, although community detection can be applied separately to disconnected components.
Abstract
from arXiv · showhide
We survey some of the concepts, methods, and applications of community detection, which has become an increasingly important area of network science. To help ease newcomers into the field, we provide a guide to available methodology and open problems, and discuss why scientists from diverse backgrounds are interested in these problems. As a running theme, we emphasize the connections of community detection to problems in statistical physics and computational optimization.
COMMUNITIES IN NETWORKS · Introduction: Networks and Communities.
The paper frames community detection as the study of mesoscopic network structure, especially groups of nodes that are densely connected internally and sparsely connected externally. It presents the field as an interdisciplinary endeavor linking statistical physics, mathematics, computer science, and applications across social, web, cellular, and genetic networks.
- Introduction: Networks and Communities.: A network is a mathematical graph whose nodes represent agents and whose edges encode interactions or ties; node degree counts incident edges, while strength totals edge weights.
- Introduction: Networks and Communities.: A community is a mesoscopic group of nodes relatively densely connected to one another but sparsely connected to other dense groups.
- Introduction: Networks and Communities.: Sociologists sought mathematical tools and large-scale data manipulation, while Girvan and Newman’s 2002 work brought graph partitioning to statistical physics and mathematics.
- Introduction: Networks and Communities.: The field rapidly attracted physicists and applied mathematicians, producing numerous community-detection methods and a massive body of research.
- Introduction: Networks and Communities.: Community structure can include hierarchical and modular components, with partitions represented as dendrograms and nested modules across multiple reasonable levels.
- Introduction: Networks and Communities.: Many real-world networks have natural hierarchies, as illustrated by U.S. House committees, subcommittees, and larger groups resolved into modules at different levels.
- Introduction: Networks and Communities.: Community structure supports applications including identifying social circles, related web pages, functional cellular or genetic modules, and repeated network motifs.
- Introduction: Networks and Communities.: Community-structure research draws on statistical physics, computer science, discrete mathematics, nonlinear dynamics, sociology, and other disciplines.
A Simple Example.
The Zachary Karate Club illustrates community detection by recovering the observed split into two clubs through spectral optimization of modularity. The method also reveals a hierarchical decomposition with a finer partition into four communities.
- The Zachary Karate Club network split into two smaller clubs after an internal dispute, with members preferentially choosing the club containing most of their friends.
- Spectral partitioning optimization of modularity identifies communities whose two main dendrogram branches reflect the actual memberships of the new clubs.
- The network has a natural hierarchy: a coarse pair of communities matching the observed split and a finer partition into four communities.
Identifying Communities.
Community detection treats communities as cohesive node groups with denser internal than external connections. Methods differ in how they define density and identify groups, while the survey presents popular approaches and contrasts their perspectives and similarities.
- Identifying Communities.: Communities are cohesive groups of nodes connected more densely internally than to nodes in other communities.This intuitive definition underlies community detection.
- Identifying Communities.: Community-detection methods differ mainly in their precise density definitions and the algorithmic heuristics used to identify communities.Different scientific fields’ needs have motivated a wide variety of methods.
- Identifying Communities.: The survey introduces many popular community-detection methods to a broad readership while contrasting their perspectives and highlighting important similarities.It does not attempt an exhaustive comparison of every available algorithm.
Traditional Clustering Techniques. · The Kernighan-Lin Algorithm. · Centrality-Based Community Detection.
The section surveys classical approaches to community detection, including partitional, hierarchical, and divisive clustering, the Kernighan–Lin optimization method, and centrality- or clique-based techniques. These methods differ in how they represent cohesive groups, optimize partitions, and scale across network types and densities.
- Traditional Clustering Techniques.: Traditional clustering methods organize objects by shared features and include partitional, neural-network, and hierarchical approaches for detecting cohesive groups.Hierarchical linkage methods begin with N individual nodes in a weighted network represented by adjacency matrix A.
- Traditional Clustering Techniques.: Divisive clustering starts with the full graph and breaks it apart; prominent examples include spectral methods, while new data-clustering methods remain actively developed.
- The Kernighan-Lin Algorithm.: The 1970 Kernighan–Lin algorithm partitions circuit nodes into boards by maximizing a quality function relating within-group edges to between-group edges.Its original objective was to minimize connections linking nodes assigned to different boards.
- The Kernighan-Lin Algorithm.: When community numbers and sizes are unspecified, generalized Kernighan–Lin methods move one node at a time, but their results depend strongly on the initial partition.The method is therefore best used as a supplement to high-quality partitions obtained with other methods.
- Centrality-Based Community Detection.: Betweenness-centrality detection identifies edges lying on many paths between vertices and uses them to expose network community structure.Girvan and Newman’s algorithm brought increased attention to community structure in mathematics and statistical physics.
- Centrality-Based Community Detection.: Centrality-based methods generalize across network components and bipartite networks but can be too slow for many large networks and perform relatively poorly on dense networks.
- Centrality-Based Community Detection.: K-clique percolation defines communities as unions of adjacent k-cliques sharing k−1 nodes, reflecting communities composed of overlapping small cliques.A k-clique is a complete subgraph of k nodes containing all k(k −1)/2 possible links.
k-Clique Percolation and other Local Methods. · Modularity Optimization.
Local methods such as k-clique percolation recover global structure from overlapping, nested communities, while modularity optimization evaluates partitions by within-group connectivity relative to chance. Modularity optimization is computationally difficult, motivating heuristics and alternatives because modularity has a known resolution limit.
- k-Clique Percolation and other Local Methods.: k-Clique percolation builds global community structure from the ensemble of communities found by looping over all network k-cliques.Some nodes may belong to no community, while interface nodes may belong to multiple communities; varying k recovers nested structure.
- k-Clique Percolation and other Local Methods.: Local methods are important because communities may overlap, including at multiple resolution levels, whereas purely agglomerative and divisive techniques do not permit overlap.The passage motivates overlap using simultaneous membership in social communities such as colleagues, family, and hobbies.
- Modularity Optimization.: Modularity measures how well a network partition compartmentalizes communities by comparing within-group edges with expectations under random edge placement.It explicitly accounts for degree heterogeneity and is closely related to the Freeman segregation index.
- Modularity Optimization.: Optimizing modularity is equivalent to an instance of MAX-CUT and is NP-complete, so many algorithms seek optima using different strategies.The computational problem arises because exhaustively enumerating network partitions requires considering a non-polynomial number of possibilities.
- Modularity Optimization.: In weighted networks, modularity uses sums of edge weights, so heavily weighted edges contribute more than lightly weighted edges.Its interpretation remains the excess within-group edge weight relative to what chance would produce.
- Modularity Optimization.: Modularity is a scaled assortativity measure that quantifies connection strength within communities versus between communities.Because communities should have relatively high internal edge density, high-modularity partitions tend to exhibit strong within-community connectivity.
- Modularity Optimization.: Greedy modularity algorithms are fast heuristics designed for networks with millions of nodes or more, trading computational cost against the typical quality of identified optima.Exhaustive sampling of a desired quality function is typically computationally infeasible.
- Modularity Optimization.: Modularity-maximization methods generalize readily to related quality functions because modularity may not be optimal and has a known resolution limit.The resolution limit can cause important communities to be missed, motivating alternative quality functions that incorporate more than network structure alone.
Spectral Partitioning.
Spectral partitioning uses graph-matrix spectra to divide networks, traditionally by minimizing the cut between two groups. Modularity-based variants instead use eigenvectors of a modularity matrix to recursively identify communities until further subdivision no longer improves modularity.
- Spectral Partitioning.: Traditional spectral partitioning relates network structure to the spectrum of the graph Laplacian matrix.The Laplacian has components Lij = kiδ(i, j) − Aij, where ki is node degree or strength.
- Spectral Partitioning.: The basic procedure recursively splits a network into two components, although each step can also partition it into more than two groups.A two-group partition uses an index vector whose components are +1 or −1 according to group membership.
- Spectral Partitioning.: Modularity-based spectral partitioning reformulates modularity with a modularity matrix, extending the method to a broader class of community-detection problems.The modularity formulation incorporates a null model specifying the relative value of intra-community edges.
- Spectral Partitioning.: The simplest effective modularity procedure uses the leading eigenvector of the modularity matrix, assigning nodes to communities according to the signs of its components.The eigenvector is paired with the largest positive eigenvalue, and component magnitude indicates the strength of a node’s community assignment.
- Spectral Partitioning.: After each bipartition, the method recursively subdivides the resulting components until additional subdivisions can no longer increase modularity.The final partition represents community structure at a specific resolution level.
The Potts Method.
The Potts method maps network community detection onto minimizing a q-state Potts spin-glass Hamiltonian by assigning spins to nodes and communities to shared spin states. With an appropriate interaction definition, the formulation recovers modularity maximization, while allowing alternative interaction models.
- The Potts Method.: In a q-state Potts spin glass, each spin has q possible states, and equal-state pairs contribute −Jij while unequal-state pairs contribute zero.The Hamiltonian sums these pairwise interaction energies over the system.
- The Potts Method.: Community detection is mapped to Potts optimization by assigning one spin to each node and setting q = N.Nodes placed in the same community contribute interaction energy −Jij.
- The Potts Method.: Edge interactions are ferromagnetic when weights exceed a null-model expectation and antiferromagnetic when weights fall below it.Thus, Jij > 0 favors placing connected nodes together, whereas Jij < 0 disfavors it.
- The Potts Method.: The formulation recovers modularity maximization when H = −Q, with division by W serving only as a normalization.Alternative interaction models can also be used to partition networks.
Resolution Parameters.
Modularity has a resolution limit that can merge communities below a network-dependent threshold. Resolution parameters address this limitation by controlling the scale of detected communities and can connect community structure to null models and dynamical time scales.
- Resolution limit: Modularity can miss communities smaller than a threshold determined by network size and community interconnectedness, merging them into larger communities.Fortunato and Barthélemy demonstrated this limitation in 2007 using real and computer-generated networks.
- Resolution parameters: Resolution parameters let researchers zoom across community sizes, with larger λ yielding smaller communities and smaller λ yielding larger ones.Fixing λ sets the scale at which the network is examined, enabling exploration of modular and hierarchical structure.
- Resolution parameters: A resolution parameter can define a uniform null model in which every node pair has a fixed average edge weight.The construction Jij = (Aij −λ)/W can help analyze correlation and similarity networks, including voting-based networks.
- Dynamical processes: Resolution parameters can be related to the time scales of dynamical processes unfolding on a network.This relationship supports studying network structure through dynamical behavior and guiding the choice of quality function.
Applications.
The applications section begins with scientific coauthorship networks as its first example, framed by scientists’ interest in Erdős numbers and self-referential topics and citations.
- Applications.: The section uses scientific coauthorship networks as its first example of community detection applications.The authors introduce this choice in the context of scientists’ obsessive computation of Erdős numbers and the section’s topic and citation selection.
Scientific Collaboration Networks.
Scientific collaboration networks can be modeled from coauthorship data, with weighted projections revealing disciplinary communities. Longitudinal mobile-phone networks extend this analysis to communication ties and societal-scale network structure, including Granovetter’s weak tie hypothesis.
- Scientific Collaboration Networks.: Coauthorship networks link scientists to papers in a bipartite representation and can be projected into weighted scientist-to-scientist networks.The collaboration strength between scientists i and j is defined from their shared authorship of multiple-author papers, weighted by paper authorship.
- Scientific Collaboration Networks.: Betweenness-based community detection on Santa Fe Institute working-paper data yields communities corresponding to different disciplines.The statistical physics community can be further subdivided into three smaller modules centered on dominant research interests.
- Scientific Collaboration Networks.: Mobile-phone networks differ from coauthorship networks because their links arise from instantaneous communication events and capture relationships as they happen.Both mobile-phone and many coauthorship data sets are longitudinal, or time-dependent.
- Scientific Collaboration Networks.: A society-wide mobile-phone interaction network containing millions of individuals was used to relate microscopic, mesoscopic, and macroscopic structure to societal tie strength.The study explored implications for Mark Granovetter’s weak tie hypothesis.
Mobile Phone Networks. · Online Social Networks.
Studies of mobile phone networks show that weak ties can preserve global connectivity, while intermediate ties can be most effective for information diffusion. Online social-network data support community detection that recovers institutional structure and enables comparisons across universities.
- Mobile Phone Networks.: Removing weak ties can trigger a phase transition that disintegrates a mobile phone network, whereas removing strong ties leaves global connectivity intact.The contrast is illustrated by a mobile phone network after strong- versus weak-tie removal.
- Mobile Phone Networks.: Intermediate ties are more effective for information diffusion than either weak or strong ties when transfer scales with tie strength.This result concerns information-transfer effectiveness across tie-strength categories.
- Mobile Phone Networks.: K-clique percolation applied to time-dependent mobile phone data found that large communities persist longer when they dynamically alter their membership.The finding links membership flexibility with longer persistence and adaptability in large groups.
- Online Social Networks.: Social networking sites provide bounded online profiles, friend connections, and traversable networks, and have collectively attracted over one billion users.The passage identifies SNSs as pervasive platforms with large-scale participation.
- Online Social Networks.: The emergence of social networking sites greatly expanded quantitative social and demographic data available for studying network structure and attachment mechanisms.The passage describes this data expansion as transforming social-network research across multiple disciplines.
- Online Social Networks.: A modified leading-eigenvector algorithm followed by KL node-swapping recovered Caltech’s Facebook community structure in agreement with dormitory House affiliations.The method produced communities that accurately matched the known Caltech House structure.
- Online Social Networks.: Facebook friendship data compared American university networks ranging from Caltech’s 1089 nodes to the University of Oklahoma’s approximately 24000 nodes.Nodes represented people and edges represented self-identified, reciprocal online friendships.
Biological Networks. · Legislative Networks.
Community detection links biological-network structure to motifs, functional roles, and evolutionary conservation, while legislative-network analyses use committee assignments and cosponsorship to reveal political organization and influential politicians.
- Biological Networks.: Biological-network clustering is central to identifying structures that may illuminate how biological information flows and networks evolve.The paper frames this as a major goal of biological-network research and notes that clustering methods are core to bioinformatics.
- Biological Networks.: Motifs are significantly overrepresented node-and-edge patterns interpreted as miniature communities, basic building blocks, or small functional modules of complex networks.Milo et al. introduced the motif perspective in 2002 through studies of numerous directed networks.
- Biological Networks.: Motif studies connected three-node and four-node patterns in an integrated Saccharomyces cerevisiae network to larger mesoscopic structures.The network integrated protein, genetic, transcriptional, sequence-homology, and expression-correlation information.
- Biological Networks.: Guimerà and Amaral’s functional cartography uses community structure and node roles to infer functionality in biological networks.Their approach organizes network themes and uses known roles of nodes and modules to interpret unknown functionality.
- Biological Networks.: In metabolic networks from twelve organisms, non-hub connecting nodes were more conserved across species than provincial hubs.Communities were detected by modularity maximization with simulated annealing, after which within-module degree and participation properties assigned node roles.
- Legislative Networks.: Legislative-network research applies community detection to study how social relationships shape political outcomes.The paper identifies community detection as central to its work on legislative networks.
- Legislative Networks.: House committee assignments form a Representative–committee bipartite graph that can be projected into a weighted committee network with normalized edge strengths.The construction uses assignments during a single two-year term of the U.S. House of Representatives.
- Legislative Networks.: Cosponsorship networks expose politicians’ social connections, while centrality measures identify influential figures such as Bob Dole, John McCain, and Ted Kennedy.Close legislative collaboration is treated as evidence of friendly or cordial relations.
Summary and Outlook.
Network community detection has grown rapidly with large-scale data and many developing methods, but interpreting and validating detected communities remains primitive and largely open. Future work should improve rigor, scalability, applicability to complex graphs, and correspondence between structural and functional communities.
- Field growth: Network community research has expanded across sociology, computer science, statistics, and other disciplines, especially since the seminal 2002 paper.The field is described as thriving, with many techniques under development.
- Open problems: Understanding what detected communities mean remains primitive, motivating a call for mathematicians to address unresolved problems.The article explicitly frames this as a call to arms for the mathematics community.
- Scalability: Massive data has produced enormous networks, while NP-completeness of modularity maximization motivates fast algorithms that still identify reasonable community structures.Some existing algorithms scale sufficiently for networks with millions of nodes or more.
- Validation practice: For real-world networks, confidence should come from structures that remain similar across several computationally tractable community-detection algorithms.The passage presents agreement across multiple methods as current best practice.
- Validation and interpretation: Validating and using identified communities is almost completely open, although missing-edge inference and demographic characterization offer promising directions.Partitions obtained algorithmically or from external demographics can help compare algorithms and infer node characteristics from partial demographic information.
- Generalization and meaning: Community-detection methods should address bipartite and directed graphs and clarify whether structurally inferred communities represent functional organization.Structural communities are imperfect proxies, and their mapping to social, biological, or other functional organization is often unclear.