2025-11-25T22:01:17.838996

Functional central limit theorem for subgraph counts in a dynamic random connection model

Hazra, Kriukov, Mandjes et al.
We prove a functional central limit theorem for subgraph counts in a dynamic version of the random connection model. To establish tightness, we develop a dynamic extension of the cumulant method.
academic

Functional central limit theorem for subgraph counts in a dynamic random connection model

基本信息

  • 论文ID: 2511.18003
  • 标题: Functional central limit theorem for subgraph counts in a dynamic random connection model
  • 作者: Rajat Subhra Hazra (Leiden University), Nikolai Kriukov (University of Amsterdam), Michel Mandjes (Leiden University & University of Amsterdam), Moritz Otto (Leiden University)
  • 分类: math.PR (概率论)
  • 发表时间: 2025年11月22日
  • 论文链接: https://arxiv.org/abs/2511.18003

摘要

本文证明了动态随机连接模型中子图计数的泛函中心极限定理。为了建立紧性（tightness），作者开发了累积量方法的动态扩展。这是首次将累积量方法成功应用于证明动态随机几何图中的泛函极限定理。

研究背景与动机

核心问题

随机连接模型（Random Connection Model, RCM）是描述空间网络的基础随机几何模型，其中节点根据相互距离以某种概率连接。本文研究的核心问题是：在节点动态激活/失活的动态RCM中，子图计数过程的极限行为是什么？

问题重要性

  1. 理论意义：子图计数（如三角形、星形等）不仅捕捉局部连通模式，还在理解模型的高阶结构和极限行为中起关键作用
  2. 实际应用：动态网络更好地反映真实世界系统（通信网络、社交网络、生物网络）的行为，这些系统的边和/或顶点随时间随机变化
  3. 方法论贡献：现有研究主要集中在静态网络，动态情形的数学挑战更大

现有方法局限性

  1. 静态限制：经典的RCM研究（如Penrose, Schulte & Thäle等）主要关注静态图的渐近正态性
  2. 有限维收敛：累积量方法以往主要用于建立有限维收敛，未被系统地用于证明泛函极限定理的紧性
  3. 动态扩展困难：将静态结果推广到动态设置面临技术挑战，特别是在处理时间相关性时

研究动机

本文受到随机图文献中关注动态演化网络的趋势驱动，旨在：

  1. 将静态RCM的子图计数结果推广到动态设置
  2. 开发累积量方法的动态扩展以证明泛函CLT
  3. 提供聚类系数过程等实际应用的理论基础

核心贡献

本文的主要贡献包括：

  1. 泛函中心极限定理：证明了动态RCM中多元子图计数过程的泛函CLT（定理1），该结果在稠密（dense）和稀疏（sparse）两种参数区域均成立
  2. 累积量方法的动态扩展：首次系统地将累积量方法应用于证明动态随机几何图的紧性条件，展示了该方法的广泛适用性
  3. 精确协方差结构：明确刻画了极限高斯过程的协方差结构，区分了稠密和稀疏区域的不同行为：
    • 稠密区域：协方差为 Z(∣t−s∣)Fij+Z(|t-s|)F^+_{ij}
    • 稀疏区域：协方差为 (Z(∣t−s∣))qi1{qi=qj}Fij−(Z(|t-s|))^{q_i}1\{q_i=q_j\}F^-_{ij}
  4. 应用示例：将主要结果应用于聚类系数过程，证明了子图比率过程的泛函CLT（命题3）

方法详解

任务定义

输入：

  • 空间域：W=[−12,12]dW = [-\frac{1}{2}, \frac{1}{2}]^d（带环面度量）
  • 泊松点过程：ηn\eta_n 在 W×D([0,T],{0,1})W \times D([0,T], \{0,1\}) 上，强度测度 ndx⊗Qn dx \otimes Q
  • 连接概率函数：ϕn(x)=ϕ(∥x∥d/νn)\phi_n(x) = \phi(\|x\|_d/\nu_n)，其中 νn→0\nu_n \to 0
  • 状态转移率：激活率 μ\mu，失活率 λ\lambda

