Community detection in graphs

Santo Fortunato

Source-linked AI summary

Community detection in graphs

Santo Fortunato

arXiv:0906.0612v2Jun 3, 2009physics.soc-phcond-mat.stat-mechcs.IRphysics.bio-phphysics.comp-phq-bio.QM

TL;DR

Community detection remains difficult because graphs can admit multiple meaningful clusterings and quality scores do not always establish genuine community structure. This paper surveys community concepts, detection methods, testing practices, significance, and applications, reporting that Infomap and two other fast methods perform best in comparative tests.

Problem
Community detection lacks a precise theoretical framework and reliable benchmarks for determining what communities are and which algorithms perform best.
Method
The paper provides a detailed interdisciplinary survey of community concepts, clustering methods, significance assessment, algorithm testing, and real-network applications.
Results
Infomap performs best in comparative tests, while methods by Blondel et al. and Ronhovde and Nussinov also perform well and are essentially linear in system size.
Takeaways & Limitations
Community detection can expose meaningful large-scale structure in real networks, including linguistically homogeneous groups in a 2.6-million-vertex Belgian phone network.
Takeaways & Limitations
Real-world graphs may contain multiple meaningful hierarchical partitions, making it difficult to determine which clustering is most relevant.

Abstract

from arXiv · show

The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i. e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e. g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks.

I. INTRODUCTION … B. Communities

Community detection seeks graph-topology-based modules and hierarchies, motivated by widespread community structure across social, biological, technological, and information networks. The problem is ambiguously defined and complicated by directed, overlapping, multipartite, weighted, and computationally demanding graph settings.

II. COMMUNITIES IN REAL-WORLD NETWORKS: Community structure appears across social, biological, technological, and information networks, where groups can correspond to meaningful functional or topical units.Examples include social groups, protein functions, web-page topics, and collaboration disciplines.
I. INTRODUCTION: Community detection supports applications including Web-service placement, graph storage and path searches, compact ad hoc routing tables, and classification of structurally central or boundary vertices.These uses connect clustering to system performance and interpretation of vertex roles.
I. INTRODUCTION: Community detection identifies graph modules and possibly their hierarchical organization using only information encoded in graph topology.The review traces the problem across several disciplines and emphasizes its broad relevance.
II. COMMUNITIES IN REAL-WORLD NETWORKS: Real networks commonly require models beyond simple partitions because edges may be directed, vertices may overlap communities, and graphs may be multipartite or weighted.Directedness can improve partitions but complicates analysis; overlapping memberships greatly increase possible covers, while projections of multipartite graphs lose information.
III. ELEMENTS OF COMMUNITY DETECTION: The concepts of community and partition are not rigorously defined, so graph clustering involves arbitrariness, common sense, and multiple legitimate resolutions.The literature consequently contains many different recipes for addressing the problem.
III. ELEMENTS OF COMMUNITY DETECTION: Structural clusters are meaningful primarily in sparse graphs with m of order n; when m ≫ n, edge distributions become too homogeneous and the task approaches data clustering.For weighted graphs with heterogeneous weights, communities may instead appear as subgraphs with high internal weight density.
A. Computational complexity: Computational efficiency is essential because real-network datasets can contain millions of vertices and billions of edges.Complexity is expressed through scaling in vertices and edges, and practical methods must avoid excessive computational and memory demands.
A. Computational complexity: Many clustering problems are NP-hard, making exact algorithms impractical beyond small systems and motivating lower-complexity approximation algorithms.Even polynomial-time methods may remain too slow for large systems of interest.

1. Basics … 4. Definitions based on vertex similarity

The paper frames communities through internal cohesion, external separation, connectedness, and multiple definition classes. It distinguishes local, global, and vertex-similarity approaches, with similarity inferred from geometry, adjacency, paths, or random walks.

1. Basics: No universally accepted community definition exists, but most approaches seek more internal than external edges.The appropriate definition depends on the system and intended application.
1. Basics: A community should be connected, while its internal density exceeds the graph’s average and its external density remains much smaller.Clustering methods generally seek a tradeoff between large δint(C) and small δext(C).
2. Local definitions: Local definitions evaluate a subgraph and possibly its immediate neighborhood, using criteria such as mutuality, reachability, degree, and internal-versus-external cohesion.These criteria underlie clique, n-clique, n-clan, n-club, k-plex, and k-core constructions.
2. Local definitions: Local cohesion is insufficient when a subgraph also connects strongly to the rest of the graph, so community definitions compare internal and external cohesion.Fitness measures quantify how strongly a subgraph satisfies a cohesion property, with larger fitness indicating a more definite community.
3. Global definitions: Global definitions treat communities as essential graph components and often identify structure indirectly through global properties or differences from a random graph.Null models preserve selected structural features while randomizing others for comparison.
4. Definitions based on vertex similarity: Vertex-similarity definitions group each vertex with vertices most similar under a chosen local or global reference property.Similarity measures support hierarchical, partitional, and spectral clustering.
4. Definitions based on vertex similarity: When vertices embed in Euclidean space, distances or cosine similarity measure their relationships; otherwise, similarity can be inferred from adjacency patterns and structural equivalence.Structurally equivalent vertices have the same neighbors, even if they are not adjacent.
4. Definitions based on vertex similarity: Other similarity measures use independent paths, weighted path counts, or random-walk behavior such as commute time, visit probabilities, and escape probability.Maximum flow relates to the number of independent paths, while weighted path sums avoid the infinite total number of paths.

