Community Detection — The Science of Finding Hidden Groups in Graphs

Introduction — Why Find "Communities"?

Real-world networks almost always contain clusters of closely connected nodes. In social networks, these are friend groups; on the Web, topically related pages; in protein interaction networks, functional modules; in citation networks, research fields. We call such densely interconnected groups of nodes communities.

Community detection is the problem of partitioning the nodes (vertices) $V$ of a graph $G = (V, E)$ into groups that are "internally dense and externally sparse." It sounds simple, but there is no universal definition of a community, maximizing the most popular quality measure (Modularity) is NP-hard, and in some regimes no algorithm can recover the communities at all. So in practice, rather than looking for a perfect method, you choose one that fits your network and the goal of your analysis.

Historical Context — From Sociograms to Leiden

The field's history spans nearly a century. Here are the main milestones.

Prehistory: Graph Partitioning

The direct ancestor of community detection is the graph partitioning problem from VLSI circuit design. The Kernighan-Lin (KL) algorithm of 1970 is a heuristic that splits a graph's nodes into two equal-sized halves, searching for a split with as few cut edges (edges between the halves) as possible.

Kernighan-Lin Algorithm (1970):
  Input: Graph G = (V, E), initial bisection (A, B) with |A| = |B|
  Repeat:
    1. Mark all nodes as "unlocked"
    2. Perform n/2 swaps, one at a time:
       a. Find the unlocked pair (a ∈ A, b ∈ B) with maximum swap gain g(a,b)
       b. Swap a and b, then "lock" both (they cannot move again this pass)
       c. Record the cumulative gain
    3. Find the prefix k that maximizes total cumulative gain
       → Only keep the first k swaps; undo the rest (backtrack)
    4. Repeat until no improvement

What makes KL work is the look-ahead: it also tries swaps that make the cut worse for now, then backtracks to the best prefix. That lets it escape local optima where a plain greedy method would get stuck.

Graph partitioning and community detection differ in these ways:

These differences are why community detection became a field of its own. The hard part is finding meaningful groups automatically when you know neither how many there are nor how large they should be.

Turning Point: Girvan-Newman (2002)

In 2002, Michelle Girvan and Mark Newman proposed a method that works from the other direction: instead of looking for edges within communities, it removes the bridges between them.

The method relies on edge betweenness centrality: an edge's betweenness is the number of shortest paths between all pairs of nodes that pass through it. Many shortest paths run across the bridge edges between communities, so those edges have high betweenness.

Girvan-Newman Algorithm:
  1. Compute betweenness for all edges
  2. Remove the edge with highest betweenness
  3. Recompute betweenness
  4. Repeat until the graph is fully disconnected
  → Produces a hierarchical dendrogram

With $n$ nodes and $m$ edges, computing the betweenness of every edge takes a breadth-first search (BFS) from every node, $O(mn)$, and this is repeated after each of up to $O(m)$ edge removals, so the complexity is $O(m^2 n)$. That rules it out for large graphs, but it was the first step toward evaluating community structure quantitatively.

Modularity Q — What Is a "Good" Partition?

Girvan-Newman leaves an open question: at which level should you cut the dendrogram? Newman and Girvan answered it in 2004 by defining Modularity Q.

Definition

Where:

• $A_{ij}$: adjacency matrix entry (1 if nodes $i$ and $j$ are joined by an edge, 0 otherwise)
• $k_i$: degree of node $i$, the number of edges attached to it (in a friendship network, the number of friends)
• $m$: total number of edges; each edge adds 1 to the degree of both of its endpoints, so the degrees sum to $2m$
• $c_i$: community of node $i$
• $\delta(c_i, c_j)$: the Kronecker delta, 1 if $c_i = c_j$ and 0 otherwise, so only pairs in the same community contribute to the sum

