Community detection

Overview

Given a graph but no group labels, community detection assigns each node to a group. The problem is to find the groups and, for model-based methods, the edge probabilities between them 1903.00114 §1. The stochastic block model (SBM) is the main model-based route: nodes in one group share an edge distribution, and edges are independent given the groups 1903.00114 §2. Non-probabilistic routes such as modularity and label propagation score or grow groups directly from the graph 1903.00114 §5.4.2. A third use applies hierarchical community detection to a graph that an LLM has extracted from text, then summarises each community for question answering [arxiv:2404.16130 §3.1]. Here the graph is not given but built from the corpus.

The review on this page sorts the design space by graph type, degree correction, hard or soft membership, inference method, and how the number of groups K is chosen 1903.00114 §1 1903.00114 §13. It runs no experiments; its tables classify published models 1903.00114 tab. 1.

Variants

Bernoulli SBM (baseline)

Each node has one group. Each pair of groups has one edge probability, and each dyad is an independent Bernoulli draw with that probability [arxiv:1903.00114 §2] 1903.00114 eq. 2. Self-edges are usually excluded [arxiv:1903.00114 §2]. Card: Lee and Wilkinson, A Review of Stochastic Block Models and Extensions for Graph Clustering.

Assortative SBM

A special case in which every between-group probability is one constant δ, smaller than the within-group values. It has K + 1 parameters, so it is a constrained SBM for graphs with a clear community structure [arxiv:1903.00114 §5.4.1]. The review does not give a value for δ 1903.00114 §5.4.1.

Degree-corrected SBM (DC-SBM)

Multiplies each node's expected degree by a per-node parameter φ_p, with φ summing to one inside each group 1903.00114 §3.3 [arxiv:1903.00114 eq. 7]. Without this correction, high-degree nodes pull the groups toward degree levels. On the karate club network the DC-SBM recovers the two known factions and the plain SBM does not 1903.00114 §8.1. The review also reports that a likelihood-ratio test finds no clear evidence for degree correction on that network 1903.00114 §8.1. A regularised DC-SBM sets φ_p = max(h·k_p, 1) with a fixed h in (0, 1) and varies h rather than estimating it 1903.00114 §5.4.1.

Poisson and valued-edge variants

For weighted or multi-edge graphs, the review lists a Poisson SBM, a collapsed Poisson SBM under Gamma priors, a signed directed model with values in {−1, 0, 1}, and a tournament model 1903.00114 §3.2 [arxiv:1903.00114 §3.3]. A zero in a valued graph may mean no edge, a zero-weight edge or missing data, and the review's remedy is a two-component mixture [arxiv:1903.00114 §3.3].

Mixed-membership and overlapping SBM

Soft membership. The mixed-membership SBM (MMSBM) gives each node a membership vector, and inference targets those vectors 1903.00114 §4.1. The overlapping SBM lets a node belong to a non-empty subset of groups. The review reports that overlapping nodes usually belong to two or three groups, make up under 30% of nodes in real networks, and make the model more prone to overfitting 1903.00114 §4.2.

Nested and microcanonical SBM

The microcanonical SBM gives a likelihood that depends on the labels only through edge and node counts, with hard edge-count constraints [arxiv:1903.00114 §3.4]. The nested SBM stacks SBMs on the groups of the level below. In a synthetic network of 64 cliques of 10 nodes, a flat microcanonical fit settled on 32 groups, and the nested model found the hierarchy 1903.00114 §7.2.1.

Modularity and label propagation

Non-probabilistic. Modularity scores a partition by its within-group edges minus the number expected from node degrees 1903.00114 §5.4.2 1903.00114 eq. 20. Label propagation is also covered as a non-probabilistic method 1903.00114 §5.4.2. Modularity has a resolution limit that can hide small groups in large graphs. The review names modularity density and multi-scale agglomeration as remedies 1903.00114 §5.4.3. Its 0.3 significance threshold is a rule of thumb from another paper, not a statistical test 1903.00114 §5.4.2.

Extensions with time or text

Longitudinal SBMs model membership or block parameters over time, with state-space or Markov dynamics 1903.00114 §9. SBMs with text on the edges or nodes combine a block model with a topic model. The review's table of these models distinguishes textual edges from textual nodes 1903.00114 §11 1903.00114 tab. 4. Topic-model background is on the topic modelling page.

Hierarchical Leiden communities with LLM summaries (GraphRAG)

The graph comes from text. An LLM extracts entities and relations from text chunks, and the graph is partitioned with Leiden 2404.16130 §3.1.2 2404.16130 §3.1.4. Leiden is applied again inside each community until the groups cannot be split further. Each level covers every node exactly once 2404.16130 §3.1.4. The paper gives no maximum cluster size, seed or connected-component setting 2404.16130 §4.1.3. Each community gets a pre-written LLM report. Reports are built bottom-up under a token budget, and a large community swaps its largest sub-community for that sub-community's report when the budget is full 2404.16130 §3.1.5. Card: From Local to Global: A Graph RAG Approach to Query-Focused Summarization.