C. Partitions · 2. Quality functions: modularity

The section defines graph partitions, covers, and hierarchical organization, then explains why exhaustive evaluation is infeasible and introduces quality functions—especially modularity—for assessing community structure. It also presents modularity’s null-model basis, interpretation, and limitations.

C. Partitions: A partition assigns every vertex to one cluster, whereas a cover allows vertices to belong to overlapping or fuzzy communities.
C. Partitions: The number of graph partitions is governed by Stirling and Bell numbers, with the total growing faster than exponentially in graph size.Therefore, enumerating or evaluating every partition is infeasible except for very small graphs.
C. Partitions: Partitions may be hierarchically ordered, representing nested communities at multiple organizational scales.A dendrogram encodes these alternatives, with horizontal cuts corresponding to graph partitions.
2. Quality functions: modularity: A good clustering is difficult to define: Kleinberg’s theorem shows that scale-invariance, richness, and consistency cannot all hold simultaneously.For graph clustering, richness and consistency remain meaningful, while scale-invariance lacks meaning without a distance function.
2. Quality functions: modularity: A quality function assigns a number to each graph partition, providing a quantitative criterion when algorithms return multiple candidate partitions.Additive quality functions express partition quality as the sum of individual cluster qualities; performance and coverage are examples.
2. Quality functions: modularity: Modularity compares a graph’s within-community edge density with its expected density under a chosen null model, using the adjacency matrix and community assignments.Under the stub-matching model, the expected number of edges between vertices i and j is Pij = kikj/2m.
2. Quality functions: modularity: A cluster contributes positively to modularity when its internal edges exceed the null-model expectation, so larger positive modularity indicates better-defined communities.Modularity can also be expressed through inter-cluster edges and their expected number.
2. Quality functions: modularity: Because maximum modularity generally increases with graph size or the number of well-separated clusters, it should not be used to compare networks of different sizes directly.Modularity optimization is widely used for community detection and can also assess partition stability and support graph visualization.

IV. TRADITIONAL METHODS … C. Partitional clustering

Traditional clustering methods include graph partitioning, hierarchical clustering, and partitional clustering, each with distinct assumptions and limitations. Graph partitioning and partitional clustering require prior cluster information, whereas hierarchical clustering avoids that requirement but produces ambiguous, similarity-dependent results.

A. Graph partitioning: Graph partitioning divides vertices into predefined groups while minimizing the cut size, the number of edges running between groups.The number and sizes of groups must be specified to avoid trivial solutions such as one cluster containing all vertices.
A. Graph partitioning: Graph partitioning is useful in computing and circuit design, but its algorithms are often NP-hard and are not well suited to community detection.Community detection generally lacks prior knowledge of the number or sizes of groups, and iterative bisection is not reliable for producing multiple communities.
B. Hierarchical clustering: Hierarchical clustering computes pairwise vertex similarities and identifies groups through agglomerative merging or divisive splitting.Agglomerative methods proceed bottom-up from singleton clusters, whereas divisive methods proceed top-down by removing edges between dissimilar vertices.
B. Hierarchical clustering: Hierarchical clustering does not require the number or sizes of clusters beforehand, but it cannot inherently select the best partition and depends on the chosen similarity measure.The method also constructs a hierarchical structure that may be artificial.
C. Partitional clustering: Partitional clustering preassigns k clusters, embeds vertices in a metric space, and optimizes a cost function based on distances among points or from points to centroids.Common objectives include compactness through cluster diameters or average pairwise distances, and centroid-based maximum or average distances.
C. Partitional clustering: The most popular partitional technique is k-means clustering, which minimizes total intra-cluster distance through Lloyd’s iterative centroid-assignment procedure.The algorithm alternates assigning each vertex to its nearest centroid with recomputing cluster centers.
C. Partitional clustering: Partitional clustering cannot derive the number of clusters, and representing a graph in a metric space may be natural for some graphs but artificial for others.These limitations parallel those of graph partitioning methods.

D. Spectral clustering … B. Other methods

The paper presents spectral clustering as an eigenvector-based transformation that reveals graph communities, then surveys divisive methods that remove structurally important intercommunity edges. It emphasizes algorithmic tradeoffs, including normalization, computational cost, stopping criteria, and limitations on graph structure and community overlap.

