Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

Improved Community Detection using Stochastic Block Models

T0 review · 2 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Stochastic block models often return internally disconnected communities, and a simple post-processing step, Well-Connected Clusters (WCC), that repeatedly removes small edge cuts typically improves clustering accuracy and scales to…

desk verdict Solid empirical study with a useful post-processing tool, but the headline accuracy claim needs a benchmark that does not share WCC's connectivity assumption. read the letter →

arxiv 2502.00686 v3 pith:U3LM4XDT submitted 2025-02-02 cs.SI

Minhyuk Park , Daniel Wang Feng , Siya Digra , The-Anh Vu-Le , Lahari Anne , George Chacko , Tandy Warnow This is my paper · ORCID
classification cs.SI
keywords communitydetectionstochasticblockmodelswell-connectednessedgeconnectivitygraphclusteringpost-processingLeidenalgorithmsyntheticbenchmarknetworks
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Community detection with stochastic block models (SBMs) is widely used, but the clusters it returns are not guaranteed to be internally connected. This paper establishes that SBM clusterings of real-world networks frequently contain internally disconnected and poorly connected communities, with the tendency worsening as networks grow, and derives why the model's own objective prefers such clusters. To repair this, the authors introduce Well-Connected Clusters (WCC), a post-processing step that repeatedly removes small edge cuts from any cluster that fails a user-set well-connectedness threshold until every cluster passes. On synthetic benchmarks modeled after real networks, applying WCC to SBM clusterings typically improves clustering accuracy, and the step adds only about an hour or two on networks with millions of nodes.

What carries the argument

The central object is the Well-Connected Clusters (WCC) post-processor, defined against a threshold for edge-connectivity: a cluster of $n$ nodes is well-connected when its minimum edge cut exceeds $\log_{10}(n)$; the paper uses the VieCut algorithm to find those cuts. WCC takes an SBM clustering, and for any cluster failing the threshold, deletes the minimum cut so the cluster splits in two, iterating until every cluster passes. The second load-bearing mechanism is the description-length decomposition of the degree-corrected SBM, $DL(A,b) = -\log p(A|b,e,k) - \log p(k|b,e) - \log p(b) - \log p(e)$: the $-\log p(e)$ term, which grows with the number of blocks, is what makes the model prefer disconnected clusters, and it is this objective that WCC avoids by operating only on the output clustering.

What would settle it

Generate synthetic networks whose ground-truth communities are deliberately allowed to be poorly connected or internally disconnected, or use real networks with curated ground truth that includes weakly connected communities, then run SBM and SBM+WCC: if the accuracy gains of WCC vanish or reverse on those benchmarks, the claimed improvement is an artifact of testing only against well-connected ground truth.

Watch

Extended reading notes

Core claim

The central claim is that stochastic block model community detection has a systematic tendency to return internally disconnected clusters, and that this failure is baked into the model's own objective. Under the degree-corrected SBM, the description-length score penalizes a large number of blocks $B$ through the $-\log p(e)$ term, which grows as $O(\log B)$; splitting a disconnected cluster into its connected pieces raises $B$ and inflates the description length, so the optimizer leaves clusters disconnected even though the model-likelihood terms prefer connected ones. The proposed remedy, WCC, bypasses the objective entirely: given a clustering and a threshold such as $\log_{10}(n)$ for a cluster of $n$ nodes, it removes the smallest edge cut of any failing cluster, never re-clustering, until every cluster is well-connected. On synthetic LFR and RECCS networks with known ground truth, SBM+WCC is typically at least as accurate as untreated SBM and competitive with Leiden-CPM(0.001)+CM, while on the largest real networks WCC finishes in under two hours on top of an SBM run that takes tens of hours.

Load-bearing premise

The accuracy results assume that synthetic networks whose ground-truth communities come from Leiden clusterings are a fair test of a method whose entire mechanism is to enforce exactly the kind of well-connectedness Leiden guarantees.

Editorial extensions

