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

Функциональная центральная предельная теорема для подсчёта подграфов в динамической модели случайного соединения

Основная информация

  • 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 (теория вероятностей)
  • Дата публикации: 22 ноября 2025 г.
  • Ссылка на статью: 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. Разработку динамического расширения метода кумулянтов для доказательства функциональной ЦПТ
  3. Предоставление теоретической основы для практических приложений, таких как процессы коэффициента кластеризации

Основные вклады

Основные вклады работы включают:

  1. Функциональная центральная предельная теорема: Доказана функциональная ЦПТ для многомерных процессов подсчёта подграфов в динамической RCM (теорема 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. Примеры приложений: Основные результаты применены к процессу коэффициента кластеризации, доказана функциональная ЦПТ для процесса отношения подграфов (предложение 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. Формула кумулянтов для графов Использована формула кумулянтов для пуассоновских 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. Ключевые оценки для доказательства плотности Для доказательства условия плотности (условие Биллингсли): $$\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): Через устройство Крамера-Вольда и метод кумулянтов доказано, что высшие кумулянты $\text{cum}_M(S_n) \to 0$ ($M\geq 3$) 2. **Плотность** (раздел 6): Через проверку условия Биллингсли, используя анализ связности разбиений и временные оценки для марковского процесса ## Связанные работы ### Статические модели случайного соединения 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. **Динамические графы Эрдёша-Рёньи**: - Chatterjee & Varadhan (2011): принцип больших отклонений для статических графов ER - Braunsteins et al. (2023): большие отклонения по путям для динамических графов ER - Erdős et al. (2013): спектральная статистика графов ER (статический случай) - Hazra et al. (2025a): функциональная ЦПТ для главного собственного значения динамических графов ER - Hazra et al. (2025b): функциональная ЦПТ для одновременного подсчёта подграфов в динамических графах ER ### Уникальный вклад данной работы - **Впервые** обобщена функциональная ЦПТ на динамическую модель случайного соединения (более общую пространственную модель, чем графы ER) - **Впервые** систематически применён метод кумулянтов для доказательства плотности в динамических случайных геометрических графах - Предоставлена единая теоретическая схема для плотной и разреженной областей ## Заключение и обсуждение ### Основные выводы 1. **Установление функциональной ЦПТ**: Успешно доказана функциональная центральная предельная теорема для многомерных процессов подсчёта подграфов в динамической RCM, предел является гауссовским процессом, структура ковариации которого явно зависит от: - Пространственной структуры (через $F^+_{ij}$ или $F^-_{ij}$) - Временной корреляции (через $Z(|t-s|)$) - Параметрической области (плотная vs разреженная) 2. **Методологический прорыв**: Метод кумулянтов применим не только к конечномерной сходимости, но и эффективно обрабатывает условия плотности в функциональных предельных теоремах, демонстрируя широкую применимость метода 3. **Практическое приложение**: Функциональная ЦПТ для процессов отношения подграфов (таких как коэффициент кластеризации) предоставляет теоретическую основу для анализа статистических свойств динамических сетей ### Ограничения 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), ограничивая богатство результатов - Ковариация процесса отношения подграфов равна нулю в плотной области (предложение 3), ограничивая практическое значение 3. **Техническая сложность**: - Система обозначений разбиений ($\Pi, \tilde{\Pi}, \bar{\Pi}$ и т.д.) довольно абстрактна, затрудняя понимание для начинающих - Технические детали доказательства плотности в разделе 6 плотны, читаемость может быть улучшена 4. **Реалистичность модели**: - Предположение независимой активации/деактивации узлов не выполняется во многих реальных сетях - Метрика тора, хотя технически удобна, отдалена от практических приложений ### Влияние 1. **Вклад в область**: - **Важный теоретический прогресс**: Впервые функциональная ЦПТ обобщена на динамическую модель случайного соединения - **Методологический вклад**: Демонстрирует мощь метода кумулянтов в динамических условиях - Закладывает основу для теории динамических пространственных случайных графов 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 - Инновационное применение метода кумулянтов для доказательства плотности - Техническая строгость и полнота результатов Основные недостатки — отсутствие численной верификации и вырожденное явление в плотной области. Данная работа закладывает прочную основу для статистической теории динамических пространственных случайных сетей и, как ожидается, будет иметь продолжительное влияние на теорию случайных геометрических графов и сетевую науку. Рекомендуется исследователям, интересующимся функциональными предельными теоремами для случайных графов, теорией пуассоновских процессов или анализом динамических сетей.