D. Spectral clustering: Spectral clustering maps objects or graph vertices into an eigenvector-defined space, where standard clustering methods can reveal structures obscured in the original representation.The eigenvector transformation makes cluster properties more evident and can separate points that direct k-means cannot resolve.
D. Spectral clustering: The Laplacian is central to spectral clustering: disconnected components produce zero eigenvalues, while weakly linked clusters produce near-zero eigenvalues and spatially separated vertex-vector groups.For k connected components, the unnormalized Laplacian has k zero eigenvalues; weak links perturb these into small nonzero eigenvalues.
D. Spectral clustering: Normalized Laplacians become especially promising when vertex degrees are highly heterogeneous, whereas their distinction from unnormalized Laplacians is small when degrees are similar.Normalization also alleviates problems caused by small eigenvector components associated with low-degree vertices.
D. Spectral clustering: Unnormalized and normalized spectral clustering compute leading Laplacian eigenvectors, represent vertices in k-dimensional space, and partition the resulting vectors with methods such as k-means.Relaxed ratio-cut and normalized-cut minimization yield the corresponding unnormalized and normalized spectral representations.
V. DIVISIVE ALGORITHMS: Divisive algorithms detect communities by identifying and removing intercommunity edges until clusters become disconnected, extending hierarchical clustering without major conceptual changes.Their central challenge is finding a property that distinguishes edges joining different communities.
A. The algorithm of Girvan and Newman: Girvan–Newman repeatedly computes edge centralities, removes an edge with maximal centrality, recalculates centralities, and iterates to generate a hierarchy of partitions.The method considers geodesic, random-walk, and current-flow betweenness; edge betweenness is shortest-path participation.
A. The algorithm of Girvan and Newman: O(n2) versus O(n3) on sparse graphs, edge betweenness is faster than random-walk or current-flow alternatives and performs better in practical applications, though Girvan–Newman remains slow.With current computational resources, the algorithm is applicable to sparse graphs with up to n ∼10000 vertices.
B. Other methods: Other divisive methods use local cycle structure or information centrality: low edge clustering coefficients indicate likely intercommunity edges, while information centrality repeatedly removes the most central edge.The cycle-based method can stop when all clusters satisfy strong or weak community conditions, but it may perform poorly in graphs with few cycles; computing all information centralities requires O(m2n).

VI. MODULARITY-BASED METHODS … 4. Spectral optimization

The paper surveys modularity-based community-detection methods, emphasizing the popularity of modularity maximization despite its intractable exhaustive optimization. It compares greedy, stochastic, extremal-optimization, and spectral approaches, including their mechanisms, accuracy, and computational costs.

VI. MODULARITY-BASED METHODS: Modularity is the most widely used quality function, and high modularity is assumed to indicate good graph partitions.This assumption motivates modularity maximization as the dominant class of community-detection methods, although it is not universally valid.
A. Modularity optimization: Exhaustive modularity optimization is impossible because even small graphs have huge numbers of possible partitions.Consequently, practical methods seek approximate optima through heuristics or relaxations.
1. Greedy techniques: Greedy agglomeration starts with one cluster per vertex and repeatedly merges groups when the merger maximizes modularity increase.The procedure explores n partitions, ranging from n clusters to one, while retaining the best modularity encountered.
1. Greedy techniques: Greedy optimization tends to form large communities at the expense of small ones, often producing poor modularity maxima despite later refinements.Normalizing merger gains by incident-edge fractions, local-search refinement, and stochastic perturbations can improve the resulting optima, but greedy accuracy remains inferior to other techniques.
2. Simulated annealing: Simulated annealing searches the state space probabilistically, accepting every improvement and otherwise accepting a decrease with probability exp(β∆F).The parameter β controls the stochastic noise in the search.
3. Extremal optimization: Extremal optimization updates the partition by shifting the vertex with the lowest local fitness, yielding very good estimates of the modularity maximum.Its fitness ranking costs O(n log n), reducible to O(n) with heaps, while selecting a vertex can add O(log n).
4. Spectral optimization: Spectral optimization represents bipartitions with ±1 vectors and optimizes modularity using eigenvectors of the modularity matrix.Recursive subdivision continues only when modularity increases, with modularity always computed from the original graph’s full adjacency matrix.
4. Spectral optimization: O[n(m + n)] is the stated cost of a graph bipartition, becoming O(n2) on sparse graphs; the full hierarchical optimization requires subsequent bipartitions.A related Q-Laplacian relaxation converts modularity maximization into a spectral partitioning problem, while Kcut can achieve O[(n+m) log K] complexity for at most K clusters.

5. Other optimization strategies · B. Modifications of modularity

The paper surveys optimization strategies for modularity and extensions that adapt it to weighted, directed, overlapping, localized, multiscale, motif-based, and signed networks. These approaches relax computational formulations or modify modularity’s null model and structural assumptions to address broader clustering settings.

5. Other optimization strategies: Modularity maximization can be formulated as linear or quadratic programming, but the integer linear formulation is NP-hard; relaxing variables to real values yields a tractable approach.The linear formulation uses link variables xij and triangle inequalities; the integer constraint causes NP-hardness, while real-valued relaxation makes the problem solvable in polynomial time.
5. Other optimization strategies: A vector relaxation transforms binary spin variables into normalized n-dimensional vectors, producing a polynomially solvable optimization problem.This follows an NP-complete two-cluster formulation in variables si = ±1 and replaces scalar products with vector inner products.
5. Other optimization strategies: Mean field annealing and genetic algorithms provide alternative modularity-optimization strategies based respectively on self-consistent Gibbs probabilities and evolving chromosome-encoded candidate solutions.Mean field annealing is deterministic, while genetic algorithms iteratively manipulate candidate solutions according to an objective-function fitness.
B. Modifications of modularity: Modularity extends to weighted graphs by replacing degrees with vertex strengths and the edge count with total edge weight, so expected edge weight is compared with actual weight.The weighted null model uses sisj/2W as the expected weight of edge ij, and weighted modularity remains generally valid when weights are approximated with sufficiently small integer units.
B. Modifications of modularity: Directed modularity has a general weighted form, but it may fail to distinguish directed flow from no flow when vertices share identical indegrees and outdegrees.Kim et al. therefore proposed a diffusion-based definition inspired by PageRank, following similar objections raised by Rosvall and Bergstrom.
B. Modifications of modularity: Overlapping-community extensions are non-unique: proposed formulations reduce edge contributions according to membership multiplicity or use generalized membership coefficients and functions.The function F must preserve properties such as zero modularity for the one-community cover, but otherwise its choice is largely arbitrary and tested a posteriori.
B. Modifications of modularity: Alternative quality functions and null models modify modularity’s comparison between observed and expected structure; absolute performance variants outperform relative variants on artificial benchmarks.Localized modularity instead computes expected internal edges from a module and neighboring modules, producing more accurate partitions on school, metabolic, and protein-protein interaction networks, although it is unbounded by 1.
B. Modifications of modularity: Spin-glass and motif-based generalizations introduce resolution or higher-order structure, while signed-network formulations separately account for positive and negative correlations.In the spin-glass model, γ controls the number of clusters across scales; motif modularity compares motif densities with null-model expectations, and signed modularity combines positive and negative contributions.

