Fluctuations of the Giant of Poisson Random Graphs

Basic Information

• Paper ID: 2501.01354
• Title: Fluctuations of the Giant of Poisson Random Graphs
• Author: David Clancy, Jr.
• Classification: math.PR (Probability Theory)
• Publication Date: January 3, 2025
• Paper Link: https://arxiv.org/abs/2501.01354

Abstract

Enriquez, Faraud, and Lemaire (2023) established process-level fluctuation theory for the giant connected component of dynamic Erdős-Rényi random graphs above the critical threshold, proving that the limit is a centered Gaussian process with continuous sample paths. Corujo, Limic, and Lemaire (2024) recently obtained a random walk proof. This paper demonstrates that analogous results hold for rank-one inhomogeneous models when the empirical weight distribution converges to a limit and its second moment also converges.

Research Background and Motivation

1. Problem to be Addressed: This paper investigates the functional central limit theorem for fluctuations of the giant connected component in rank-one inhomogeneous random graph models, which represents an important generalization of classical Erdős-Rényi random graph results.
2. Significance of the Problem:
   • The giant connected component of random graphs is a central concept in network theory, describing the emergence of large-scale connected structures
   • Understanding its fluctuation properties is crucial for network stability analysis and phase transition theory
   • Inhomogeneous models are closer to real-world networks, where nodes have different connection propensities
3. Limitations of Existing Methods:
   • Previous results have primarily focused on homogeneous Erdős-Rényi models
   • For inhomogeneous models, particularly those with general weight distributions, systematic theoretical results are lacking
4. Research Motivation: To generalize the profound results of Enriquez et al. on dynamic Erdős-Rényi graphs to more general rank-one inhomogeneous models using the novel "synchronized breadth-first walk" approach.

Core Contributions

1. Main Theoretical Result: Proves that under appropriate conditions, the joint fluctuations of the size and volume of the giant connected component in rank-one inhomogeneous random graphs converge to a two-dimensional Gaussian process
2. Methodological Innovation: Employs Limic's "synchronized breadth-first walk" method, providing a more direct proof pathway than the original approach
3. Generalization of Classical Results: Extends the functional central limit theorem for Erdős-Rényi graphs to more general inhomogeneous settings
4. Technical Contributions: Establishes convergence of weighted empirical processes and controls endpoint behavior of excursion intervals through refined analysis

Detailed Methodology

Problem Formulation

Consider a random graph $G_n(w,\lambda)$ with weight vector $w = (w_1, \ldots, w_n)$, where each edge $\{i,j\}$ appears independently with probability $1-\exp(-\lambda w_i w_j/n)$. We study the fluctuation behavior of the giant connected component size $L_n(\lambda)$ and volume $V_n(\lambda)$ when $\lambda > \lambda_{crit} = 1/E[W^2]$.

Model Architecture

1. Random Graph Model:
   • Node set: $[n] = \{1,2,\ldots,n\}$
   • Weights: $w_i > 0$ for node $i$
   • Edge probability: $P(i \sim j) = 1-\exp(-\lambda w_i w_j/n)$
2. Key Parameter Definitions:

   ϕ_p^{(n)}(t) = E[W_n^p(1-e^{-W_n t})] = Σ_{j=1}^n n^{-1} w_j^p (1-e^{-w_j t})
   θ^{(n)}(λ) = inf{t > 0 : ϕ_1^{(n)}(λt) - t < 0}
   ρ^{(n)}(λ) = ϕ_0^{(n)}(λθ^{(n)}(λ))
   β^{(n)}(λ) = 1 - λE[W_n^2 e^{-W_n λθ^{(n)}(λ)}]
   

3. Breadth-First Walk Representation: Utilizing Limic's results, the giant connected component is linked to the longest excursion interval of the random walk $X_{n,1}(λt) - t$.

Technical Innovations

1. Weighted Empirical Process Method: Employs Shorack's weighted empirical process convergence theorem to establish the functional central limit theorem for $X_{n,p}(t)$
2. Excursion Interval Analysis: Controls fluctuations of excursion interval endpoints through refined analysis:
   • Left endpoint $g_n(\lambda) \to 0$
   • Right endpoint $d_n(\lambda)$ fluctuations determined by Gaussian process $\Psi_1$
3. Uniform Convergence: Establishes uniform convergence of relevant quantities on compact sets, ensuring strong convergence of processes

Experimental Setup

This is a purely theoretical work with no numerical experiments. The theoretical results are verified primarily through rigorous mathematical proofs.

Theoretical Verification Methods

1. Skorohod Representation: Uses the Skorohod representation theorem to establish almost sure couplings
2. Uniform Estimates: Establishes precise asymptotic behavior through Taylor expansion and uniform convergence
3. Tightness Arguments: Verifies tightness conditions for processes to ensure weak convergence

