A central limit theorem for the giant in a stochastic block model

David Clancy Jr

REVIEW 1 major objections 5 minor 2 cited by

A central limit theorem for the giant in a stochastic block model

T0 review · 1 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read This paper proves that the vector of giant-component counts in a finite-type stochastic block model has Gaussian fluctuations at the $n^{-1/2}$ scale, with an explicit covariance formula.

desk verdict A credible and mostly explicit CLT for the K-weighted giant in a finite-type SBM, but the proof as written has a load-bearing gap in the positivity reduction and a wrong argument in Lemma 3.5. read the letter →

arxiv 2501.01351 v1 pith:KRS5JE4Q submitted 2025-01-02 math.PR

David Clancy Jr This is my paper · ORCID

classification math.PR MSC 60F0505C80

keywords stochasticblockmodelgiantcomponentcentrallimittheorembreadth-firstwalkexcursionrepresentationdeltamethodrandomgraphssupercriticalphase

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

This paper proves a central limit theorem for the vector of class-wise counts of the largest connected component (the giant) in a finite-type stochastic block model. Under mild conditions on class sizes and connection probabilities, it shows that $n^{1/2}(n^{-1} K C_n^{(1)} - K M \rho)$ converges in distribution to an explicit Gaussian vector. The limit combines intrinsic sampling noise with first-order perturbations coming from class-size imbalances and edge-probability shifts. The proof is short because it encodes the random graph by a breadth-first walk whose largest jump is the rescaled giant, reducing the computation to an invariance principle and the delta method. A reader should care because the result gives a concise, explicit fluctuation formula for the giant in a multi-type random graph, not just a qualitative Gaussian limit.

What carries the argument

The load-bearing object is the breadth-first walk $T(y,v,Z^{(n)})$ built from entrywise Poisson-like processes $Z_{i,j}^{(n)}$; the associated excursion representation identifies the jumps of this walk with $n^{-1} K C_n^{(l)}$, so the largest jump is exactly the rescaled giant. The proof then uses the classical invariance principle for empirical distribution functions to write $Z^{(n)}=\phi + n^{-1/2}\Psi + o(n^{-1/2})$, where $\phi(t)_i=-t_i+\sum_j \kappa_{ij}\mu_j(1-e^{-t_j})$ has a zero set containing the deterministic point $t_0=KM\rho$. The delta method with Jacobian $J=KM(I-\mathrm{diag}(\rho))-I$ converts fluctuations of $\phi$ at $t_0$ into fluctuations of the walk's endpoint, giving the stated Gaussian limit.

What would settle it

Simulate a two-type stochastic block model with $n=10^5$, fixed $\mu$, supercritical $K$, nonzero $\beta$ and $\Lambda$, and estimate the covariance matrix of $n^{1/2}(n^{-1} K C_n^{(1)} - K M \rho)$ across many repetitions; if the estimated covariance disagrees with the theorem's formula beyond sampling error, Theorem 1.3 is false.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is Theorem 1.3: under its Assumption 1.1, if $C_n^{(1)}$ is the vector of class counts of the largest component, $K=(\kappa_{ij})$, $M=\mathrm{diag}(\mu)$, and $\rho$ is the unique positive fixed point of $1-\exp(-\sum_j \kappa_{ij}\mu_j\rho_j)=\rho_i$, then $n^{1/2}(n^{-1} K C_n^{(1)} - K M \rho)$ converges in distribution to $J^{-1}K\zeta - J^{-1}(KB + \Lambda M)\rho - \Lambda M\rho$, where $J=KM(I-\mathrm{diag}(\rho))-I$, $B=\mathrm{diag}(\beta)$, $\Lambda=(\lambda_{ij})$, and the $\zeta_j$ are independent centered normals with variance $\mu_j\rho_j(1-\rho_j)$. The parameter $\beta_j$ describes the $n^{1/2}$ perturbation of class size $n_j$, and $\lambda_{ij}$ the $n^{1/2}$ perturbation of connection rates. In the one-class case the formula reduces to the classical central limit theorem for the giant in the sparse random graph $G(n,c/n)$, and with a nonzero $\lambda$ it matches the previously known perturbed single-type result.

Load-bearing premise

The proof assumes that the imported excursion representation is valid for this model and that perturbing any zero connection rates to small positive values does not change the limit; the second reduction is asserted rather than proved.