C. Limits of modularity

Modularity has important limits: a high maximum can appear in random graphs, while z-score tests can yield false positives and false negatives. Its null model also creates resolution limits that hide small communities, and its optimization landscape may contain exponentially many near-optimal partitions.

Significance of modularity: A large Qmax does not necessarily indicate community structure, because random-graph fluctuations can produce apparent communities.The z-score compares Qmax with the null-model average in standard-deviation units; although z ≫1 indicates strong structure and cutoffs of 2–3 are customary, the approach can produce false positives and false negatives.
Resolution limit: Modularity’s null model imposes a resolution limit: even a single edge can keep sufficiently small subgraphs together, including maximally dense cliques.Consequently, optimizing modularity may merge multiple natural cliques, leaving many small communities in diverse real graphs undetected.
Resolution limit: The resolution limit follows from assuming that every vertex can interact with every other vertex, an assumption questionable for large systems such as the Web.A limited-horizon interaction model is presented as more reasonable for such systems.
Generalized quality functions: √γm is the limit scale for undetectable clusters in the generalized formulation, and tuning γ can arbitrarily vary the corresponding resolution scale.For γ = 1, the modularity resolution limit is recovered; weighting edges can also enable very high-resolution detection while using modularity optimization.
Optimization landscape: An exponential number of distinct partitions can have modularity values very close to the global maximum, especially in networks with hierarchical community structure.This modularity-landscape degeneracy complicates identifying a unique meaningful partition.

VII. SPECTRAL ALGORITHMS … B. Random walk

The paper reviews spectral and dynamic approaches to community detection, using graph eigenvectors, spin interactions, and random-walk processes to identify, measure, or refine communities. These methods range from spectral embeddings and localized eigenvectors to persistence-based quality functions and diffusion-based clustering.

VII. SPECTRAL ALGORITHMS: Spectral algorithms use eigenvectors of graph matrices, especially Laplacian, transfer, adjacency, and stochastic matrices, to reveal partitions or vertex similarities.Spectral techniques are reviewed as methods proposed mostly for graph clustering, extending earlier spectral clustering ideas.
VII. SPECTRAL ALGORITHMS: Transfer-matrix eigenvectors encode random-walk currents, while a localized eigenvector’s participation ratio estimates the size of its associated community.Cluster significance can be assessed by comparing the participation ratio with that of a random graph having the same expected degree sequence.
VII. SPECTRAL ALGORITHMS: Laplacian spectral methods embed vertices as points using eigenvector components, then seek compact groups; the required dimension can be selected by maximizing modularity across candidate dimensions.The eigenvectors can be computed with the Lanczos method, but the number needed for clean cluster separation is not known a priori.
VIII. DYNAMIC ALGORITHMS: Dynamic algorithms analyze processes on graphs, including spin-spin interactions, random walks, and synchronization.The supplied material subsequently develops spin models and random-walk methods as dynamic approaches.
A. Spin models: Potts-model and FRFIM methods assign spin states or fields to vertices so that homogeneous spin clusters can recover graph communities, including in weighted graphs.FRFIM implementations can reach complexity O(n^θ), enabling analysis of systems with millions of vertices; Barabási-Albert tests show no community structure.
B. Random walk: Random-walk methods exploit community persistence: dense internal connectivity keeps walkers inside communities, supporting distance, signaling, hierarchical, and diffusion-based clustering.These algorithms can be trivially extended to weighted graphs.
B. Random walk: Delvenne et al.’s stability function unifies random-walk community measures: at t = 1 it equals Newman-Girvan modularity, while as t →∞ it yields the Fiedler partition.Stability selects the partition with the largest value of r(t; H), based on the probability that a walk remains within clusters over time.
B. Random walk: The Markov Cluster Algorithm alternates transfer-matrix diffusion with inflation, raising entries to a real-valued power α to enhance strong within-community flows.After inflation, each matrix column is renormalized so its entries sum to one.

C. Synchronization · IX. METHODS BASED ON STATISTICAL INFERENCE · A. Generative models

The section presents synchronization-based community detection and statistical-inference methods, emphasizing dynamical identification, generative modeling, Bayesian fitting, and important methodological limitations. Synchronization reveals communities through correlated oscillator dynamics, while generative approaches infer classifications from graph connectivity under explicit model assumptions.