If this is right

  • SBM practitioners can safely add WCC as a fast post-step that guarantees every reported community meets the user's connectivity threshold, at a runtime cost of under two hours even for networks with roughly 14 million nodes.
  • On non-bipartite networks, SBM+WCC is generally competitive with, and on several model conditions more accurate than, Leiden-CPM(0.001)+CM across NMI, ARI, AGRI, and RMI on the tested LFR and RECCS benchmarks.
  • WCC costs node coverage: the fraction of nodes in non-singleton clusters falls from 100% to 48% on medium and 38% on large non-bipartite networks on average, a larger drop than the Connected Components baseline.
  • The description-length analysis implies that any SBM variant whose objective penalizes the number of blocks will tend to prefer internally disconnected clusters; removing the $-\log p(e)$ term flips the preference in 59 of 71 degree-corrected SBM networks.
  • WCC is not always free: on one RECCS network it exceeded 256 GB of RAM and on one LFR network it exceeded the 72-hour limit, while CC and CM completed in both cases.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the disconnection tendency is caused by the block-count penalty, then constraining the SBM search to connected clusterings (the paper's own suggested future direction) could capture most of WCC's benefit without a post-processing stage.
  • Because the benchmark ground truth comes from Leiden, which guarantees well-connected communities, a test on synthetic networks with deliberately weak or disconnected ground-truth communities would reveal whether WCC's accuracy gains persist when the target communities are themselves poorly connected.
  • The user-set threshold suggests a resolution-style sweep: raising it above $\log_{10}(n)$ would return smaller, tighter clusters and lowering it would return larger ones, giving practitioners a knob between coarse and fine partitions.
  • The results are established only for non-bipartite networks; since the paper found nearly all SBM clusters on bipartite networks are disconnected, WCC's behavior there is untested.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies the connectivity of communities found by Stochastic Block Models (SBMs) on 120 real-world networks, showing that SBMs frequently produce internally disconnected or poorly connected clusters, especially on bipartite and large networks. To address this, the authors propose Well-Connected Clusters (WCC), a post-processing technique that recursively removes small edge cuts until each cluster meets a user-specified well-connectedness threshold (default log10(n)), and compare WCC with two other post-processors (Connected Components and the Connectivity Modifier). Using synthetic LFR and RECCS networks whose ground truth is derived from Leiden clusterings of real networks, the authors report that WCC generally improves SBM clustering accuracy across NMI, ARI, AGRI, and RMI, and is computationally fast on networks with millions of nodes. The paper also offers a description-length analysis explaining why the degree-corrected SBM favors disconnected clusters.

Significance. If the accuracy claim holds, WCC is a simple, fast, and open-source post-processing step that SBM practitioners could apply to obtain well-connected clusters with improved accuracy on non-bipartite networks. The paper's empirical characterization of SBM cluster connectivity across 120 real networks is a useful contribution, and the runtime experiments (Experiment 4) demonstrate WCC's scalability to a network with about 14 million nodes. The description-length analysis (Fig 8, Table 1, Eq 2) provides a plausible mechanistic explanation for why SBMs prefer internally disconnected clusters. However, the central accuracy claim rests on synthetic benchmarks whose ground truth is generated by methods that enforce well-connectedness, which is exactly the property WCC imposes; this creates a systematic bias that must be addressed before the claim can be considered established.

major comments (2)
  1. [Materials and methods: Synthetic networks; Experiment 3a (Fig 3)] The accuracy evaluation in Experiment 3 is based entirely on synthetic networks whose ground truth is derived from Leiden clusterings of real-world networks: LFR parameters come from networks clustered with Leiden optimizing modularity or CPM, RECCS uses Leiden-CPM(0.01), and the two LFR networks with a large proportion of disconnected ground-truth clusters were excluded from the study. Because Leiden guarantees well-connected communities, the benchmark ground truth is well-connected by construction, which is exactly the property WCC enforces. Consequently, any internally disconnected SBM cluster is automatically an error with respect to this ground truth, and WCC is the treatment designed to repair that error; the comparison SBM vs. SBM+WCC is therefore systematically biased in WCC's favor. To establish that WCC 'typically improves' accuracy, please add benchmarks whose ground truth is not constrained to be well-connected (e.g., LFR or RECCS networks generated from random partitions, from SBM models with disconnected blocks, or from the excluded LFR networks with disconnected ground truth), and report accuracy separately for well-connected versus disconnected ground-truth communities.
  2. [Experiment 2 (Table A; Fig A in S1 Appendix)] The real-world results in Table A show that WCC reduces node coverage from 100% to 48% on medium and 38% on large non-bipartite networks, with median non-singleton cluster sizes dropping to 3. This is a very different structure from the benchmark ground truth, whose communities are the much larger well-connected clusters produced by Leiden. If WCC fragments real SBM clusters to this degree, it is unclear whether accuracy gains on the synthetic benchmarks, whose ground truth consists of large well-connected communities, will transfer to real-world applications. Please discuss this discrepancy explicitly and, if possible, validate on a real-world network with known community labels, or at least report the distribution of accuracy contributions as a function of cluster size on the synthetic benchmarks.
minor comments (5)
  1. [Abstract] The abstract contains several typos: 'sh own' should be 'shown', 'an d' should be 'and', 'evalu ate' should be 'evaluate', 'pro pose' should be 'propose', and 'net works' should be 'networks'. Please proofread the entire manuscript.
  2. [Table A caption (S1 Appendix)] The caption reads 'lage-sized' instead of 'large-sized', and the same typo appears in other supplementary table captions. Please correct these.
  3. [Figure 8 caption] The caption states 'We show the contribution of − log p(e) term on the description lengths of CC-treated SBM clusterings,' but the box plot shows differences for all four description-length components. Please rephrase to describe the full set of components shown.
  4. [Experiment 3a (Fig 3)] The heatmap in Fig 3 reports normalized differences, but the underlying numeric accuracy scores (NMI, ARI, AGRI, RMI) are not provided as a table. A supplementary table with these values for each method and each synthetic network would improve reproducibility and allow readers to verify claims such as 'WCC always was neutral or beneficial for NMI and ARI.'
  5. [Discussion (Eq 2)] The description-length analysis is restricted to the degree-corrected SBM and the CC treatment, while the recommended method is WCC. The explanation would be more compelling if the same component decomposition were reported for WCC and for the non-degree-corrected and planted-partition SBM variants, since these models are also used in the selected SBM clustering.

Circularity Check

1 steps flagged · score 4.0 of 10

Experiment 3's accuracy gain is partly built into a benchmark whose Leiden-derived ground truth shares WCC's connectivity objective; real-world and runtime results remain independent.

  1. other [Materials and methods: Synthetic networks (LFR and RECCS); Materials and methods: Post-processing treatments (WCC); Discussion]
    "Each of these networks was produced using the LFR software, using parameters obtained from a clustered real-world network. ... the networks were clustered using Leiden optimizing either modularity or the Constant Potts Model (CPM) ... To produce RECCS networks, we provided parameters to the RECCS software for the Leiden-CPM(0.01) clustering ... WCC checks each cluster to see if it is well-connected. If so, it puts the cluster in the output, and otherwise it removes the small edge cut from the cluster, thus producing two smaller clusters."

    The accuracy benchmark in Experiment 3 is generated from Leiden clusterings, and the paper states that 'Leiden never produces disconnected ground truth clusters, unlike SBM, but can produce poorly connected clusters.' WCC is defined as iteratively removing small edge cuts until each cluster is well-connected. Thus the ground truth and the WCC output are both constrained to the same connectivity property by construction: any internally disconnected SBM cluster is an error relative to this ground truth, and WCC is exactly the treatment that repairs that error. The measured ARI/NMI/RMI/AGRI gains are therefore partially artifacts of the benchmark construction, not independent tests.

full rationale

The main accuracy claim — that applying WCC to SBM clusterings can improve accuracy on synthetic networks — is evaluated exclusively on LFR and RECCS benchmarks whose ground-truth partitions are derived from Leiden clusterings of real-world networks (Leiden-mod or Leiden-CPM, and Leiden-CPM(0.01) for RECCS). Leiden's defining property is that it produces connected communities, and the paper explicitly notes that 'Leiden never produces disconnected ground truth clusters, unlike SBM, but can produce poorly connected clusters.' WCC is defined as repeatedly removing small edge cuts until every cluster is well-connected. The benchmark and the treatment therefore share the same connectivity constraint by construction, so the Experiment 3 comparison systematically rewards WCC for repairing exactly the disconnected-cluster error that the benchmark defines as wrong. This is a genuine, if partial, circularity: a control with ground truth not constrained to be connected or well-connected is absent. The paper's own real-world measurements (Table A) show WCC drops node coverage from 100% to 38% on large non-bipartite networks with median cluster sizes of 3, indicating that the benchmark's ground truth is not representative of WCC's real-world output. However, the paper is not fully circular: no parameter is fitted to the accuracy metrics, the connectivity of SBM clusters on real networks is measured directly, the description-length analysis is an independent derivation, and the runtime claims (Experiment 4) are self-contained. The self-citations to the prior LFR and RECCS benchmark papers are secondary to this constructional bias. Score 4 reflects partial benchmark circularity with substantial independent content.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central empirical claims rest on the threshold log10(n), on Leiden-derived synthetic ground truths, and on tool correctness. The threshold is inherited from prior work; the benchmark design is the main circularity concern because ground truth comes from Leiden, which already enforces well-connectedness.

free parameters (2)
  • well-connectedness threshold t = log10(n) = log10(n) (default)
    User-specified threshold from prior work [6]; determines when WCC stops splitting and what counts as poorly connected. Affects all accuracy and connectivity results.
  • Leiden resolution for synthetic benchmark ground truth = 0.01 for RECCS; 0.0001, 0.001, 0.01, 0.1, 0.5 for LFR
    These resolution values and the choice of Leiden modularity/CPM determine ground-truth communities used to score SBM+WCC; changing them changes measured accuracy.
assumptions (3)
  • domain assumption Well-connectedness is appropriately measured by minimum edge cut exceeding log10(n), where n is the cluster size.
    Adopted from Park et al. [6]; this threshold controls WCC behavior and defines the paper's evaluation categories. The paper treats it as a default, user-specified criterion.
  • domain assumption Synthetic networks generated by LFR and RECCS from Leiden-based clusterings of real networks are faithful proxies for real-world community structure.
    Materials and methods: synthetic networks use parameters from real-world networks clustered with Leiden (modularity or CPM). Accuracy on these benchmarks is the main evidence for WCC's benefit.
  • domain assumption VieCut computes correct minimum cuts and graph-tool's SBM inference is a valid oracle for community structure.
    WCC/CM rely on VieCut for minimum cuts; SBM clusterings rely on graph-tool's description-length minimization. No independent verification of these tools' outputs is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Community Detection using Stochastic Block Models." pith.science (2026). https://pith.science/paper/U3LM4XDT

@misc{pith2026250200686,
  author       = {Pith},
  title        = {Pith review of: Improved Community Detection using Stochastic Block Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U3LM4XDT}},
  note         = {Machine review of arXiv:2502.00686}
}
read the original abstract