Editorial extensions

If this is right

When the model has a single class and the perturbation parameters vanish, the theorem's limit reduces to the classical CLT for the giant in $G(n,c/n)$ with variance $\sigma^2(c)$.
For a finite-type stochastic block model, the theorem gives an explicit Gaussian law for the class-wise counts of the giant, including first-order corrections from class-size imbalances and edge-probability perturbations.
At the $n^{1/2}$ scale, all smaller components are negligible: the largest of them is $O_P(\log n)$, so only the giant's fluctuations contribute to the limit.
The limit's covariance is controlled by the matrix $J=KM(I-\mathrm{diag}(\rho))-I$, and the proof implies this matrix is invertible throughout the supercritical regime.
The proof strategy shows the CLT follows from the invariance principle for empirical distribution functions plus the delta method, avoiding component-specific generating function analysis.

Reading between the lines

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

One can pursue the same excursion representation to derive CLTs for other additive functionals of the giant, such as internal edge counts, by replacing the jump functional $K C_n^{(1)}$ with a different component-level statistic.
The explicit covariance formula could be used to build asymptotic confidence intervals for class sizes in a fitted stochastic block model, an application the paper does not discuss.
The unproved continuity when zero connection rates are perturbed to positive values suggests a numerical check at a boundary where one $\kappa_{ij}=0$ but the matrix $KM$ remains irreducible; if the limit's covariance changes discontinuously there, the proof's reduction would need repair.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Read it. The main result is a CLT for the K-weighted giant component vector in a finite-type SBM, with an explicit Gaussian covariance that includes first-order perturbations in class sizes and connection probabilities. That is genuinely new: Neal's work covers the unperturbed case, and Bhamidi-Budhiraja-Sakanaveeti give a functional CLT with the covariance buried in an SDE system. The proof strategy is clean, the rescaling computations check out, and the d=1 reduction to Stepanov's theorem is correct. Lemma 3.7 is a nice elementary estimate.

Two soft spots keep it from being finished. First, Section 3.1's WLOG reduction to strictly positive κ_{i,i} is unjustified as written. The excursion representation of [6] requires positive diagonal entries, but Assumption 1.1 allows zeros. The one-line appeal to Janson's asymptotic equivalence doesn't work at this scale: a fixed δ>0 perturbation changes edge probabilities by δ/n, and the Hellinger affinity over n^2 pairs decays like exp(-c δ^2 n), so the laws are not asymptotically equivalent. You would need a perturbation of order o(n^{-1/2}) and then a continuity argument for the limiting expression. Neither appears. This is load-bearing because every subsequent lemma uses positivity to define the processes.

Second, the proof of Lemma 3.5 makes an invalid Perron-Frobenius inference. The coordinate-wise inequality KM v_y ≤ λ_1 v_y does not imply v_y is a scalar multiple of the Perron eigenvector a; there can be slack in some coordinates. The lemma may be true, but the proof doesn't show it. There is also a minor mismatch between the title/abstract, which promise a CLT for the number of vertices in the giant, and the theorem, which states the result for K C_n^(1). For d>1 the raw vertex count is not directly covered.

I don't think any of this sinks the underlying claim; the result is very likely true and the method is right. But the paper as it stands proves the theorem only for positive diagonal K and even there has a defective hitting-time lemma. It deserves a serious referee who can ask for a proper treatment of the positivity reduction and a corrected (or cited) proof of Lemma 3.5. Send it out, with those conditions.

Referee Report

1 major / 5 minor

Summary. The paper proves a central limit theorem for the rescaled vector of class counts in the largest connected component of a finite-type stochastic block model, allowing first-order perturbations in the class sizes and in the connection probability matrix. Under an irreducibility and supercriticality condition, the limit is Gaussian with an explicit covariance formula. The proof uses the excursion representation of [6] for a degree-corrected SBM and follows the approach of [7], reducing the fluctuations to those of empirical distribution functions of exponential variables and a delta-method step.

Significance. If the result is correct, it is a valuable contribution: it gives an explicit Gaussian fluctuation formula for the component size vector in a finite-type SBM with perturbations, recovers Stepanov's CLT for Erdős-Rényi graphs, and complements the functional CLT of Bhamidi et al. [2] with a concise single-time covariance. The proof strategy is elegant and the analytic steps (Donsker, delta method) are largely transparent. The main obstacle is the treatment of zero entries in the connection matrix K, which the current manuscript does not adequately resolve.