C. Synchronization: Synchronization identifies communities by placing oscillators on graph vertices, where units within the same community synchronize before those in different communities.Local synchronization is measured through oscillator correlations and visualized using thresholded dynamic connectivity matrices.
C. Synchronization: Synchronization-based algorithms vary coupling by edge betweenness, recover partitions from the whole graph to singleton vertices, and select the partition with maximum modularity.Inter-cluster edges are suppressed because their high betweenness reduces their coupling strength.
C. Synchronization: O(mn), or O(n2) on sparse graphs, is the time complexity reported for the synchronization algorithm, which performs well on practical examples including Zachary’s karate club and the Girvan–Newman benchmark.A synchronization-based technique also detects overlapping communities through interfacial vertices with intermediate oscillation frequencies.
C. Synchronization: Synchronization-based algorithms may be unreliable when communities differ greatly in size, an issue for which tests are still missing.
IX. METHODS BASED ON STATISTICAL INFERENCE: Statistical-inference methods seek the model that best fits a graph by assigning vertices to classes according to their connectivity patterns, with Bayesian inference as the main focus.For graph clustering, the evidence is the graph structure, represented by an adjacency or weight matrix.
A. Generative models: Bayesian generative models maximize posterior support from likelihood and prior distributions, but computing the required integral is a major challenge and choosing the prior is non-obvious.Generative models differ in their model choices and in how they address these two issues.
A. Generative models: The general parameterization uses community assignments {q}, model parameters {π}, and the number of clusters k; Hastings instantiates it with the planted partition model using pin and pout.In that model, same-group and different-group vertex pairs connect with probabilities pin and pout, respectively, and pin > pout yields community structure.
A. Generative models: Newman and Leicht use a mixture model with expectation-maximization to infer the most likely vertex classification without specifying the structure type, but normalization prevents detection of intuitive directed bipartite groups.Their method can detect structures other than communities, whereas the bipartite-graph failure follows from requiring every group to have non-zero outdegree.

B. Blockmodeling, model selection and information theory · X. ALTERNATIVE METHODS

The section presents blockmodeling and information-theoretic approaches that simplify or compress graph structure, alongside alternative local, dynamical, and graph-transformation methods for detecting groups.

B. Blockmodeling, model selection and information theory: Blockmodeling decomposes graphs into vertex classes with common properties, typically using structural or regular equivalence to obtain a simpler graph description.Structural equivalence means having the same neighbors, or more generally the same ties to the same vertices.
B. Blockmodeling, model selection and information theory: A blockmodel assigns vertices to q classes and represents their interclass connectivity with a q×q image-graph adjacency matrix.Different image graphs encode different structural patterns; self-edges recover Newman-Girvan modularity for directed graphs.
B. Blockmodeling, model selection and information theory: Model selection seeks simple models that describe systems well, using heuristics such as AIC, BIC, MDL, and MML.Compression-based approaches balance a compact representation against preserving information about the original graph.
B. Blockmodeling, model selection and information theory: Rosvall and Bergstrom formulate community detection as compressing information about graph topology or random-walk diffusion, with Huffman coding naming vertices and communities organizing the code.The communication formulation selects a partition whose signal retains the most information about the original topology while avoiding the uncompressed X = Y solution.
B. Blockmodeling, model selection and information theory: The information bottleneck method compresses graph topology while preserving predefined information by minimizing mutual information between the input variable X and partition variable Z.The retained information is represented by a relevant variable Y.
X. ALTERNATIVE METHODS: Label propagation repeatedly assigns each vertex a majority neighbor label, while balanced partitions make its objective formally equivalent to Newman-Girvan modularity.Applied to online social networks, the original algorithm often produces one giant community.
X. ALTERNATIVE METHODS: Local alternatives include L-shell community growth, Bridge Bounding based on boundary edges, and Clauset’s greedy maximization of local modularity R.Clauset’s local modularity uses community-boundary vertices to define the ratio of internal boundary-associated edges to edges incident on the boundary.
X. ALTERNATIVE METHODS: Other alternatives use clustering coefficients, prototype-graph approximation, resistor-network potentials, community volume, graph complements, or dynamical simplex evolution.The resistor-network method partitions graphs into two parts and can obtain more communities through iterative applications, while CLGA optimizes matrix-distance approximation.

XI. METHODS TO FIND OVERLAPPING COMMUNITIES … A. Multiresolution methods

The paper surveys methods for detecting overlapping communities, including clique-based, local-optimization, similarity-based, edge-based, and vertex-splitting approaches, then presents multiresolution methods for exploring cluster scales and hierarchy. These methods tune resolution or assess stability across scales, but scalability and reliable stability assessment remain important limitations.