Experimental Results

Main Theoretical Results

Theorem 1.3 (Main Result): Under Assumption 1.2, $\left(\left(\frac{L_n(\lambda) - ρ^{(n)}(\lambda)n}{n^{1/2}}, \frac{V_n(\lambda) - θ^{(n)}(\lambda)n}{n^{1/2}}\right); \lambda > \lambda_{crit}\right) \xrightarrow{d} (X(\lambda); \lambda > \lambda_{crit})$

where $X$ is a two-dimensional centered continuous Gaussian process: $X(\lambda) = \left(\Ψ_0(λθ(λ)) + \frac{λϕ'_0(λθ(λ))}{β(λ)}Ψ_1(λθ(λ)), \frac{1}{β(λ)}Ψ_1(λθ(λ))\right)$

Covariance Structure

The Gaussian processes $Ψ_0, Ψ_1$ have covariance: $E[Ψ_p(s)Ψ_q(t)] = E[W^{p+q}e^{-Ws}(1-e^{-Wt})]$ for all $s \leq t$ and $p,q \in \{0,1\}$.

Technical Results

• Theorem 2.5: Establishes the functional central limit theorem for weighted empirical processes
• Theorem 3.1: Precisely characterizes fluctuation behavior of excursion interval endpoints
• Proposition 3.3: Provides uniform lower bound estimates for excursion intervals

Related Work

1. Classical Results:
   • Stepanov (1970): First CLT for Erdős-Rényi graph giant component
   • Pittel (1990): Improved formula formulations
   • Bollobás & Riordan (2012): Random walk methods
2. Dynamic Graph Theory:
   • Enriquez, Faraud, Lemaire (2023): Process-level fluctuations for dynamic Erdős-Rényi graphs
   • Corujo, Limic, Lemaire (2024): Random walk proof methods
3. Inhomogeneous Models:
   • Martin-Löf (1986): Generalized random epidemic models
   • Neal (2007): CLT for variable generalized random epidemics
   • This paper unifies these results within the rank-one graph model framework

Conclusions and Discussion

Main Conclusions

This paper successfully generalizes the profound theory of giant component fluctuations in dynamic Erdős-Rényi random graphs to rank-one inhomogeneous models. Under conditions of weak convergence of weight distributions and convergence of second moments, it establishes a complete functional central limit theorem.

Limitations

1. Weight Distribution Conditions: Requires weak convergence and second moment convergence of weight distributions, which may be restrictive in certain applications
2. Near-Critical Behavior: The paper notes that for barely supercritical regimes, different assumptions on weight vectors are necessary
3. Higher-Order Moments: Qualitatively different near-critical behavior occurs when weight distributions have finite or infinite third moments

Future Directions

1. Barely Supercritical Regime: Study behavior when $\lambda = \lambda_{crit} + t\varepsilon_n$
2. More General Graph Models: Extend to finite type stochastic block models
3. Application Extensions: Apply theory to practical network analysis

In-Depth Evaluation

Strengths

1. Theoretical Depth: Provides important generalization of rank-one inhomogeneous random graph theory, filling theoretical gaps in the field
2. Methodological Innovation: Cleverly employs Limic's breadth-first walk method, making proofs more direct and transparent
3. Technical Rigor: Proof is rigorous, particularly demonstrating sophisticated techniques in refined analysis of excursion interval endpoints
4. Unified Framework: Unifies seemingly disparate results (epidemic models, random graph theory) under a single framework

Weaknesses

1. Limited Applications: As purely theoretical work, lacks numerical verification and practical application examples
2. Restrictive Conditions: Assumptions are relatively strong, particularly the second moment convergence condition may be difficult to verify in practice
3. Technical Threshold: Employs extensive advanced probability techniques, limiting accessibility of results

Impact

1. Academic Value: Provides important theoretical tools for random graph theory, expected to be widely cited in the field
2. Methodological Contribution: Demonstrates the power of breadth-first walk methods in analyzing complex random structures
3. Subsequent Research: Lays theoretical foundation for studying more complex network models

Applicable Scenarios

1. Theoretical Research: Provides important tools for probability and random graph theory researchers
2. Network Science: Applicable to analyzing large-scale networks with heterogeneity
3. Epidemiology: Provides theoretical support for understanding transmission processes in heterogeneous populations

References

The paper cites core literature in the field, including:

• 1 Aldous (1997): Multiplicative coalescence theory
• 12 Enriquez, Faraud, Lemaire (2023): Dynamic Erdős-Rényi graph fluctuations
• 16 Limic (2019): Breadth-first walk methods
• 27 Shorack (1979): Weighted empirical process theory

These citations fully reflect the author's deep understanding of related fields and the precise positioning of this work within the academic genealogy.