The bracket compares two quantities. $A_{ij}$ records whether $i$ and $j$ are actually connected, and $\frac{k_i k_j}{2m}$ is the number of edges expected between them if the edges were rewired at random while every node kept its degree; high-degree nodes are likely to be connected even at random. A positive difference means $i$ and $j$ are more strongly connected than random wiring predicts, a negative one less. Modularity Q adds up this difference over all pairs in the same community and normalizes the sum by $\frac{1}{2m}$.

This degree-preserving random rewiring is the configuration model, the null model behind Modularity. Because it keeps the degree sequence, it is a more realistic baseline than a plain random graph (the Erdős-Rényi model). In words, Modularity Q is:

Q measures how much denser the connections inside communities are than random wiring would make them. $Q = 0$ means the communities contain no more edges than random wiring would put there, and $Q > 0$ means denser-than-random connections inside them. Networks with strong community structure typically score $Q \approx 0.3$–$0.7$ (Newman & Girvan, 2004). The theoretical range of $Q$ is $[-0.5, 1]$ (Brandes et al., 2008), but negative values are rare in practice.

Achievements and Limitations of Modularity

Modularity gave community detection a quantitative criterion, and research in the field grew quickly after it. The first practical algorithm for optimizing it was the Clauset-Newman-Moore (CNM) greedy method (2004), which is agglomerative: it starts with every node in its own community and repeatedly merges the pair whose merger raises Q the most. With complexity $O(md \log n)$ (where $d$ is dendrogram depth), CNM bridged the gap between Girvan-Newman (2002) and Louvain (2008).

Two basic problems with Modularity also emerged:

1. NP-Hardness (Brandes et al., 2008): Modularity maximization is NP-hard, so exact solutions are out of reach for realistic graphs
2. Resolution Limit (Fortunato & Barthélemy, 2007): Modularity optimization can miss small communities

Both are covered in "The Fundamental Hardness of Community Detection" below.

Major Algorithms in Detail

1. Louvain Algorithm (2008)

Proposed by Blondel, Guillaume, Lambiotte, and Lefebvre in 2008, the Louvain algorithm became the de facto standard for community detection. It combines greedy local moves with hierarchical aggregation, which lets it handle large graphs.

The Two Phases

For each node $i$, compute the change in Modularity, $\Delta Q$, from moving it to the community $C$ of each neighboring node:

Where:

• $\Sigma_{in}$: sum of the weights of the edges inside community $C$ (edges between two members of $C$), with each edge counted once from each end
• $\Sigma_{tot}$: sum of the weights of all edges incident to nodes in $C$, internal and external alike
• $k_{i,in}$: sum of the weights of the edges from node $i$ to nodes in $C$, which measures how strongly $i$ is tied to $C$'s members
• $k_i$: degree of node $i$

The formula subtracts the contribution before the move from the contribution after it. The first bracket is $C$'s contribution to Modularity once $i$ has joined: the edges between $i$ and $C$ (total weight $k_{i,in}$) become internal, and because internal edges are counted from both ends, $\Sigma_{in}$ grows by $2k_{i,in}$; the expected-edge term grows with $i$'s degree, from $\Sigma_{tot}$ to $\Sigma_{tot} + k_i$. The second bracket is the contribution before the move: $C$ and the isolated node $i$, counted separately. The more strongly $i$ is tied to $C$'s members (the larger $k_{i,in}$), the larger $\Delta Q$ is for moving $i$ into $C$.

Each node moves to the community with the largest positive $\Delta Q$. All nodes are processed in turn, and the sweep repeats until no node moves.

In practice, $\Delta Q$ is computed in two steps: the cost of removing a node from its current community, then the gain of inserting it into the target community. The formula above shows the gain for inserting an isolated node (one in its own singleton community) into community $C$.

Collapse each community from Phase 1 into a single "super-node." Internal edges become self-loops; inter-community edges become super-edges. Apply Phase 1 again on this coarsened graph.

The demo below steps through both phases:

Why It's Fast

One local-moving sweep over all nodes costs roughly in proportion to the number of edges it examines. Each aggregation also cuts the number of communities sharply, so most of the running time goes into the first round of local moving and aggregation. Blondel et al. (2008) write that simulations on large ad hoc modular networks suggest a complexity linear in network size on typical sparse data. That is an observed trend, not a worst-case guarantee. In the same paper, Louvain processed a web graph with 118 million nodes and about one billion edges in 152 minutes.

Louvain's Flaw

Louvain also has a basic flaw. Because Phase 1 moves nodes one at a time and aggregation hides internal structure, communities can end up badly connected or even disconnected: two nodes in the same community may have no path between them that stays inside it. Traag et al. (2019) observed this on real networks.

2. Leiden Algorithm (2019)

Traag, Waltman, and van Eck proposed the Leiden algorithm in 2019 to fix Louvain's flaw. It has three phases:

1. Local Moving — Similar to Louvain, but revisits only nodes whose neighborhood has changed, which it keeps in a queue
2. Refinement — Sub-partitions communities before aggregation so disconnected or badly connected pieces are split rather than carried forward
3. Aggregation — Coarsens using refined communities

Leiden maintains Louvain's speed while guaranteeing internally connected communities after each iteration and, under iterative application, converging toward partitions whose community subsets are locally optimally assigned. Because it yields well-connected communities as well as high Modularity, Leiden is becoming the standard replacement for Louvain.

3. Label Propagation (2007)

The Label Propagation Algorithm (LPA) by Raghavan, Albert, and Kumara is fast and follows a simple rule:

Label Propagation:
  1. Assign each node a unique label
  2. Process nodes in random order:
     - Update to the most frequent label among neighbors
  3. Repeat until no labels change
  → Nodes sharing the same label form a community

With $O(m)$ cost per iteration it is among the fastest methods, but results are non-deterministic. Outcomes depend on node processing order and tie-breaking. With synchronous updates (all nodes updated simultaneously), oscillation can occur, so asynchronous updates (one node at a time) are the common practical choice.

4. Spectral Clustering

This approach uses linear algebra. It starts from the graph Laplacian $L = D - A$, where $A$ is the adjacency matrix (1 for an edge, 0 otherwise) and $D$ is the diagonal degree matrix with $D_{ii} = k_i$, and decomposes $L$ into eigenvectors:

An eigenvector $\mathbf{v}$ is a vector that multiplication by $L$ only scales, and the scaling factor $\lambda$ is its eigenvalue. Sorted in increasing order, the eigenvalues of $L$ always start with $\lambda_1 = 0$. The number of zero eigenvalues equals the number of connected components, and the more eigenvalues lie close to 0, the more readily the graph splits into weakly connected parts.

The eigenvector for the second-smallest eigenvalue $\lambda_2$, the Fiedler vector, gives each node a real value: nodes in the same community tend to get similar values, and nodes in different communities different ones. Splitting the nodes by the sign of these values gives an approximate bisection. To find $k$ communities, embed the nodes in $k$-dimensional space using the eigenvectors of the $k$ smallest eigenvalues and cluster them with k-means.

Strengths: Solid theory. The method is derived as a continuous relaxation of graph-cut minimization, and the Cheeger inequality bounds the quality of the Fiedler-vector bisection.

Weaknesses: You must specify $k$ in advance. Full eigendecomposition is $O(n^3)$, but for sparse graphs iterative methods (Lanczos/ARPACK) compute just the $k$ eigenvectors needed in $O(k \cdot m)$ time.

In practice, the normalized Laplacian $L_{sym} = D^{-1/2}LD^{-1/2}$ or $L_{rw} = D^{-1}L$ is more commonly used than the combinatorial Laplacian (Shi & Malik, 2000). The normalized version produces more stable results on graphs with heterogeneous degree distributions.