输出：

  • 多元子图计数过程 Γn(t)=(Γn,1(t),…,Γn,m(t))\Gamma_n(t) = (\Gamma_{n,1}(t), \ldots, \Gamma_{n,m}(t))，其中 Γn,i(t)=1ai∑Pqi∈ηn,≠qi1{∀(k,ℓ)∈E(Gi):Xk↔Xℓ}⋅∏k=1qiAk(t)\Gamma_{n,i}(t) = \frac{1}{a_i}\sum_{P_{q_i}\in\eta^{q_i}_{n,\neq}} 1\{\forall(k,\ell)\in E(G_i): X_k \leftrightarrow X_\ell\} \cdot \prod_{k=1}^{q_i} A_k(t)

目标：证明中心化和归一化后的过程 Γn∗(⋅)\Gamma^*_n(\cdot) 收敛到高斯过程 Γ(⋅)\Gamma(\cdot)

模型架构

动态随机连接模型

  1. 空间结构：节点位置从齐次泊松点过程采样，密度为 nn
  2. 动态机制：每个节点独立地在激活/失活状态间切换
    • 初始状态：以概率 ϱ=μ/(μ+λ)\varrho = \mu/(\mu+\lambda) 激活
    • 转移动态：失活→激活（率 μ\mu），激活→失活（率 λ\lambda）
  3. 边的生成：潜在边一次性采样并固定，但仅当两端节点同时激活时才出现在图中

归一化方案

定义归一化因子：

