--- kind: concept slug: community-detection title: Community detection summary: >- Splitting a graph's nodes into groups whose members link more among themselves. Covers stochastic block models (degree correction, mixed membership, nested), modularity, fitting and choosing the number of groups, and Leiden communities used by GraphRAG. Review figures only; GraphRAG results are author-reported. tags: [graph-clustering, network-analysis, stochastic-block-model, knowledge-graph] papers: ["1903.00114", "2404.16130"] related: [spectral-clustering, clustering-evaluation, expectation-maximization, topic-modelling, stochastic-block-model, retrieval-augmented-generation] status: draft updated_at: 2026-10-24 --- ## 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 [arxiv: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 [arxiv:1903.00114 §2]. Non-probabilistic routes such as modularity and label propagation score or grow groups directly from the graph [arxiv: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 [arxiv:1903.00114 §1] [arxiv:1903.00114 §13]. It runs no experiments; its tables classify published models [arxiv: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] [arxiv: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](/papers/1903.00114). ### 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 δ [arxiv: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 [arxiv: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 [arxiv:1903.00114 §8.1]. The review also reports that a likelihood-ratio test finds no clear evidence for degree correction on that network [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:1903.00114 §5.4.2] [arxiv:1903.00114 eq. 20]. Label propagation is also covered as a non-probabilistic method [arxiv: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 [arxiv:1903.00114 §5.4.3]. Its 0.3 significance threshold is a rule of thumb from another paper, not a statistical test [arxiv: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 [arxiv: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 [arxiv:1903.00114 §11] [arxiv:1903.00114 tab. 4]. Topic-model background is on the [topic modelling](/concepts/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 [arxiv:2404.16130 §3.1.2] [arxiv: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 [arxiv:2404.16130 §3.1.4]. The paper gives no maximum cluster size, seed or connected-component setting [arxiv: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 [arxiv:2404.16130 §3.1.5]. Card: [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](/papers/2404.16130). The question step is not a clustering step. Reports are scored and combined map-reduce style [arxiv: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 [arxiv: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 [arxiv: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] [arxiv:2404.16130 tab. 2]. Indexing the Podcast corpus took 281 minutes [arxiv: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 [arxiv:1903.00114 §6]. - **Gibbs and other MCMC** with Beta priors on block probabilities and a Dirichlet prior on memberships [arxiv:1903.00114 §6] [arxiv: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 [arxiv:1903.00114 §6.2] [arxiv:1903.00114 eq. 23]. - **Greedy label switching** that moves one node at a time and keeps the best partition seen [arxiv: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 [arxiv:1903.00114 §7.1]. A Dirichlet process or an Indian buffet process can generate K inside the model instead [arxiv:1903.00114 §7.2]. ## When to use which | Situation | Use | Why | |---|---|---| | Binary, undirected graph, no degree heterogeneity assumed | Bernoulli SBM | Simplest model; the review's base case [arxiv:1903.00114 §2] | | Hubs dominate the degrees | DC-SBM | Separates degree from group in the model [arxiv:1903.00114 §3.3]; on karate it recovered the factions the plain SBM missed [arxiv:1903.00114 §8.1] | | Edges carry weights or counts | Valued or Poisson variant | These models describe edge values rather than presence only [arxiv:1903.00114 §3.2] [arxiv:1903.00114 §3.3] | | A node may belong to several groups | MMSBM or overlapping SBM | Soft membership [arxiv:1903.00114 §4.1] [arxiv:1903.00114 §4.2]; overlapping fits overfit more easily [arxiv:1903.00114 §4.2] | | Groups are nested or the hierarchy matters | Nested microcanonical SBM | Recovers levels a flat fit misses on the synthetic example [arxiv:1903.00114 §7.2.1] | | Want a partition without fitting a generative model | Modularity or label propagation | No likelihood to fit [arxiv:1903.00114 §5.4.2]; watch small groups in large graphs [arxiv:1903.00114 §5.4.3] | | Large graph, soft membership | Variational EM | The review cites O(nK + 2K) against O(n²) for MCMC, as claimed by the cited authors [arxiv:1903.00114 §6.2] | | Edges change over time | Longitudinal SBM | Models dynamics of membership or dyads [arxiv:1903.00114 §9] | | Edges or nodes carry text | Block-topic model | Joint model of structure and text [arxiv:1903.00114 §11] | | Corpus-wide questions over a text collection, slow indexing accepted | Hierarchical Leiden communities with LLM reports (GraphRAG) | Beat vector RAG on comprehensiveness in the authors' LLM-judged runs [arxiv:2404.16130 fig. 2]; indexing took 281 minutes on the Podcast corpus [arxiv:2404.16130 §4.1.3] | | Single-fact lookup in a text collection | Vector RAG, not community summaries | The paper's directness control favours vector RAG [arxiv:2404.16130 fig. 2] | 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 [arxiv:1903.00114 §7.1] [arxiv:1903.00114 §2]. The loop is a sketch of the search described in [arxiv:1903.00114 §6.3]. ```pseudocode # 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 [arxiv: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 [arxiv:1903.00114 §8.1]. Decelle et al. and Newman and Reinert both find K = 2 as the best fit [arxiv: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 [arxiv:1903.00114 §8.1]. - **Different graphs, different metrics.** The review's karate club and blog results use graphs whose edges are given [arxiv:1903.00114 §8.1]. GraphRAG clusters a graph an LLM extracted from text and reports LLM-judged answer comparisons, not recovered labels [arxiv: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) [arxiv:1903.00114 §7] [arxiv:1903.00114 tab. 1]. Check the source paper before using either value. ## Papers - [A Review of Stochastic Block Models and Extensions for Graph Clustering](/papers/1903.00114): 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](/papers/2404.16130): clusters an LLM-extracted entity graph with hierarchical Leiden and summarises each community for corpus-wide questions.