Source-linked AI summary
Community Structure in Graphs
Santo Fortunato, Claudio Castellano
TL;DR
Community detection seeks meaningful graph partitions despite ambiguity over community definitions, overlapping membership, hierarchies, and the enormous number of possible partitions. This review surveys traditional and newer methods, including approaches intended to extract community structure without preliminary inputs, while documenting important limits of definitions, quality measures, and scalability.
Problem
Community detection lacks a unique community definition and a reliable way to select among exponentially many partitions, including overlapping and hierarchical alternatives.
Method
The review synthesizes traditional clustering and graph-partitioning approaches alongside newer divisive, modularity-based, and other community-detection methods.
Results
New methods can extract graph partitions without preliminary knowledge or inputs about the community structure.
Takeaways & Limitations
Community-detection methods differ in how they define or generate communities, handle required inputs, and evaluate partition quality.
Takeaways & Limitations
Modularity values cannot be compared across graphs of different sizes and can be fairly large even for random graphs.
Abstract
from arXiv · showhide
Graph vertices are often organized into groups that seem to live fairly independently of the rest of the graph, with which they share but a few edges, whereas the relationships between group members are stronger, as shown by the large number of mutual connections. Such groups of vertices, or communities, can be considered as independent compartments of a graph. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. The task is very hard, though, both conceptually, due to the ambiguity in the definition of community and in the discrimination of different partitions and practically, because algorithms must find ``good'' partitions among an exponentially large number of them. Other complications are represented by the possible occurrence of hierarchies, i.e. communities which are nested inside larger communities, and by the existence of overlaps between communities, due to the presence of nodes belonging to more groups. All these aspects are dealt with in some detail and many methods are described, from traditional approaches used in computer science and sociology to recent techniques developed mostly within statistical physics.
1 Introduction
Graphs represent biological, social, technological, and information systems, whose organization often differs from random graphs. Community structure captures groups with many internal connections and fewer links between groups, motivating community detection across several applications.
- Graph analysis represents biological, social, technological, and information networks, making graph structure important for understanding these systems.
- Real networks differ from random graphs through broad degree distributions and locally concentrated edges within groups.Community structure is the resulting pattern of high internal connectivity and low connectivity between groups.
- Communities can represent related webpages, metabolic pathways, social groups, or compartments in food webs.
- Community detection classifies vertices by their positions, distinguishing central vertices from boundary vertices that mediate relationships between communities.Central vertices may support control and stability, while boundary vertices lead exchanges between groups.
- The task identifies modules using graph topology, including partitions that can reduce communication between processor groups in parallel computing.
- Divisive methods remove edges connecting communities and generate hierarchical partitions, while Girvan–Newman identifies such edges using edge betweenness.
2 Elements of Community Detection
Community detection formalizes ambiguous notions of graph organization into definitions, quality criteria, and methods that must handle overlapping and hierarchical structures. The task is difficult because possible partitions are super-exponentially numerous, while measures such as modularity have important scope and comparison caveats.
- Definition and ambiguity: Community detection has no unique formal definition, allowing overlapping or nonoverlapping communities and single partitions or hierarchies.Different legitimate interpretations create a comparison problem: one must identify which partition or hierarchy best expresses community structure.
- Definition and ambiguity: Local definitions identify communities from a subgraph and its immediate neighborhood, using criteria such as cliques, n-cliques, or k-plexes.Clique-based approaches can be computationally demanding, and larger cliques are rare in real networks.
- Definition and ambiguity: Global definitions compare internal connectivity with a null model, commonly a degree-preserving randomized graph, as in modularity.A subset is considered a community when its internal edges exceed the null model’s expected number; motif-based generalizations also exist.
- Definition and ambiguity: Similarity-based definitions group vertices according to quantitative pairwise similarity, which may derive from distances or eigenvector components.Hierarchical clustering uses such similarities but requires an additional criterion to close communities.
- Quality functions: Modularity evaluates partitions by comparing observed within-module edges with expectations from a degree-preserving random graph, with larger positive differences indicating stronger modularity.It is also used for community detection, partition stability assessment, and graph reduction while preserving community structure.
- Quality functions: Modularity values cannot be directly compared across differently sized graphs, random graphs can yield fairly large values, and optimization may merge subgraphs below a characteristic size.These effects create a serious bias when modularity optimization is used to identify communities.
3 Computer Science: Graph Partitioning
Graph partitioning divides vertices into predefined groups while minimizing intergroup edges, whereas spectral methods use Laplacian eigenvectors to approximate low-cut splits. These methods can be fast and effective, but their assumptions and required group specifications limit their suitability for community detection.
- Graph partitioning divides vertices into g predefined-size groups while minimizing the cut size, defined as the number of edges between groups.
- The partitioning problem is fundamental across computing applications, but most variants are NP-hard.
- The Kernighan-Lin algorithm optimizes a benefit function by swapping equal-sized vertex subsets between two predefined groups and scales as O(n^2) in the reported setting.It permits some swaps that decrease the objective to reduce the risk of becoming trapped in local maxima.
- Spectral bisection represents a two-group split with an index vector and uses the Laplacian spectrum, with a near-zero λ2 and Fiedler vector indicating weakly linked groups.Ordering Fiedler-vector components yields candidate groupings, and the smaller-cut partition is selected when group sizes disagree.
- When λ2 and λ3 are well separated, Lanczos computation is faster than calculating the complete eigenvector set, whose reported cost scales as O(n3).The resulting partitions are generally good and can be further improved with Kernighan-Lin.
- Graph partitioning is unsuitable for community detection when the number and sizes of communities are unknown, and iterative bisection is not reliable.Leaving the number of groups unconstrained makes the minimum-cut solution trivial: all vertices form one module.
4 Social Science: Hierarchical and K-Means Clustering
Social-network clustering groups vertices using similarity, either through hierarchical merging or k-means assignment in a metric space. Hierarchical methods expose multiple partitions without requiring cluster counts, while both approaches have important limitations in selecting or representing community structure.
- Social clustering partitions vertices so members of the same cluster are more similar to one another than to members of different clusters.
- Hierarchical clustering: Hierarchical clustering repeatedly merges the two most similar groups, producing a sequence of partitions represented by a dendrogram.Group similarity can use single, complete, or average linkage.
- Hierarchical clustering: Similarity measures can compare adjacency patterns, structural equivalence, independent paths, or weighted sums of paths whose length-l contributions are scaled by α^l with α < 1.The weighting exponentially suppresses long paths so the total sum converges.
- Hierarchical clustering: Hierarchical clustering avoids prior knowledge of cluster number and size, but it does not select among its partitions, depends on the similarity measure, and can miss central community vertices.
- K-means clustering: K-means embeds vertices in a metric space, selects k centroids, and assigns each vertex to one centroid while minimizing total dissimilarity.
- K-means clustering: K-means requires the number of clusters in advance, and its metric-space embedding may be artificial for some graphs.
5 New Methods
New community-detection methods address limits of traditional graph partitioning by using divisive removal, modularity optimization, spectral representations, and dynamical or statistical-physics processes.
- Overview: Traditional approaches often require the number and size of clusters as inputs, while hierarchical methods still require selecting the best partition.These limitations motivate newer algorithms reviewed in this section.
- 5.1 Divisive Algorithms: Divisive algorithms remove edges identified as connecting communities, producing disconnected clusters and a hierarchy of partitions represented by dendrograms.Edge betweenness is one criterion for identifying such intercommunity edges.
- 5.2 Modularity Optimization: Modularity maximization seeks high-quality partitions but is NP-hard, so practical algorithms find approximations using greedy, extremal-optimization, or spectral techniques.The spectral modularity method typically runs in O(n^2 log n) on sparse graphs and is faster and slightly more accurate than extremal optimization, especially for large graphs.
- 5.3 Spectral Algorithms: Spectral algorithms represent vertices through eigenvector components, exploiting the tendency of vertices in the same community to receive similar coordinates.Donetti and Muñoz use Laplacian eigenvectors to represent vertices and assess their similarities.
- 5.4 Dynamic Algorithms: Process-based methods include Potts models, random walks, and synchronization dynamics, with synchronization recovering partitions across coupling strengths and selecting the one with largest modularity.Synchronization algorithms scale as O(mn), or O(n^2) on sparse graphs, but may be unreliable when communities differ greatly in size.
6 Testing Methods
Community-detection methods are tested by comparing their partitions with known or reference partitions using similarity measures. Benchmarks include synthetic graphs with tunable community mixing and real networks whose community structure is independently documented, but both settings have important limitations.
- Comparing partitions: Partition similarity measures, including information-theoretic measures and the Jaccard index, quantify agreement between detected and reference communities.The Jaccard index counts vertex pairs placed together in both partitions versus pairs assigned inconsistently.
- Synthetic benchmarks: Figure 11 illustrates the benchmark at zin = 15, zin = 11, and zin = 8, with the four groups basically invisible at zin = 8.The benchmark tests similarity between an algorithm’s partition and the natural four-group partition.
- Synthetic benchmarks: The Girvan–Newman benchmark uses 128 vertices in four equal groups, with internal degree zin controlling the mixing between communities.When zin is near 16, groups are clear; when zin <= 8, intercommunity edges make the structure fuzzy.
- Benchmark limitations: Synthetic benchmarks can misidentify the reference partition because random edge placement may give some vertices more connections outside than inside their initial group.For such realizations, treating the four initial groups as the graph’s real partition is inappropriate.
- Real-network benchmarks: Real-network tests commonly use a limited number of examples with precise vertex information, including Zachary’s karate club network.The karate club network records relationships observed over two years before a conflict divided the club.
- Benchmark limitations: Topology-only communities need not coincide with reasonable communities defined using non-topological information in real networks.This caveat applies to frequently used networks such as American college football teams and bottlenose dolphins.
7 The Mesoscopic Description of a Graph
Community partitions provide a mesoscopic description in which communities become the graph’s elementary units between the vertex and whole-graph scales. Their size distributions, overlaps, and vertex roles reveal organization beyond individual connections.
- Community sizes: Community-size distributions are skewed, with power-law tails having exponents between 1 and 3 rather than a characteristic community size.Small communities commonly coexist with large ones; Figure 13 shows the Amazon purchasing network partitioned by greedy modularity optimization.
- Overlapping communities: Overlapping communities can be represented as a network whose vertices are communities and whose edges indicate overlaps between them.This community-overlap network has an initial exponential degree decay followed by a slower power-law decay, reproducible through preferential attachment.
- Vertex roles: Vertex roles can be classified using the z-score and participation ratio, which measure within-module position and how edges are distributed across modules.Guimerá and Amaral use these indices to distinguish seven vertex roles.
- Vertex roles: Connector vertices with many cross-module edges are often more evolutionarily conserved metabolites in metabolic networks.The passage presents this correlation as an example of how community-based roles may relate to vertex functions.
8 Future Directions
Community-detection methods have scaled to graphs with millions of vertices and increasingly extract partitions without specifying community structure in advance. They also address overlapping and hierarchical communities, but no method yet combines meaningful partitions, these realistic features, and short runtime without serious limitations.
- Partitions can now be found in graphs with up to millions of vertices as community-detection methods have improved their scalability.
- New methods can infer the number of communities from graph topology instead of requiring it as an input.
- Recent algorithms can select one or a few meaningful partitions rather than returning an undiscriminated hierarchy of alternatives.
- Overlapping and hierarchical communities are increasingly incorporated into community-detection methods.
- No existing method simultaneously guarantees meaningful partitions, handles overlap and hierarchy, and operates in a short time.
- Community detection remains important for biology because quantitative network data now include gene-regulatory, protein-interaction, and metabolic systems.