major comments (1)

[Section 3.1] The reduction to κ^{(n)}_{i,j} > 0 is not justified. The sentence 'This can be done without loss of generality by considering a perturbation sufficiently small and using the general equivalence of Janson [11]' is insufficient: for sparse graphs, adding a fixed δ>0 to κ changes the edge probabilities by δ/n, and the Hellinger affinity over n^2 pairs is exp(-c δ^2 n), so the laws are not asymptotically equivalent. A perturbation that preserves the n^{1/2}-fluctuation limit must be o(n^{-1/2}) in κ, and one must then prove both that the excursion representation of [6] applies uniformly in n to the perturbed model and that the limiting expression in Theorem 1.3 is continuous as the perturbation vanishes. Without this, Theorem 1.3 is proved only for matrices K with strictly positive entries, a strict subset of Assumption 1.1. This point is load-bearing because the processes X^{(n)} and Z^{(n)} and Corollary 3.2 require κ_{i,i}>0.

minor comments (5)

[Lemma 3.5] The Perron-Frobenius step is invalid: the inequality KM v_y ≤ λ_1 v_y is derived only up to an O(||v_y||^2) term that is not controlled coordinate-wise, and Perron-Frobenius theory does not imply proportionality from such an approximate inequality. The lemma is not used in Sections 3.5-3.6, so it should be corrected or removed.
[Section 1.1.2] The first displayed equation has an erroneous square: the factor should be 1/(1-c(1-ρ)) without the square, otherwise the variance does not match σ^2(c). The second displayed equation writes 'KJ^{-1}' where 'K^{-1}J^{-1}' is meant. These typos obscure the verification of the Erdős-Rényi reduction.
[Section 3.2] The text says 'The second inequality follows from t = n^{-1/3} diag(K)s', but the displayed transformation is an equality; the word 'inequality' should be 'equality'.
[Abstract and Section 3.1] There are several typographical errors: 'proof for of' in the abstract should be 'proof of', 'stocahstic' should be 'stochastic', and 'Perron-Frobinous'/'eigevnector' should be 'Perron-Frobenius'/'eigenvector'.
[Proof of Lemma 3.6] The convergence n^{1/2} Z^{(n)}(R_n) ⇒ 0 is said to follow 'immediately'; the proof should spell out that the jump of Z^{(n)} over the giant component cancels exactly in the limit, so that Z^{(n)}(R_n) ≈ Z^{(n)}(L_n-). This would make the argument easier to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the CLT is derived from Donsker's theorem, the fixed-point equation, and the Delta method; the self-cited excursion representation is an independent structural theorem.

full rationale

The central derivation is not circular. The fluctuation limit is obtained from Lemma 3.3, which is an application of Donsker's theorem to the empirical distribution of Exp(1) variables, followed by a Delta-method argument using the Jacobian J = phi'(t0) and the inverse function theorem (Lemma 3.8). The deterministic centering rho is defined by the fixed-point equation (1.3), not fitted from the target fluctuation. The self-cited Theorem 3.1 and Corollary 3.2 from [6] provide an excursion representation identifying the jumps of the breadth-first walk with n^{-1}K C_n^{(l)}; this representation is parameter-free, has stated assumptions (kappa_{i,i} > 0), and does not assume the CLT being proved, so it is independent support rather than a circular premise. The d=1 reduction recovers Stepanov's externally known CLT, providing a benchmark that confirms the derivation has independent content. The only notable issue is a proof gap, not circularity: Section 3.1 asserts the positivity reduction 'without loss of generality by considering a perturbation sufficiently small and using the general equivalence of Janson [11]' without supplying the required rate or continuity argument for the n^{1/2} fluctuations, so the proof as written may not cover zero entries of K. This is a correctness risk, not a case of the conclusion being assumed as an input. Self-citation [6] is load-bearing but does not make the target limit an input, fitted parameter, or renamed known result.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The theorem's only inputs are the model parameters (μ, β, K, Λ) and the fixed point ρ; none are fitted to data. The proof imports several external theorems: the BJR law of large numbers, the excursion representation of [6], Donsker's theorem, Perron-Frobenius, and the Delta method. The least justified input is the WLOG positivity of κ entries, which is asserted.