XI. METHODS TO FIND OVERLAPPING COMMUNITIES: Overlapping-community methods address graphs in which vertices may belong to multiple communities, unlike standard partitions assigning each vertex to one community.The section introduces techniques specifically designed to detect overlapping communities and represent them as covers.
A. Clique percolation: Clique Percolation Method (CPM) defines communities as connected unions of adjacent k-cliques, exploiting dense internal clique structure and distinguishing community structure from random graphs.Two k-cliques are adjacent when they share k −1 vertices; analyzed sparse graphs with up to 10^5 vertices can be processed in reasonably short time.
A. Clique percolation: CPM’s meaningfulness depends on clique abundance: few cliques can make covers uninformative, whereas many cliques can produce trivial covers or chains unlike dense communities.The algorithm’s scalability depends on several factors and cannot be expressed in closed form.
B. Other techniques: Other overlapping methods define communities through local optimization, fuzzy membership, vertex similarity, edge grouping, or separating overlapping vertices before applying standard clustering.These approaches include normalized membership coefficients, similarity-matrix optimization, hierarchical link clustering, and a three-stage vertex-splitting procedure.
B. Other techniques: Edge-based communities can simplify overlap detection when intercluster and intracluster edges are easier to distinguish than overlapping vertices, though grouping edges is not inherently superior to grouping vertices.The paper illustrates this with communities formed by two triangles sharing a central vertex.
XII. MULTIRESOLUTION METHODS AND CLUSTER HIERARCHY: Multiresolution methods respond to modularity’s resolution limit by scanning cluster scales, which is important when graphs contain hierarchical communities at multiple organizational levels.A freely tunable parameter sets the characteristic size of the clusters to be detected; γ is the resolution parameter in the spin-glass framework.
A. Multiresolution methods: Pons and Arenas et al. assess community relevance or stability through scale-dependent persistence, using relevance ranges or plateaus in the number of clusters as indicators.Pons identifies peaks of partition relevance, while Arenas et al. find meaningful structures in plateau intervals that exclude standard modularity’s r = 0 in the described cases.
A. Multiresolution methods: Multiresolution methods face computational and statistical difficulties: some are very slow, and increasing numbers of partitions can obscure stability signatures in large graphs.Partition correlations may be more reliable for assessing stability than properties of individual partitions.

B. Hierarchical methods · XIII. DETECTION OF DYNAMIC COMMUNITIES

Hierarchical methods expose graph organization through dendrograms or recursively ordered affinity matrices, but raise unresolved questions about selecting meaningful levels and interpreting ensemble averages. Dynamic-community studies track communities across graph snapshots using stability, overlap, vertex-centric, and temporal-regularization approaches, revealing systematic persistence and evolution patterns.

B. Hierarchical methods: Hierarchical clustering produces a full dendrogram, but identifying relevant partitions requires an additional criterion and does not guarantee recovery of the graph’s actual hierarchy.These limitations concern both selecting hierarchical levels and validating whether the inferred organization reflects the underlying graph.
B. Hierarchical methods: Sales-Pardo et al. infer hierarchy by measuring modularity-based node affinity, reordering the affinity matrix toward block-diagonal form, and recursively analyzing detected subgraphs.Affinity is based on how frequently vertex pairs co-occur in communities from local modularity optima; blocks represent communities at successive levels.
B. Hierarchical methods: Clauset et al. model hierarchical organization with dendrograms whose internal nodes carry linking probabilities, selecting probabilities from observed edge densities and sampling compatible structures by Markov chain Monte Carlo.Because the hierarchy is represented by a dendrogram, the approach questions the notion of ranking partitions by relevance.
XIII. DETECTION OF DYNAMIC COMMUNITIES: Dynamic-community analysis remains immature because static graph clustering is already controversial and timestamped real-network data have been scarce.Recently available data sets enabled monitoring community evolution over time.
XIII. DETECTION OF DYNAMIC COMMUNITIES: Hopcroft et al. analyzed NEC CiteSeer citation-graph snapshots from 1990 to 2001 using cosine-similarity hierarchical clustering and identified communities robust to small vertex-removal perturbations.Their natural communities are defined as hierarchical-tree communities only slightly affected by minor graph perturbations.
XIII. DETECTION OF DYNAMIC COMMUNITIES: Palla et al. found that older communities are larger on average, while larger communities change composition faster and smaller communities remain essentially static across time.They studied mobile-phone calls and condensed-matter coauthorship networks, linking community states through relative overlap.
XIII. DETECTION OF DYNAMIC COMMUNITIES: Vertex dynamics depend on structural position: vertices strongly connected to their communities tend to remain attached to stable cores, whereas community evolution can also be classified through stability, sociability, popularity, and influence indices.Fenn et al. used a multiresolution method on time-dependent exchange-rate-correlation weights, fixing γ at the value occurring in most stability plateaus.
XIII. DETECTION OF DYNAMIC COMMUNITIES: Because independently clustering each timestamp can create noisy short-term partition changes, temporal methods balance snapshot quality against history cost using a tunable relative weight cp.The objective seeks partitions that fit current relational data while remaining similar to the preceding partition.

XIV. SIGNIFICANCE OF CLUSTERING · XV. TESTING ALGORITHMS · A. Benchmarks

The paper argues that high partition quality does not by itself establish meaningful community structure, so significance must be assessed through stability, null-model comparisons, entropy, or community-level tests. It then frames algorithm evaluation around known-solution benchmarks, emphasizing that benchmark realism and methodological cross-checking are essential because standard models can diverge from real networks.