Identifying edge-dense communities that are also well-connected is an important aspect of understanding community structure. Prior work has shown that community detection methods can produce poorly connected communities, and some can even produce internally disconnected communities. In this study we evaluate the connectivity of communities obtained using Stochastic Block Models. We find that SBMs produce internally disconnected communities from real-world networks. We present a simple technique, Well-Connected Clusters (WCC), which repeatedly removes small edge cuts until the communities meet a user-specified threshold for well-connectivity. Our study using a large collection of synthetic networks based on clustered real-world networks shows that using WCC as a post-processing tool with SBM community detection typically improves clustering accuracy. WCC is fast enough to use on networks with millions of nodes and is freely available in open source form.

Figures

Figures reproduced from arXiv: 2502.00686 by the authors.

Figure 1
Figure 1. Experiment 1: Cluster connectivity of SBM on real-wor [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Experiment 1: Node coverage of SBM+CC clusterings [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Experiment 3a: Impact of treatment on NMI/ARI/AGRI/R [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Experiment 3a: Impact of WCC treatment on ARI scores of [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: Experiment 3b: ARI accuracies of SBM+WCC against vari [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: Experiment 3b: AGRI accuracies of SBM+WCC against var [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]
Figure 7
Figure 7. Figure 7: Experiment 4: Runtime of SBM and SBM + treatments on lar [PITH_FULL_IMAGE:figures/full_fig_p014_7.png]
Figure 8
Figure 8. Figure 8: SBM(DC)+CC to SBM(DC) difference for description len [PITH_FULL_IMAGE:figures/full_fig_p016_8.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Hypermodularity and community detection in hypergraphs

    physics.soc-ph 2024-12 conditional novelty 6.0 of 10

    A spectral algorithm for hypergraph community detection based on higher-order SVD of the hypermodularity tensor, with the caveat that the top singular vector is a heuristic, not a proven optimizer.

Reference graph

Works this paper leans on

25 extracted references · 23 canonical work pages · cited by 1 Pith paper

  1. [1]

    On clusterings: Good, bad and spe ctral

    Kannan R, Vempala S, Vetta A. On clusterings: Good, bad and spe ctral. Journal of the ACM (JACM). 2004;51(3):497–515

    work page 2004

  2. [2]

    From Louvain to Leiden: guaran teeing well-connected communities

    Traag V A, Waltman L, Van Eck NJ. From Louvain to Leiden: guaran teeing well-connected communities. Scientific Reports. 2019;9(1):1–12

    work page 2019

  3. [3]

    Fast unfolding of communities in large networks

    Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. Journal of statistical mechanics: t heory and experiment. 2008;2008(10):P10008

    work page 2008

  4. [4]

    Improv ed Community Detection using Stochastic Block Models; 2024

    Park M, Feng DW, Digra S, Vu-Le TA, Chacko G, Warnow T. Improv ed Community Detection using Stochastic Block Models; 2024. arXiv pre print arXiv:2408.10464

    arXiv 2024

  5. [5]

    The graph-tool python library

    Peixoto TP. The graph-tool python library. figshare. 2014;doi:10.6084/m9.figshare.1164194

    doi:10.6084/m9.figshare.1164194 2014

  6. [6]

    Well-connectedness and community detection

    Park M, Tabatabaee Y, Ramavarapu V, Liu B, Pailodi VK, Ramacha ndran R, et al. Well-connectedness and community detection. PLOS Complex S ystems. 2024;1(3):e0000009

    work page 2024

  7. [7]

    Leiden Algorithm: leidenalg; 2019

    Traag V. Leiden Algorithm: leidenalg; 2019. https://github.com/vtraag/leidenalg

    work page 2019

  8. [8]

    The map equation

    Rosvall M, Axelsson D, Bergstrom CT. The map equation. The Eur opean Physical Journal Special Topics. 2009;178(1):13–23

    work page 2009

Show all 25 references
  1. [9]

    Center-per iphery structure in research communities

    Wedell E, Park M, Korobskiy D, Warnow T, Chacko G. Center-per iphery structure in research communities. Quantitative Science Studies. 2022;3(1):289–314

    2022

  2. [10]

    Graph clustering via a discrete uncoupling process

    Dongen SV. Graph clustering via a discrete uncoupling process. SIAM Journal on Matrix Analysis and Applications. 2008;30(1):121–141

    2008

  3. [11]

    Emulating real networks using LFR graphs; 202 3

    Tabatabaee Y. Emulating real networks using LFR graphs; 202 3. https://github.com/ytabatabaee/emulate-real-nets

  4. [12]

    Comparing partitions

    Hubert L, Arabie P. Comparing partitions. Journal of classifica tion. 1985;2:193–218

    1985

  5. [13]

    Synthetic Netw orks That Preserve Edge Connectivity

    Anne L, Vu-Le TA, Park M, Warnow T, Chacko G. Synthetic Netw orks That Preserve Edge Connectivity. arXiv preprint arXiv:240813647. 202 4;. February 17, 2025 18/19

    2025

  6. [14]

    The Netzschleuder network catalogue and reposit ory; 2020

    Peixoto TP. The Netzschleuder network catalogue and reposit ory; 2020. https://networks.skewed.de

    2020

  7. [15]

    Benchmark graphs for testing community detection algorithms

    Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E. 2008;78(4):046 110

    2008

  8. [16]

    Synthetic Networks For B enchmarking

    Anne L, Park M, Warnow T, Chacko G. Synthetic Networks For B enchmarking

  9. [17]

    Stochastic blockmodels and community st ructure in networks

    Karrer B, Newman ME. Stochastic blockmodels and community st ructure in networks. Physical Review E—Statistical, Nonlinear, and Soft Matt er Physics. 2011;83(1):016107

    2011

  10. [18]

    Stochastic blockmodels: Fir st steps

    Holland PW, Laskey KB, Leinhardt S. Stochastic blockmodels: Fir st steps. Social Networks. 1983;5(2):109–137

    1983

  11. [19]

    Statistical inference of assortative com munity structures

    Zhang L, Peixoto TP. Statistical inference of assortative com munity structures. Physical Review Research. 2020;2(4):043271

    2020

  12. [20]

    Practical Minimum Cut Alg orithms

    Henzinger M, Noe A, Schulz C, Strash D. Practical Minimum Cut Alg orithms. ACM Journal of Experimental Algorithmics. 2018;23:1–22

    2018

  13. [21]

    Elements of Information Theory

    Thomas M, Joy AT. Elements of Information Theory. Wiley-Inte rscience; 2006

    2006

  14. [22]

    Comparing graph clusterings: Set partit ion measures vs

    Poulin V, Th´ eberge F. Comparing graph clusterings: Set partit ion measures vs. graph-aware measures. IEEE Transactions on Pattern Analysis a nd Machine Intelligence. 2020;43(6):2127–2132

    2020

  15. [23]

    Improved mutual informat ion measure for clustering, classification, and community detection

    Newman ME, Cantwell GT, Young JG. Improved mutual informat ion measure for clustering, classification, and community detection. Physical R eview E. 2020;101(4):042304

    2020

  16. [24]

    N/A” cells are those netwo rks that are not available; see text for explanation. There are three out-of-memory (oom) entries (top row) and one “time-out

    Peixoto TP. 11. In: Bayesian Stochastic Blockmodeling. John Wile y & Sons, Ltd; 2019. p. 289–332. Available from: https://onlinelibrary.wiley.com/doi/abs/10.1002/9781119483298.ch11. February 17, 2025 19/19 arXiv:2502.00686v3 [cs.SI] 13 Feb 2025 Supplementary Materials for Impr...

    2019 arXiv

  17. [2025]

    Available from: https://doi.org/10.13012/B2IDB-9805305_V1

    doi

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.