Newman (2006) also showed that Modularity can be optimized via the leading eigenvector of the Modularity matrix $B_{ij} = A_{ij} - k_i k_j / 2m$, which is exactly the bracketed term in the definition of Q. The objective functions differ, but some Modularity optimizers and spectral methods use the same linear-algebra tool: partitioning by eigenvectors.

5. Infomap — Information-Theoretic Approach (2008)

Proposed by Rosvall and Bergstrom, Infomap finds the community structure that most efficiently compresses (describes) a random walker's trajectory.

At its heart is the Map Equation:

• $M$: a partition of the nodes into communities (what the method optimizes)
• $c$: number of communities
• $L(M)$: the average code length needed to describe each step of the random walk under partition $M$ (smaller is better)
• $q_{\curvearrowleft}$: the probability that the walker moves between communities
• $H(\mathcal{Q})$: the entropy (uncertainty) of movements between communities
• $p_{\circlearrowleft}^i$: the probability that the walker is at a node in community $i$, plus the probability that it leaves $i$
• $H(\mathcal{P}^i)$: the entropy of movements within community $i$

The first term is the cost of describing movements between communities: the more often the walker switches communities, the more bits it takes to say which community it enters next. The second term is the cost of describing movements within each community; a small community has few nodes, so short codes suffice. Splitting communities too finely inflates the first term, and making them too large inflates the second, so the balance between the two terms sets the size of the communities.

If the partition captures community structure well, a random walker stays inside a community for long stretches. Nodes inside a community can then get short codewords, which shortens the overall description. Telephone area codes work the same way: within your city (community) you dial a short number, and you need an area code only to call another city (community).

Modularity compares a partition with a random model, a statistical view. Infomap frames the problem as information compression. Because it models the flow of a random walk directly, it suits directed graphs and networks with flow structure.

6. Stochastic Block Model (SBM) — Statistical Inference

Statistical inference approaches work from a different premise than Modularity-based methods. The best-known one, the SBM, is a generative model:

1. Each node belongs to community $c_i \in \{1, ..., k\}$
2. Edge probability between communities $r$ and $s$ is $\omega_{rs}$
3. Infer the most likely community assignments and parameters from the observed graph

Likelihood of the observed graph $G$ given assignments $\{c_i\}$ and edge probabilities $\omega$:

Here $\omega_{c_i c_j}$ is the probability of an edge between communities $c_i$ and $c_j$; in typical community structure it is high within a community and low between communities. A node pair contributes $\omega_{c_i c_j}$ if it is joined by an edge ($A_{ij} = 1$) and $1 - \omega_{c_i c_j}$ if it is not ($A_{ij} = 0$), and the product over all pairs is the probability that the model generates the observed graph. SBM inference looks for the $\{c_i\}$ and $\omega$ that maximize this likelihood, the same idea as maximum likelihood estimation (MLE) in machine learning.

The Degree-Corrected SBM (Karrer & Newman, 2011) extends the model to handle uneven node degrees. Real networks often have power-law degree distributions, which the original SBM cannot model well.

SBM Inference:
  Parameters: community assignments {c_i}, edge probability matrix ω
  Objective: maximize posterior P({c_i}, ω | G)
  Methods: EM, variational inference, MCMC, Belief Propagation

The most important feature of SBM is model selection. The number of communities $k$ is also inferred, with criteria such as Minimum Description Length (MDL) guarding against overfitting. This lets SBM answer whether community structure exists at all.

Peixoto (2014) pointed out that a resolution limit affects not only Modularity optimization but also model selection with the ordinary SBM. His nested SBM recursively block-structures the SBM itself to describe the whole hierarchy of the network, which gives nonparametric model selection and avoids that limit as well.

The Fundamental Hardness of Community Detection

Each algorithm above optimizes a different objective, but some difficulties remain whichever one you use.

1. Ill-Definedness

The most basic difficulty is that no universal definition of "community" exists.