assumptions (7)

standard math BJR weak law and O_P(log n) bound for small components (Proposition 1.2, from [3])
Used in Section 3.5 to identify the giant and bound the small components; imported from Bollobás, Janson and Riordan.
standard math Excursion representation of [6] (Theorem 3.1): T(y,v,X) has jumps n^{-2/3} diag(K)^{-1} K C_n(l), and after rescaling jumps are n^{-1} K C_n(l) (Corollary 3.2).
Core encoding that connects the walk to component vectors; cited, not reproven.
standard math Donsker's theorem for empirical distribution functions of Exp(1) variables (Lemma 3.3)
Used to derive the Gaussian noise field Ψ.
standard math Perron-Frobenius theorem for irreducible nonnegative matrices, including the eigenvalue bound λ_1^*<1 for KM(I-diag(ρ))
Used in Lemma 2.2 to prove J is invertible and in Lemma 3.5.
standard math Skorohod representation theorem and the Delta method / inverse function theorem (Lemma 3.8)
Used in Section 3.6 to convert convergence of φ(R_n) into convergence of R_n.
ad hoc to paper Strict positivity of K^{(n)} entries can be assumed WLOG via Janson's asymptotic equivalence [11]
Section 3.1 asserts this reduction without showing the CLT limit is continuous under the perturbation; this is a proof convenience specific to the paper.
domain assumption Assumption 1.1: asymptotic expansion of class sizes (i), connection probabilities (ii), and irreducibility/supercriticality (iii)
These are the model assumptions under which the theorem is stated.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A central limit theorem for the giant in a stochastic block model." pith.science (2026). https://pith.science/paper/KRS5JE4Q

@misc{pith2026250101351,
  author       = {Pith},
  title        = {Pith review of: A central limit theorem for the giant in a stochastic block model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KRS5JE4Q}},
  note         = {Machine review of arXiv:2501.01351}
}

read the original abstract

We provide a simple proof for of the central limit theorem for the number of vertices in the giant for super-critical stochastic block model using the breadth-first walk of Konarovskyi, Limic and the author (2024). Our approach follows the recent work of Corujo, Limic and Lemaire (2024) and reduces to the classic central limit theorem for the Erd\H{o}s-R\'{e}nyi model obtained by Stepanov (1970).

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

Functional Central limit theorems for microscopic and macroscopic functionals of inhomogeneous random graphs
math.PR 2024-12 conditional novelty 7.0 of 10

For finite-type inhomogeneous random graphs, component-density fluctuations converge to a Gaussian process solving an explicit infinite-dimensional SDE, yielding CLTs for the giant component and MST weight.
Asymptotic normality of the giant component size in a random bipartite graph
math.CO 2026-07 conditional novelty 3.0 of 10

The giant component of G(n,n,p) with np→c>1 satisfies a central limit theorem with variance 2σ².

Reference graph

Works this paper leans on

20 extracted references · 14 canonical work pages · cited by 2 Pith papers

[6]

Degree corrected stochastic block model: excursion representation

D. Clancy, Jr., V. Konarovskyi, and V. Limic. Degree corrected s tochastic block model: excursion representation. arXiv e-prints , page arXiv:2409.18894, Sept. 2024

work page Pith review arXiv 2024
[7]

Corujo, S

J. Corujo, S. Lemaire, and V. Limic. A novel approach to the gian t component ﬂuctuations. arXiv e-prints, page arXiv:2412.06995, Dec. 2024

arXiv 2024
[2]

Bhamidi, A

S. Bhamidi, A. Budhiraja, and A. Sakanaveeti. Functional centr al limit theorems for microscopic and macroscopic functionals of inhomogeneous random graphs, 2024

work page 2024
[11]

S. Janson. Asymptotic equivalence and contiguity of some rand om graphs. Random Structures & Algo- rithms, 36(1):26–45, 2010

work page 2010
[1]

Barraez, S

D. Barraez, S. Boucheron, and W. Fernandez de la Vega. On the ﬂuctuations of the giant component. Combin. Probab. Comput. , 9(4):287–304, 2000

2000
[3]

Bollob´ as, S

B. Bollob´ as, S. Janson, and O. Riordan. The phase transition in inhomogeneous random graphs. Random Structures Algorithms, 31(1):3–122, 2007

work page 2007
[4]

Bollob´ as and O

