The number of connected components in sub-critical random graph processes

Josu\'e Corujo

The number of connected components in sub-critical random graph processes

T0 review · 0 major / 2 minor · reviewed 2026-05-23 · grok-4.3

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

Pith's one-line read Sub-critical multiplicative random graph processes have an explicit fluid limit for the normalized number of connected components plus a diffusion limit on fluctuations.

desk verdict The paper gives explicit closed-form fluid and diffusion limits for the normalized count of connected components in sub-critical multiplicative random graph processes. read the letter →

arxiv 2406.06380 v2 pith:U4GE2PKL submitted 2024-06-10 math.PR

Josué Corujo This is my paper

classification math.PR

keywords randomgraphprocessesconnectedcomponentsfluidlimitsdiffusionsub-criticalregimemultiplicativeprocessErdős-Rényigraphs

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

The paper examines the dynamics of the number of connected components in random graph models where new edges form at a rate equal to the product of the current sizes of their endpoints. It derives a closed-form expression for the fluid limit of this count after normalizing by the initial value, valid up to the time when the process would turn critical. The work also characterizes the scaled fluctuations around that limit as converging to a diffusion process. The same results are specialized to the Erdős-Rényi case with mean degree strictly below one. These limits describe how networks fragment before large-scale connectivity emerges.

What carries the argument

The multiplicative random graph process (edges appear independently after an exponential time at rate equal to the product of vertex sizes); the normalized count of connected components together with its fluid and diffusion limits.

What would settle it

Simulate the multiplicative process with fixed initial vertex sizes, stop at a time strictly below the critical threshold given by the reciprocal of the sum of squared sizes, and check whether the sample average of the normalized component count matches the paper's explicit fluid-limit formula within Monte-Carlo error.

Watch

Extended reading notes

Core claim

We provide an explicit expression for the fluid limit of the number of connected components normalized by its initial value, when the time is smaller than the inverse of the sum of the square of the initial vertex sizes. We also identify the diffusion limit of the rescaled fluctuations around the fluid limit. This is applied to several examples. In the particular setting of the Erdős-Rényi graph process, we explicit the fluid limit of the number of connected components normalized, and the diffusion limit of the scaled fluctuations in the sub-critical regime, where the mean degree is between zero and one.

Load-bearing premise

The process remains strictly sub-critical throughout the interval so that no giant component forms and component sizes stay controlled by the initial configuration.

Editorial extensions

If this is right

The normalized number of components converges in probability to an explicit deterministic function of time.
The properly rescaled fluctuations around the fluid limit converge in distribution to a diffusion process whose characteristics are identifiable.
The same limits hold for the Erdős-Rényi process when the mean degree lies between zero and one.
The results extend to arbitrary initial vertex-size configurations provided the sub-critical time bound is respected.

Reading between the lines

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

The explicit formulas could be used to approximate component counts in moderately large finite graphs without running full simulations.
Similar scaling arguments might track other observables such as the empirical component-size distribution in the same regime.
The technique may transfer to related multiplicative coalescence models arising in population genetics or polymerization.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The main thing to know is that this work supplies explicit expressions for the fluid limit of the number of connected components (normalized by the initial value) and the diffusion limit of fluctuations around it, valid up to the standard sub-critical time horizon set by the sum of squared initial sizes. They specialize the result to the Erdős-Rényi case with mean degree between 0 and 1. That is the concrete advance over existing mean-field treatments of coalescence processes. The derivations appear to follow the usual route of ODEs for the fluid part and martingale or generator methods for the fluctuations, which is appropriate for this setting. The sub-critical cutoff is the conventional one that keeps component sizes controlled by the initial configuration, so no hidden assumption jumps out. The abstract states the limits cleanly without obvious circularity or fitted parameters. The only real limitation visible is that the full proofs and technical sections are not in front of us, so any edge cases in the initial vertex-size distribution or error bounds cannot be checked directly. Still, the claims line up with standard analysis for multiplicative kernels and do not contradict the cited literature. This is a paper for people already working on component evolution in random graphs or coalescence models. A reader who needs usable approximations for large sub-critical graphs would find the closed forms helpful. It is focused and technically grounded enough to merit a serious referee rather than a desk reject.

Referee Report

0 major / 2 minor