The question step is not a clustering step. Reports are scored and combined map-reduce style 2404.16130 §3.1.6. The paper's win rates against vector RAG for comprehensiveness are 72 to 79 across community levels C0 to C3 on both corpora. For diversity the range is 75 to 81 on Podcast and 62 to 71 on News 2404.16130 fig. 2. The paper reports these as LLM-judged, and a claim-based check agreed with the judge on 78% of non-tied comprehensiveness pairs 2404.16130 §5.2. Root-level C0 uses over 97% fewer context tokens than map-reduce over source text, and C3 uses 26 to 33% fewer [arxiv:2404.16130 §5.1] 2404.16130 tab. 2. Indexing the Podcast corpus took 281 minutes 2404.16130 §4.1.3.

Fitting and choosing K

Inference options named in the review:

• Likelihood maximisation or EM for the frequentist case; the review cites its use for K = 2 1903.00114 §6.
• Gibbs and other MCMC with Beta priors on block probabilities and a Dirichlet prior on memberships 1903.00114 §6 1903.00114 §6.1. Collapsed samplers add moves that change group counts [arxiv:1903.00114 §6.1.1].
• Variational EM with a factorised approximation to the latent variables 1903.00114 §6.2 1903.00114 eq. 23.
• Greedy label switching that moves one node at a time and keeps the best partition seen 1903.00114 §6.3.

Criteria for K, as listed in the review: a modularity-like profile likelihood, BIC (which the review calls intractable for SBMs), ICL, a variational bound used as marginal likelihood, penalised likelihood, held-out perplexity, and an elbow plot 1903.00114 §7.1. A Dirichlet process or an Indian buffet process can generate K inside the model instead 1903.00114 §7.2.

When to use which

Choose by the constraint that binds: graph type first, then whether degree heterogeneity is expected, then the compute budget for inference.

Implementation sketch

The common core of the model-based methods is a greedy label-switching search over one partition score. Variants differ in the score, the priors, and how K is chosen. The score shown is the profile likelihood with the block matrix at its maximum-likelihood value 1903.00114 §7.1 1903.00114 §2. The loop is a sketch of the search described in 1903.00114 §6.3.

# Greedy label switching for SBM-style hard clustering  [§6.3] [§7.1]
# Input:  adjacency Y (n, n) symmetric, initial labels z (n,) in 0..K-1
# Output: labels z (n,) at a local optimum of the profile score

def greedy_label_switch(Y, z, K):
    # Profile score: Bernoulli log-likelihood with C at its MLE  [§7.1] [§2]
    best_z = z.copy()
    best_score = profile_score(Y, z, K)
    while True:
        start_score = best_score
        # Visit nodes one at a time, in random order  [§6.3]
        for p in random_order(n):
            # Move p to the group that scores best (sketch, not the paper's rule)
            z[p] = best_group(Y, z, p, K)
            score = profile_score(Y, z, K)
            # Keep the best labelling seen along the way  [§6.3]
            if score > best_score:
                best_z, best_score = z.copy(), score
        # Restart from the best labelling; stop when it stops rising  [§6.3]
        if best_score <= start_score:
            return best_z
        z = best_z.copy()

Where the variants differ: swap profile_score for a DC-SBM score with φ §3.3, a microcanonical score §3.4, or a Bayesian posterior §6. Modularity replaces the score with the modularity function eq. 20 §5.4.2.

Contradictions

• Degree correction on karate. The DC-SBM recovers the two factions and the plain SBM does not 1903.00114 §8.1. A likelihood-ratio test finds no clear evidence for degree correction on the same network [arxiv:1903.00114 §8.1].
• Number of groups on karate. Under the DC-SBM the ICL selects K = 1; under the plain SBM it selects K = 4 1903.00114 §8.1. Decelle et al. and Newman and Reinert both find K = 2 as the best fit 1903.00114 §8.1.
• Political blogs. A penalised likelihood selects K = 4 at one setting and K = 1 at another, which the review reads as a reason for a heavier-penalty BIC 1903.00114 §8.1.
• Different graphs, different metrics. The review's karate club and blog results use graphs whose edges are given 1903.00114 §8.1. GraphRAG clusters a graph an LLM extracted from text and reports LLM-judged answer comparisons, not recovered labels 2404.16130 §3.3 [arxiv:2404.16130 §5.2]. The two sets of results should not be compared directly.
• Review text and table. The text gives Tallberg K = 2 and Karrer and Newman K = 3; Table 1 gives Tallberg Fixed (3) and Karrer and Newman Fixed (2) 1903.00114 §7 1903.00114 tab. 1. Check the source paper before using either value.

Papers

• A Review of Stochastic Block Models and Extensions for Graph Clustering: the review this page is built on. It maps SBM variants, inference methods, criteria for K, and extensions to time and text.
• From Local to Global: A Graph RAG Approach to Query-Focused Summarization: clusters an LLM-extracted entity graph with hierarchical Leiden and summarises each community for corpus-wide questions.