B. Bollob´ as and O. Riordan. Asymptotic normality of the size of th e giant component via a random walk. J. Combin. Theory Ser. B , 102(1):53–61, 2012

2012
[5]

Chaumont and M

L. Chaumont and M. Marolleau. Fluctuation theory for spectrally positive additive L´ evy ﬁelds.Electron. J. Probab., 25:Paper No. 161, 26, 2020

work page 2020

Show all 20 references

[8]

Enriquez, G

N. Enriquez, G. Faraud, and S. Lemaire. The process of ﬂuctua tions of the giant component of an Erd˝ os-R´ enyi graph.arXiv e-prints , page arXiv:2311.07701, Nov. 2023

2023 arXiv
[9]

Erd˝ os and A

P. Erd˝ os and A. R´ enyi. On the evolution of random graphs.Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl., 5:17–61, 1960

1960
[10]

P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic block models: ﬁrst steps. Social Networks , 5(2):109–137, 1983

1983
[12]

P. Neal. SIR epidemics on a Bernoulli random graph. J. Appl. Probab. , 40(3):779–782, 2003

2003
[13]

P. Neal. Multitype randomized Reed-Frost epidemics and epidemic s upon random graphs. Ann. Appl. Probab., 16(3):1166–1189, 2006

2006
[14]

B. Pittel. On tree census and the giant component in sparse ran dom graphs. Random Structures Algo- rithms, 1(3):311–342, 1990

1990
[15]

A. A. Puhalskii. Stochastic processes in random graphs. Ann. Probab., 33(1):337–412, 2005

2005
[16]

B. R´ ath. A moment-generating formula for Erd¨ os-R´ enyi component sizes. Electron. Commun. Probab., 23:Paper No. 24, 14, 2018

2018
[17]

V. E. Stepanov. On the probability of connectedness of a rand om graph Gm(t). Theory of Probability & Its Applications, 15(1):55–67, 1970

1970
[18]

van der Hofstad

R. van der Hofstad. Random graphs and complex networks. Vol. 1 . Cambridge Series in Statistical and Probabilistic Mathematics, [43]. Cambridge University Press, Cambrid ge, 2017

2017
[19]

A. W. van der Vaart. Asymptotic statistics , volume 3 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 1998

1998
[20]

W. Woess. Denumerable Markov chains . EMS Textbooks in Mathematics. European Mathematical Society (EMS), Z¨ urich, 2009. Generating functions, boundary t heory, random walks on trees

2009

Pith tools

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

[1] [6]

Degree corrected stochastic block model: excursion representation

D. Clancy, Jr., V. Konarovskyi, and V. Limic. Degree corrected s tochastic block model: excursion representation. arXiv e-prints , page arXiv:2409.18894, Sept. 2024

work page Pith review arXiv 2024

[2] [7]

Corujo, S

J. Corujo, S. Lemaire, and V. Limic. A novel approach to the gian t component ﬂuctuations. arXiv e-prints, page arXiv:2412.06995, Dec. 2024

arXiv 2024

[3] [2]

Bhamidi, A

S. Bhamidi, A. Budhiraja, and A. Sakanaveeti. Functional centr al limit theorems for microscopic and macroscopic functionals of inhomogeneous random graphs, 2024

work page 2024

[4] [11]

S. Janson. Asymptotic equivalence and contiguity of some rand om graphs. Random Structures & Algo- rithms, 36(1):26–45, 2010

work page 2010

[5] [1]

Barraez, S

D. Barraez, S. Boucheron, and W. Fernandez de la Vega. On the ﬂuctuations of the giant component. Combin. Probab. Comput. , 9(4):287–304, 2000

2000

[6] [3]

Bollob´ as, S

B. Bollob´ as, S. Janson, and O. Riordan. The phase transition in inhomogeneous random graphs. Random Structures Algorithms, 31(1):3–122, 2007

work page 2007

[7] [4]

Bollob´ as and O

B. Bollob´ as and O. Riordan. Asymptotic normality of the size of th e giant component via a random walk. J. Combin. Theory Ser. B , 102(1):53–61, 2012

2012

[8] [5]

Chaumont and M

L. Chaumont and M. Marolleau. Fluctuation theory for spectrally positive additive L´ evy ﬁelds.Electron. J. Probab., 25:Paper No. 161, 26, 2020

work page 2020