Summary. The paper studies the evolution of the number of connected components in sub-critical multiplicative random graph processes, where edges form independently at exponential times with rate equal to the product of the sizes of the two vertices. It derives an explicit fluid limit for the number of components normalized by its initial value, valid for times strictly less than the reciprocal of the sum of squares of the initial vertex sizes, and identifies the diffusion limit of the rescaled fluctuations around this fluid limit. The results are applied to several examples, with a detailed treatment of the Erdős-Rényi graph process in the sub-critical regime (mean degree between 0 and 1).

Significance. If the derivations hold, the explicit fluid and diffusion limits supply precise, closed-form descriptions of component-count evolution in the sub-critical regime of multiplicative coalescence, which is a standard but often only implicitly characterized regime in random-graph theory. The parameter-free character of the fluid limit (under the stated time cutoff) and the explicit fluctuation scaling are strengths that could facilitate further analytic work on component statistics before the emergence of a giant component.

minor comments (2)

The abstract and introduction state the time horizon as 'smaller than the inverse of the sum of the square of the initial vertex sizes,' but the precise normalization (whether the sum is over all vertices or only a subset) should be clarified in the model definition section to avoid ambiguity with the standard 1/∑v_i² cutoff.
In the Erdős-Rényi application, the fluid limit is described as 'explicit' for mean degree in (0,1); a short remark comparing the obtained expression to the known solution of the associated ODE (e.g., via the generating-function approach) would strengthen the presentation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments appear in the provided report, so there are no specific points requiring point-by-point response.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The paper states an explicit fluid limit for the normalized number of connected components and the associated diffusion limit under the standard sub-critical regime (time < 1/sum of squared initial sizes). These expressions are derived directly from the multiplicative coalescence process definition via mean-field ODEs and fluctuation analysis; the sub-critical cutoff is an external modeling assumption that keeps components controlled by the initial configuration and is not obtained from the limits themselves. No self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations appear in the provided claims or abstract. The derivation chain is self-contained against the process definition.

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

The work rests on standard constructions of continuous-time random graph processes and on the assumption that the process stays sub-critical. No free parameters, invented entities, or non-standard axioms are mentioned in the abstract.

assumptions (2)

domain assumption Edges appear independently after exponential waiting times with rate equal to the product of component sizes.
This defines the multiplicative random graph process under study.
domain assumption Time horizon is strictly less than the inverse of the sum of squared initial vertex sizes.
This enforces the sub-critical regime in which the fluid limit is claimed to hold.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The number of connected components in sub-critical random graph processes." pith.science (2026). https://pith.science/paper/U4GE2PKL

@misc{pith2026240606380,
  author       = {Pith},
  title        = {Pith review of: The number of connected components in sub-critical random graph processes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U4GE2PKL}},
  note         = {Machine review of arXiv:2406.06380}
}

read the original abstract

We present a detailed study of the evolution of the number of connected components in sub-critical multiplicative random graph processes. We consider a model where edges appear independently after an exponential time at rate equal to the product of the sizes of the vertices. We provide an explicit expression for the fluid limit of the number of connected components normalized by its initial value, when the time is smaller than the inverse of the sum of the square of the initial vertex sizes. We also identify the diffusion limit of the rescaled fluctuations around the fluid limit. This is applied to several examples. In the particular setting of the Erd\H{o}s-R\'enyi graph process, we explicit the fluid limit of the number of connected components normalized, and the diffusion limit of the scaled fluctuations in the sub-critical regime, where the mean degree is between zero and one.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Aldous and V

D. Aldous and V. Limic, The entrance boundary of the multiplicative coalescent, Electron. J. Probab. 3 (1998), paper 3, 59

work page 1998
[2]

Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent, Ann

D. Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent, Ann. Probab. 25 (1997), no. 2, 812--854

work page 1997
[3]

Billingsley, Convergence of probability measures, New York - London - Sydney - Toronto : John Wiley and Sons , Inc

P. Billingsley, Convergence of probability measures, New York - London - Sydney - Toronto : John Wiley and Sons , Inc . XII , 253 p. (1968)., 1968

work page 1968
[4]

ed., Wiley Ser

, Convergence of probability measures., 2nd ed. ed., Wiley Ser. Probab. Stat., Chichester: Wiley, 1999 (English)

work page 1999
[6]