Most people share the intuition that communities are "internally dense and externally sparse," but there are countless ways to formalize it:

• Cut minimization: the graph partitioning tradition
• Internal density maximization: the Modularity perspective
• Random walk residence time: the Infomap perspective
• Probabilistic model fit: the SBM perspective
• Clique-like structure: subgraph density focus

These can yield different "correct answers" for the same graph, and which one is right depends on what the analysis treats as a community.

2. NP-Hardness

Modularity maximization is NP-hard (Brandes et al., 2008), so, assuming P ≠ NP, no efficient algorithm finds the exact optimum. The number of ways to partition $n$ nodes is the Bell number $B_n$, which grows superexponentially ($B_{30}$ is about $8.5 \times 10^{23}$), so exhaustive search is impractical even for graphs with a few dozen nodes. Every practical algorithm is an approximation and can get stuck in local optima.

In one sense, though, NP-hardness is a surface problem. The choice of what to optimize is itself arbitrary, so the harder question is what to optimize in the first place.

3. Resolution Limit

The resolution limit, found by Fortunato and Barthélemy (2007), is a fundamental critique of Modularity-based methods. Let $m$ be the total number of edges. The expected number of edges $\frac{k_i k_j}{2m}$ shrinks as $m$ grows, so between two small communities in a large graph it can fall below one; a single edge between them is then enough to make merging them increase Q.

Whether a merge happens depends on the surrounding graph as well as on community size. Fortunato and Barthélemy showed this with a ring of cliques: cliques (subgraphs in which every pair of nodes is joined by an edge) arranged in a ring, each joined to its neighbors by a single edge. There, cliques whose internal edge count is below the $\sqrt{m}$ scale can be merged in the Modularity-optimal solution even though each clique is an unambiguous community. The boundary is commonly summarized as fewer than about $\sqrt{m/2}$ internal edges, or a total internal degree below about $\sqrt{2m}$.

In a graph with about one million edges, for example, $\sqrt{2 \times 10^6} \approx 1414$, so communities whose total internal degree is below that may be indistinguishable to Modularity optimization, depending on how they connect to the rest of the graph.

Many real networks have multi-scale structure, which makes this limit a serious problem. A social network, for example, contains groups ranging from a handful of close friends to communities of thousands.

Countermeasures include:

• Resolution parameter $\gamma$ (Reichardt & Bornholdt, 2006): $Q_\gamma = \frac{1}{2m} \sum_{ij} \left[ A_{ij} - \gamma \frac{k_i k_j}{2m} \right] \delta(c_i, c_j)$ $\gamma$ works like the magnification of a lens. With $\gamma > 1$ the null-model penalty is stronger and smaller communities become easier to detect; with $\gamma < 1$ larger communities are detected
• Multi-scale analysis: detect repeatedly at different $\gamma$ to capture communities at several scales
• Moving to the nested SBM: it drops the null-model comparison and uses hierarchical model selection that can detect small communities too (Peixoto, 2014)

4. Detectability Threshold — Fundamentally Undetectable Regimes

The detectability threshold was derived by Decelle et al. (2011) with the cavity method, a technique from statistical physics that is not mathematically rigorous, and was later proven. It matters because it limits the problem itself, not the performance of any particular algorithm.

Take an SBM with two equal-sized communities and edge probability parameters $c_{in}/n$ within communities and $c_{out}/n$ between communities (each node has $\approx c_{in}/2$ within-community neighbors and $\approx c_{out}/2$ between-community neighbors, giving average degree $(c_{in} + c_{out})/2$). When the following holds and the number of nodes is large, no algorithm can detect the communities better than a random assignment:

The left side, the squared difference between the within- and between-community parameters, measures how different inside and outside connections are: the signal. The right side is proportional to the average degree and stands for random fluctuation: the noise. Scaling $c_{in}$ and $c_{out}$ down by the same factor shrinks the left side quadratically but the right side only linearly, so the sparser the graph, the larger the noise relative to the signal. The inequality is the condition under which the signal drowns in the noise: when connections inside communities differ little from those between them, or when the graph is too sparse, random fluctuations erase the trace of the communities.

This result is closely tied to spin glass theory in statistical physics and shows that community detectability has a phase transition. Below the threshold, detection is impossible in principle, which Mossel, Neeman & Sly (2015) proved. Above it, detection suddenly becomes possible: Massoulié (2014) and Mossel, Neeman & Sly (2018) independently proved that efficient (polynomial-time) algorithms succeed there. The impossibility below the threshold is an information-theoretic limit, not computational hardness.

5. Absence of Ground Truth

Unlike classification in machine learning, community detection generally lacks ground-truth labels.

• The LFR benchmark (Lancichinetti-Fortunato-Radicchi, 2008) generates synthetic graphs with power-law distributions for both degree and community size. Because it partly mimics real-network statistics, it is widely used as the standard benchmark, but the ground truth of such benchmarks is artificial and does not reflect the complexity of real networks
• Metadata (paper fields, user attributes) is sometimes used as ground truth, but metadata-based groups don't necessarily align with network-derived communities (Peel, Larremore & Clauset, 2017)
• Evaluation metrics such as NMI (normalized mutual information) and ARI (adjusted Rand index) assume ground truth exists

SBM-based approaches can evaluate results through model fit without ground truth, but nothing guarantees that the model's assumptions are correct.

6. Overlapping Communities

In real networks, nodes often belong to several communities at once. A university researcher might belong to both the "machine learning" and "computational theory" communities.

Algorithms that allow overlap exist (COPRA, BigCLAM, Mixed-Membership SBM, etc.), but formulation and evaluation get harder still. How to measure overlap, and what counts as the correct overlapping structure, are open questions.

Beyond Modularity — Why So Many Approaches Exist

Modularity is the most widely used metric, but methods differ in the objective functions they use because they conceive of a "community" differently:

In the conductance formula, $\text{cut}(S, \bar{S})$ is the number of edges crossing the boundary between community $S$ and the rest of the graph $\bar{S}$, and $\text{vol}(S)$ is the sum of the degrees of the nodes in $S$ (the community's "volume"). Taking the minimum treats $S$ and $\bar{S}$ symmetrically, so a set that covers most of the graph cannot score low merely because its volume is large. The lower the conductance, the sharper the boundary and the less the community "leaks," so lower values mark better communities.

Which objective is appropriate depends on the network's properties and the analysis goal.

Modern Developments and Open Problems

Consensus Clustering

The results of Label Propagation and Louvain depend on the order in which nodes are processed. To address this non-determinism, consensus clustering (Lancichinetti & Fortunato, 2012) was proposed. The algorithm is run several times, and a consensus matrix is built from how often nodes $i$ and $j$ land in the same community. Running community detection again on this matrix gives stable results.

Higher-Order / Motif-Based Detection

Traditional approaches consider only pairwise edges, but community detection based on motifs, specific subgraph patterns, has also developed (Benson, Gleich & Leskovec, 2016). For example, communities defined by triangle density reveal structure that edge density alone cannot capture.

GNN-Based Approaches

Graph Neural Networks (GNNs) are also being applied to community detection (Tsitsulin et al., 2023). These approaches learn node features and optimize community assignments end to end. Some make unsupervised objectives such as Modularity differentiable and optimize them by gradient descent; others use contrastive learning. Interpretability and generalization remain open issues.

Dynamic and Multiplex Networks

In time-varying networks, detection has to track communities being born, growing, splitting, and dying, which makes it harder still. Mucha et al. (2010) gave a unified formulation for time-dependent, multiscale, multiplex networks. Temporal modularity and matching communities across snapshots are active research topics.

Large-Scale Distributed Processing

Billion-node networks such as social graphs and Web graphs cannot be processed on a single machine. Work on distributed Louvain/Leiden built on MapReduce and Pregel is ongoing.

Practical Algorithm Selection Guide

Based on the comparisons above, these are the methods I recommend for each situation:

Summary

"Find hidden structure in a graph" sounds like a simple problem, but community detection carries these fundamental difficulties:

1. Definitional ambiguity: No universal definition of "community" exists
2. Computational hardness: Modularity maximization is NP-hard
3. Resolution limit: Scale-dependent detection blind spots
4. Detectability threshold: Information-theoretically undetectable regimes
5. Absence of ground truth: Solving a problem without knowing the answer
6. Overlapping structure: Reality resists hard partitions

Nearly a century of research has shown that perfect community detection is impossible in principle, and the field has settled on a practical stance: choose the right tool for the purpose. Louvain/Leiden suit fast partitioning of large graphs, SBM suits inferring the number of communities and whether there is any structure at all, and Infomap suits networks with flow.

Next in the series: Part 2 explores higher-order, dynamic, and multiplex community detection, followed by Part 3 on streaming community detection.

References

• Kernighan, B. W., & Lin, S. (1970). An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49(2), 291–307.
• Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE TPAMI, 22(8), 888–905.
• Girvan, M., & Newman, M. E. J. (2002). Community structure in social and biological networks. PNAS, 99(12), 7821-7826.
• Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113.
• Clauset, A., Newman, M. E. J., & Moore, C. (2004). Finding community structure in very large networks. Physical Review E, 70(6), 066111.
• Newman, M. E. J. (2006). Modularity and community structure in networks. PNAS, 103(23), 8577-8582.
• Reichardt, J., & Bornholdt, S. (2006). Statistical mechanics of community detection. Physical Review E, 74(1), 016110.
• Brandes, U., et al. (2008). On modularity clustering. IEEE TKDE, 20(2), 172-188.
• Fortunato, S., & Barthélemy, M. (2007). Resolution limit in community detection. PNAS, 104(1), 36-41.
• Raghavan, U. N., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3), 036106.
• Blondel, V. D., et al. (2008). Fast unfolding of communities in large networks. JSTAT, P10008.
• Rosvall, M., & Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. PNAS, 105(4), 1118-1123.
• Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008). Benchmark graphs for testing community detection algorithms. Physical Review E, 78(4), 046110.
• Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3-5), 75-174.
• Mucha, P. J., et al. (2010). Community structure in time-dependent, multiscale, multiplex networks. Science, 328(5980), 876–878.
• Karrer, B., & Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Physical Review E, 83(1), 016107.
• Decelle, A., et al. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6), 066106.
• Lancichinetti, A., & Fortunato, S. (2012). Consensus clustering in complex networks. Scientific Reports, 2, 336.
• Massoulié, L. (2014). Community detection thresholds and the weak Ramanujan property. STOC 2014, 694–703.
• Peixoto, T. P. (2014). Hierarchical block structures and high-resolution model selection in large networks. Physical Review X, 4(1), 011047.
• Mossel, E., Neeman, J., & Sly, A. (2015). Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162(3–4), 431–461.
• Benson, A. R., Gleich, D. F., & Leskovec, J. (2016). Higher-order organization of complex networks. Science, 353(6295), 163–166.
• Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Physics Reports, 659, 1-44.
• Peel, L., Larremore, D. B., & Clauset, A. (2017). The ground truth about metadata and community detection in networks. Science Advances, 3(5), e1602548.
• Mossel, E., Neeman, J., & Sly, A. (2018). A proof of the block model threshold conjecture. Combinatorica, 38(3), 665–708.
• Traag, V. A., Waltman, L., & van Eck, N. J. (2019). From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports, 9, 5233.
• Tsitsulin, A., et al. (2023). Graph clustering with graph neural networks. JMLR, 24(127), 1–21.