XIV. SIGNIFICANCE OF CLUSTERING: High modularity does not necessarily indicate that a graph has a definite cluster structure, so partition quality alone cannot establish clustering significance.Many partitions may appear meaningful, and methods can struggle to discriminate among them.
XIV. SIGNIFICANCE OF CLUSTERING: Significant partitions should remain recoverable under limited graph perturbations, with stability assessed relative to a comparable null-model graph rather than by an absolute score.Clustering entropy ranges from S = 0 for the most stable partition to S = 1 for the most unstable, but its absolute value is not meaningful.
XIV. SIGNIFICANCE OF CLUSTERING: Entropy-based significance compares the entropy of the observed classification with random label permutations: Θ⃗k,⃗q ≤1 indicates irrelevance, whereas Θ⃗k,⃗q ≫1 indicates relevant clustering.The comparison controls for the degree sequence and fixed inter-cluster edge counts.
XIV. SIGNIFICANCE OF CLUSTERING: The C-score tests individual communities against random graphs, and a low C-score (≤5%) strongly indicates that a group is a genuine community rather than a random fluctuation.Removing vertices in increasing internal-degree order can reveal dense subgraphs through sharp score drops, although reliance on the worst vertex makes the measure noise-sensitive.
XV. TESTING ALGORITHMS: Algorithm testing is necessary because the literature lacks sufficient performance comparisons, making it impossible to identify the most reliable methods and encouraging choices based on popularity.The testing framework uses benchmark graphs with built-in communities, partition-similarity measures, and comparative evaluations.
A. Benchmarks: Benchmarks test algorithms by comparing their output with a known planted partition, but link fluctuations can make even existing communities undetectable.The Girvan-Newman benchmark uses four equal-sized groups with n = 128 and fixed average degree ⟨k⟩ = 16, while repeated realizations are averaged for each zout.
A. Benchmarks: The Girvan-Newman benchmark is structurally unrealistic because it gives vertices approximately equal degrees and communities exactly equal sizes, unlike real networks’ heterogeneous degree and community-size distributions.The LFR benchmark addresses this limitation with power-law degree and community-size distributions, has construction complexity O(m), and extends to directed, weighted, and overlapping graphs.
A. Benchmarks: Benchmark models require refinement because constant within- and between-community linking probabilities are unrealistic, while real-network tests cover few cases and should be cross-checked across clustering methods.Agreement among algorithms is useful, but graph-based communities need not coincide with groups defined by non-structural information.

B. Comparing partitions: measures

Partition similarity is evaluated with several measures that compare shared vertex pairs, cluster overlaps, or information required to infer one partition from another. Each family has distinct interpretations and limitations, motivating measures such as adjusted indices and variation of information.

Measure families: Similarity measures are commonly grouped into pair-counting, cluster-matching, and information-theoretic categories, alongside the ad hoc fraction of correctly classified vertices.The correctly classified fraction distinguishes the natural and algorithmic partitions and marks merged natural groups as incorrectly classified.
Pair counting: Pair-counting measures use vertex pairs that are placed together or apart in both partitions, including Wallace, Rand, Mirkin, and Jaccard indices.The Rand index counts pairs correctly classified as either same-cluster or different-cluster, while the Mirkin metric is equivalent to it.
Pair counting: Adjusted Rand and Jaccard indices subtract the independence-null expectation and normalize the result, giving 1 for identical partitions and 0 for independent partitions.Negative adjusted values are possible.
Cluster matching: Cluster-matching measures maximize overlaps between clusters, but can ignore clusters whose overlaps with the other partition are insufficiently large.Consequently, partitions differing only in subdivisions of unused graph regions can receive the same score.
Information theory: Information-theoretic measures interpret similarity as the information needed to infer one partition from another, but mutual information can equate distinct refinements of a partition.Normalized mutual information equals 1 for identical partitions and has expected value 0 for independent partitions; variation of information is a local metric with maximum value log n.

C. Comparing algorithms · XVI. GENERAL PROPERTIES OF REAL CLUSTERS

Algorithm comparisons show that LFR benchmarks provide a more severe test than the Girvan–Newman benchmark, with Infomap performing best overall while results depend on how benchmarks and algorithms define communities. Across real graphs, communities commonly have skewed size distributions, characteristic conductance profiles, diverse vertex roles, and heterogeneous overlap and membership patterns.

C. Comparing algorithms: The Girvan–Newman benchmark is not representative of real community structure because real graphs have heterogeneous degree and community-size distributions.The LFR benchmark was designed to provide a more severe test of clustering techniques.
C. Comparing algorithms: Infomap appears best across the LFR tests, while the methods of Blondel et al. and Ronhovde and Nussinov also perform well.Tests included directed, weighted, and overlapping-community versions when possible, as well as random graphs without community structure.
C. Comparing algorithms: The modularity landscape surveying method identifies planted overlaps when the fraction of overlapping vertices is small, whereas CPM performs poorly on the same task.CPM often identifies overlapping vertices different from those in the planted partition.
C. Comparing algorithms: Benchmark-based evaluations require both graphs with built-in communities and algorithms that recover them, but their shared community concept can make results definition-dependent.If the benchmark and algorithm use very different notions of community, good performance should not be expected.
XVI. GENERAL PROPERTIES OF REAL CLUSTERS: Most clustering techniques find skewed community-size distributions whose tails are approximately power laws with exponents between 1 and 3.This pattern is reported consistently across multiple clustering studies of real graphs.
XVI. GENERAL PROPERTIES OF REAL CLUSTERS: Conductance-based analyses of large real networks assess community quality across sizes, with the typical network community profile indicating best-defined communities near 100 vertices.The profile rises for larger communities, which are described as less well-defined.
XVI. GENERAL PROPERTIES OF REAL CLUSTERS: Vertices can be classified by within-module degree and participation ratio into seven roles, distinguishing hubs from non-hubs and measuring how neighbors are distributed across clusters.Vertices with z ≥2.5 are hubs; participation values close to 1 indicate uniform distribution across clusters, while P = 0 means all neighbors are internal.
XVI. GENERAL PROPERTIES OF REAL CLUSTERS: In overlapping communities, both overlap and vertex-membership distributions are skewed, indicating no characteristic values for either quantity.Overlap counts shared vertices between cluster pairs, while membership counts the communities containing each vertex.