, The standard augmented multiplicative coalescent revisited, arXiv e-prints 2305.04716 https://arxiv.org/abs/2305.04716 (2023)

work page Pith review arXiv 2023
[7]

Del Moral and S

P. Del Moral and S. Penev, Stochastic processes. From applications to theory , Chapman Hall/CRC Texts Stat. Sci. Ser., Boca Raton, FL: CRC Press, 2017

work page 2017
[8]

N.\ Enriquez, G.\ Faraud, and S.\ Lemaire, The process of fluctuations of the giant component of an E rd o s--Rényi graph , arXiv 2311.07701 (2023)

work page arXiv 2023
[9]

S. N. Ethier and T. G. Kurtz, Markov processes. C haracterization and convergence , Wiley Ser. Probab. Math. Stat., John Wiley & Sons, Hoboken, NJ, 1986

work page 1986

Show all 17 references

[10]

Erd o s and A

P. Erd o s and A. R \'e nyi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci., Ser. A 5 (1960), 17--61

1960
[11]

Konarovskyi and V

V. Konarovskyi and V. Limic , On Moments of Multiplicative Coalescents , arXiv e-prints (2021), arXiv:2108.11799

2021
[12]

Limic, Properties of the multiplicative coalescent, Ph.D

V. Limic, Properties of the multiplicative coalescent, Ph.D. thesis, UC Berkeley, 1998

1998
[13]

Limic, The eternal multiplicative coalescent encoding via excursions of L \'e vy -type processes , Bernoulli 25 (2019), no

V. Limic, The eternal multiplicative coalescent encoding via excursions of L \'e vy -type processes , Bernoulli 25 (2019), no. 4A, 2479--2507

2019
[14]

Norros and H

I. Norros and H. Reittu, On a conditionally poissonian graph process, Advances in Applied Probability 38 (2006), no. 1, 59–75

2006
[15]

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

2005
[16]

A. V. Skorokhod, Limit theorems for stochastic processes, Teor. Veroyatn. Primen. 1 (1956), 289--319 (Russian)

1956
[17]

van der Hofstad, Random graphs and complex networks

R. van der Hofstad, Random graphs and complex networks. Volume 1 , Camb. Ser. Stat. Probab. Math., vol. 43, Cambridge: Cambridge University Press, 2017

2017
[18]

Whitt, Proofs of the martingale FCLT , Probability Surveys 4 (2007), no

W. Whitt, Proofs of the martingale FCLT , Probability Surveys 4 (2007), no. none, 268 -- 302

2007

Pith tools

Reviewed May 23, 2026 · model on record in the stance chip above.

[1] [1]

Aldous and V

D. Aldous and V. Limic, The entrance boundary of the multiplicative coalescent, Electron. J. Probab. 3 (1998), paper 3, 59

work page 1998

[2] [2]

Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent, Ann

D. Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent, Ann. Probab. 25 (1997), no. 2, 812--854

work page 1997

[3] [3]

Billingsley, Convergence of probability measures, New York - London - Sydney - Toronto : John Wiley and Sons , Inc

P. Billingsley, Convergence of probability measures, New York - London - Sydney - Toronto : John Wiley and Sons , Inc . XII , 253 p. (1968)., 1968

work page 1968

[4] [4]

ed., Wiley Ser

, Convergence of probability measures., 2nd ed. ed., Wiley Ser. Probab. Stat., Chichester: Wiley, 1999 (English)

work page 1999

[5] [6]

, The standard augmented multiplicative coalescent revisited, arXiv e-prints 2305.04716 https://arxiv.org/abs/2305.04716 (2023)

work page Pith review arXiv 2023

[6] [7]

Del Moral and S

P. Del Moral and S. Penev, Stochastic processes. From applications to theory , Chapman Hall/CRC Texts Stat. Sci. Ser., Boca Raton, FL: CRC Press, 2017

work page 2017

[7] [8]

N.\ Enriquez, G.\ Faraud, and S.\ Lemaire, The process of fluctuations of the giant component of an E rd o s--Rényi graph , arXiv 2311.07701 (2023)

work page arXiv 2023

[8] [9]

S. N. Ethier and T. G. Kurtz, Markov processes. C haracterization and convergence , Wiley Ser. Probab. Math. Stat., John Wiley & Sons, Hoboken, NJ, 1986

work page 1986