\varrho^{q_i}n^{(q_i-1)/2}\nu_n^{q_i-1}, & \nu_n \in \mathcal{D} \text{ (稠密)} \\ \varrho^{q_i}\sqrt{nq_i\nu_n^{q_i-1}}, & \nu_n \in \mathcal{S} \text{ (稀疏)} \end{cases}$$ 中心化归一化过程： $$\Gamma^*_{n,i}(t) = \frac{\Gamma_{n,i}(t) - \mathbb{E}[\Gamma_{n,i}(t)]}{\psi_{n,i}}$$ ### 技术创新点 #### 1. 分割与图论结构 引入分割集合 $\Pi(q_1,\ldots,q_m)$ 及其子集： - $\tilde{\Pi}(q_1,\ldots,q_m)$：诱导分割 $\sigma^*$ 只有一个块 - $\bar{\Pi}(q_1,\ldots,q_m)$：每行至少有一个元素属于大小 $\geq 2$ 的块 对每个分割 $\sigma$ 构造辅助图，其边集 $E_\sigma$ 反映子图间的重叠结构。 #### 2. 累积量图公式 利用Poisson U-统计量的累积量表示（来自Schulte & Thäle）： $$\text{cum}(S_1,\ldots,S_m) = \sum_{\sigma\in\tilde{\Pi}(q_1,\ldots,q_m)} \int_{X^{|\sigma|}} (\otimes_{l=1}^m f^{(l)})_\sigma d\mu^{|\sigma|}$$ 这将累积量与特定张量积的积分联系起来。 #### 3. 紧性证明的关键估计 为证明紧性条件（Billingsley条件）： $$\mathbb{E}[\|\Gamma^*_n(r)-\Gamma^*_n(s)\|^2 \|\Gamma^*_n(s)-\Gamma^*_n(t)\|^2] \leq C(t-r)^2$$ 关键步骤： 1. 将四阶矩表示为分割和： $$\Delta_{n,i,j}(r,s,t) = \sum_{\sigma\in\bar{\Pi}(q_i,q_i,q_j,q_j)} \int_{X^{|\sigma|}} (f^{(i)}\otimes f^{(i)}\otimes f^{(j)}\otimes f^{(j)})_\sigma d\mu_n^{|\sigma|}$$ 2. 分离空间和时间依赖： - **时间部分**：利用马尔可夫跳跃过程性质（引理6）得到 $|r-t|^2$ 界 - **空间部分**：根据辅助图的连通性应用引理5 3. 连通性分析： - 连通图：$I_n(\sigma) \sim \beta_1\nu_n^{|\sigma|-1}$ - 两个连通分量：$I_n(\sigma) \sim \beta_2\nu_n^{|\sigma|-2}$ #### 4. 稠密与稀疏区域的统一处理 通过精心设计的归一化因子 $\psi_{n,i}$，使得两种参数区域下的证明框架统一，但极限协方差结构不同： - **稠密区域** ($n\nu_n \to \infty$)：不同子图的计数完全相关 - **稀疏区域** ($n\nu_n \to 0$)：仅同构子图相关 ## 实验设置 ### 理论验证而非数值实验 本文是纯理论工作，不包含数值实验或模拟。验证通过严格的数学证明完成。 ### 参数配置 理论结果要求： 1. **基本条件**：$\lim_{n\to\infty}\nu_n = 0$，$\lim_{n\to\infty}n^{q_i}\nu_n^{q_i-1} = \infty$（对所有 $i\in[m]$） 2. **区域划分**： - 稠密区域：$n\nu_n \to \infty$（例如 $\nu_n = n^\gamma$，$-1<\gamma<0$） - 稀疏区域：$n\nu_n \to 0$（例如 $\nu_n = n^\gamma$，$-q_i/(q_i-1)<\gamma<-1$） ### 应用案例：聚类系数 考虑 $G_1$ 为三角形，$G_2$ 为楔形（wedge）： - $q=3$，$a_1=6$，$a_2=2$ - 定义积分常数： $$\kappa_d = \int_{\mathbb{R}^d}\phi(\|y\|_d)dy, \quad \tau_d = \int_{(\mathbb{R}^d)^2}\phi(\|y_1\|_d)\phi(\|y_2\|_d)\phi(\|y_1-y_2\|_d)d(y_1,y_2)$$ 聚类系数过程的协方差为： - 稠密区域：$\Sigma_C(s,t) = 0$（退化情形） - 稀疏区域：$\Sigma_C(s,t) = 9(Z(|t-s|))^3\left(\frac{36}{\tau_d} - \frac{90\kappa_d^2}{\tau_d^2} + \frac{54\kappa_d^4}{\tau_d^3}\right)$ ## 实验结果 ### 主要理论结果 **定理1（主要结果）**： 若 $\nu_n$ 满足条件(3)，则 $\Gamma^*_n(\cdot) \to \Gamma(\cdot)$（在 $D([0,T],\mathbb{R}^m)$ 中依分布收敛），其中 $\Gamma(\cdot)$ 是中心化高斯过程，协方差矩阵为： $$\Sigma_{i,j}(s,t) = \begin{cases} Z(|t-s|)F^+_{ij}, & \nu_n \in \mathcal{D} \\ (Z(|t-s|))^{q_i}1\{q_i=q_j\}F^-_{ij}, & \nu_n \in \mathcal{S} \end{cases}$$ 其中 $Z(t) = 1 + (\lambda/\mu)e^{-(\lambda+\mu)t}$ 刻画了马尔可夫跳跃过程的时间相关性。 **注记2（稠密区域的特殊性）**： 在稠密区域，可以写成 $F^+_{i,j} = (q_iF(G_i)/a_i)(q_jF(G_j)/a_j)$，这意味着 $\Gamma(\cdot)$ 的各分量完全相关，可表示为： $$\Gamma'_i(\cdot) = \frac{q_iF(G_i)}{a_i}\xi(\cdot)$$ 其中 $\xi(\cdot)$ 是标量高斯过程。 ### 应用结果 **命题3（子图比率过程）**： 设 $G_1, G_2$ 是连通图，满足 $V(G_1)=V(G_2)=q$ 且 $G_1\subset G_2$。定义子图比率过程： $$C_{n,G_1,G_2}(t) = \frac{a_1\Gamma_{n,1}(t)}{a_2\Gamma_{n,2}(t)}$$ 则中心化归一化后的过程 $C^*_{n,G_1,G_2}(\cdot)$ 收敛到中心化高斯过程 $C_{G_1,G_2}(\cdot)$。 **特别地**，在稠密区域 $\Sigma_C(s,t)=0$，这是因为分子和分母完全相关导致的退化现象。 ### 关键技术成果 1. **期望渐近**（引理7）： $$\mathbb{E}[\Gamma_{n,i}(t)] = \frac{F_n(G_i)(\varrho n)^{q_i}}{a_i}$$ 2. **协方差渐近**（引理8）： $$\text{Cov}(\Gamma_{n,i}(t),\Gamma_{n,j}(s)) \sim \sum_{m=1}^{q_i\wedge q_j}\sum_{H_1,H_2} \frac{n^{q_i+q_j-m}\varrho^{q_i+q_j}Z(|t-s|)^m}{m!(q_i-m)!(q_j-m)!}\nu_n^{q_i+q_j-m-1}F(H)$$ 3. **积分渐近**（引理5）： $$F_n(H) \sim \nu_n^{q-1}F(H)$$ 其中 $F(H)$ 是归一化的空间积分。 ### 证明策略的有效性 证明分两步： 1. **有限维收敛**（命题9）：通过Cramér-Wold装置和累积量方法，证明高阶累积量 $\text{cum}_M(S_n) \to 0$（$M\geq 3$） 2. **紧性**（第6节）：通过验证Billingsley条件，利用分割的连通性分析和马尔可夫过程的时间估计 ## 相关工作 ### 静态随机连接模型 1. **经典文献**： - Meester & Roy (1996)：连续渗流理论 - Penrose (1991, 2003)：随机几何图的基础工作 - Roy (2011)：随机几何图上的渗流 2. **子图计数**： - Penrose (2003)：静态RCM中子图计数的渐近正态性 - Schulte & Thäle (2017, 2024)：累积量方法在泊松泛函中的应用 - Liu & Privault (2024)：随机连接模型中子图计数的正态逼近 - Heerten et al. (2025)：权重依赖随机连接模型的中偏差 ### 动态随机图 1. **时序随机图综述**： - Holme & Saramäki (2012)：时序网络的物理学视角 2. **动态Erdős-Rényi图**： - Chatterjee & Varadhan (2011)：静态ER图的大偏差原理 - Braunsteins et al. (2023)：动态ER图的样本路径大偏差 - Erdős et al. (2013)：ER图的谱统计（静态） - Hazra et al. (2025a)：动态ER图主特征值的泛函CLT - Hazra et al. (2025b)：动态ER图同时子图计数的泛函CLT ### 本文的独特贡献 - **首次**将泛函CLT推广到动态随机连接模型（比ER图更一般的空间模型） - **首次**系统地用累积量方法证明动态随机几何图的紧性 - 提供了稠密和稀疏两种区域的统一理论框架 ## 结论与讨论 ### 主要结论 1. **泛函CLT的建立**：成功证明了动态RCM中多元子图计数过程的泛函中心极限定理，极限为高斯过程，其协方差结构明确依赖于： - 空间结构（通过 $F^+_{ij}$ 或 $F^-_{ij}$） - 时间相关性（通过 $Z(|t-s|)$） - 参数区域（稠密vs稀疏） 2. **方法论突破**：累积量方法不仅可用于有限维收敛，还能有效处理泛函极限定理的紧性条件，展示了该方法的广泛适用性 3. **实际应用**：子图比率过程（如聚类系数）的泛函CLT为分析动态网络的统计性质提供了理论基础 ### 局限性 1. **模型假设**： - 节点位置固定，仅状态动态变化（不考虑节点移动） - 独立激活/失活（实际网络可能存在空间或时间相关性） - 环面度量避免边界效应（实际应用中边界可能重要） 2. **参数限制**： - 要求 $\nu_n \to 0$ 且 $n^{q_i}\nu_n^{q_i-1} \to \infty$，排除了某些参数范围 - 稠密区域出现退化现象（完全相关），限制了应用 3. **技术限制**： - 证明依赖于连通图假设 - 未涉及更复杂的图结构（如有向图、多重图） ### 未来方向 虽然论文未明确列出，但可推断的研究方向包括： 1. **模型扩展**： - 考虑节点位置也动态变化的模型 - 引入空间或时间相关的激活机制 - 研究非马尔可夫的状态转移过程 2. **理论深化**： - 大偏差原理（类似Braunsteins et al.的工作） - 中偏差原理（类似Heerten et al.的工作） - 更精细的收敛速度估计 3. **应用拓展**： - 其他网络统计量（如直径、连通分量大小） - 多层动态网络 - 实际数据的统计推断 4. **计算方法**： - 开发高效的模拟算法 - 统计检验方法的实现 ## 深度评价 ### 优点 1. **理论严谨性**： - 证明完整且技术细节充分，从累积量的图公式到紧性的验证都有严格论证 - 区分稠密和稀疏区域，提供统一框架但尊重不同行为 - 引理5的积分渐近和引理6的时间估计为主要结果提供了坚实基础 2. **方法创新性**： - **关键创新**：将累积量方法从有限维收敛扩展到泛函极限定理的紧性证明 - 分割的连通性分析巧妙地处理了空间依赖结构 - 时间和空间依赖的分离处理展示了深刻的技术洞察 3. **结果完整性**： - 不仅证明了主要定理，还提供了实际应用（聚类系数） - 明确给出了极限高斯过程的协方差结构 - 注记2关于稠密区域完全相关性的观察很有价值 4. **写作清晰度**： - 结构清晰：动机→模型→预备知识→期望/协方差→有限维收敛→紧性→应用 - 技术准备充分（第3节的预备知识） - 图1直观展示了动态RCM的机制 ### 不足 1. **数值验证缺失**： - 作为纯理论工作，缺乏数值模拟验证理论预测 - 未提供有限样本下收敛速度的经验证据 - 实际应用案例仅停留在理论层面 2. **稠密区域的退化**： - 稠密区域下不同子图计数完全相关（注记2），限制了结果的丰富性 - 子图比率过程在稠密区域协方差为0（命题3），实际意义有限 3. **技术复杂度**： - 分割记号系统（$\Pi, \tilde{\Pi}, \bar{\Pi}$等）较为抽象，初学者理解困难 - 第6节紧性证明的技术细节密集，可读性可提升 4. **模型现实性**： - 节点独立激活/失活的假设在许多实际网络中不成立 - 环面度量虽然技术上方便，但与实际应用有距离 ### 影响力 1. **对领域的贡献**： - **重要理论进展**：首次将泛函CLT推广到动态随机连接模型 - **方法论贡献**：展示了累积量方法在动态设置中的强大功能 - 为动态空间随机图理论奠定了基础 2. **实用价值**： - 为动态网络的统计推断提供理论基础 - 聚类系数等网络指标的渐近理论可用于假设检验 - 潜在应用于无线网络、社交网络分析 3. **可复现性**： - 理论证明详细，可由专业人员验证 - 缺乏代码或数值实验，实际应用需要进一步工作 - 主要结果的条件明确，便于后续研究引用 ### 适用场景 1. **理论研究**： - 随机几何图理论的进一步发展 - 其他动态空间随机模型的极限定理 - 累积量方法的应用研究 2. **实际应用**： - **无线通信网络**：节点间连接依赖距离，节点可能周期性休眠 - **社交网络**：用户活跃度动态变化，连接概率依赖"社交距离" - **生物网络**：细胞或蛋白质的激活/失活动态 3. **统计推断**： - 动态网络数据的假设检验 - 网络参数（如激活率、连接函数）的估计 - 网络变化点检测 ## 参考文献（关键文献） 1. **Schulte & Thäle (2024)**: "Moderate deviations on Poisson chaos" - 累积量方法的核心文献 2. **Last et al. (2014)**: "Moments and central limit theorems for some multivariate Poisson functionals" - 泊松泛函理论基础 3. **Penrose (2003)**: "Random Geometric Graphs" - 随机几何图的经典教材 4. **Hazra et al. (2025b)**: "Functional CLT for simultaneous subgraph count of dynamic ER graphs" - 最相关的前期工作 5. **Billingsley (2013)**: "Convergence of Probability Measures" - 泛函极限定理的标准参考 --- ## 总体评价 这是一篇**高质量的理论概率论文**，在动态随机几何图领域做出了重要贡献。主要优势在于： - 首次建立动态RCM的泛函CLT - 创新性地将累积量方法用于紧性证明 - 技术严谨，结果完整 主要不足是缺乏数值验证和稠密区域的退化现象。该工作为动态空间随机网络的统计理论奠定了坚实基础，预期将对随机几何图理论和网络科学产生持续影响。推荐给对随机图极限定理、泊松过程理论或动态网络分析感兴趣的研究者。