XVII. APPLICATIONS ON REAL-WORLD NETWORKS … XVIII. OUTLOOK

Graph clustering has been applied to biological, social, citation, auction, legislative, and financial networks, revealing functionally, socially, politically, and economically meaningful communities. Despite these applications, the field still lacks a shared theoretical framework, reliable benchmarks and null models, and methods that adequately handle diverse, evolving, overlapping, and large-scale graphs.

XVII. APPLICATIONS ON REAL-WORLD NETWORKS: Applications remain limited relative to algorithm development, although clustering studies increasingly investigate real systems, especially biological and social networks.The examples are illustrative rather than exhaustive and include other network types.
A. Biological networks: Biological networks exhibit modular organization, and detected communities often group proteins with shared or consistent functions or coincide with known protein complexes.Community clustering coefficients and link density can indicate biological homogeneity, with clustering coefficients remaining informative regardless of community size.
B. Social networks: Social-network communities reveal linguistic, demographic, institutional, racial, and geographic structure across mobile-phone, Facebook, collaboration, and other interaction networks.A Belgian mobile-phone network with 2.6 millions vertices produced six hierarchical levels, with 261 groups at the highest level containing more than 100 vertices.
C. Other networks: Clustering of citation, auction, and legislative networks uncovers relationships among scientific fields, bidders, politicians, parties, geography, and committee memberships.A citation network comprising over 6000 scientific journals was used to derive a map of science.
C. Other networks: In stock-correlation networks, communities correspond to relevant business sectors, while smaller lower-level clusters can represent economically meaningful substructures.Earlier maximum-spanning-tree clusters also matched economic sectors, and later weighted clique-percolation analyses identified sectoral organization.
XVIII. OUTLOOK: Graph clustering lacks a precise theoretical framework defining communities and algorithmic goals, preventing principled decisions about which method performs best.The field has developed chaotically, with new algorithms and improvements but no satisfactory general solution.
XVIII. OUTLOOK: Real-world graphs may have multiple meaningful hierarchical partitions, while quantitative community definitions, null models, and method-selection criteria remain unsettled.Modularity is popular but can be unreliable on large graphs, and no single perfect method is expected to work well for every graph type.
XVIII. OUTLOOK: Future research must incorporate graph-specific information and address directed, weighted, bipartite, multitype, overlapping, evolving, and very large graphs while making results interpretable.Computational complexity has improved by at least one power in graph size, but large-graph results remain unreliable and the meaning of detected communities is still underdeveloped.

Appendix A: Elements of Graph Theory … 3. Model graphs

The appendix defines core graph-theoretic objects, matrix representations, and spectral tools before introducing random, small-world, and scale-free models used to study network structure and test community-detection methods. These models capture properties such as short path lengths, high clustering, and heterogeneous degree distributions while generally lacking community structure.

1. Basic Definitions: A graph consists of vertices and edges, with directed, weighted, multigraph, and hypergraph variants extending the basic definition.Edges connect pairs of vertices; weighted graphs assign real numbers to edges, while multigraphs permit loops or multiple edges and hypergraphs connect more than two vertices.
1. Basic Definitions: Subgraphs, induced subgraphs, cuts, graph size, cliques, paths, connectivity, distance, trees, and bipartite structures provide fundamental graph-theoretic concepts.A cut partitions vertices into S and V −S, with cut size counting crossing edges; a tree with n vertices has n −1 edges.
2. Graph Matrices: The adjacency matrix fully encodes graph topology, while row or column sums give node degrees and weighted graphs use a weight matrix.For undirected graphs, the adjacency matrix is symmetric and has zero diagonal because loops are absent.
2. Graph Matrices: Graph spectra comprise adjacency-matrix eigenvalues, while stochastic matrices describe diffusion and random walks.The right stochastic matrix divides each adjacency-matrix row by the corresponding vertex degree, and the transfer matrix is its transpose.
2. Graph Matrices: The Laplacian and its normalized forms support spectral clustering and graph partitioning through eigenvectors, especially the Fiedler vector.For a connected graph, the Laplacian has one zero eigenvalue and all others positive; the second-smallest eigenvalue’s eigenvector supports bipartitioning.
3. Model graphs: Popular graph models serve as null models for community detection because they lack community structure and enable negative tests of clustering algorithms.The appendix introduces random, small-world, and scale-free models as approximations of real systems.
3. Model graphs: Random graphs connect each vertex pair independently with probability p, yielding expected edge count pn(n−1)/2 and expected mean degree ⟨k⟩= p(n −1).Their diameter grows logarithmically with n, and the expected vertex clustering coefficient is p.
3. Model graphs: Real networks often have heterogeneous degree distributions, with many low-degree vertices and some highly connected vertices whose tails may be fat or approximately power-law.A power law is not necessary: fat tails spanning orders of magnitude in degree can explain complex-network properties.