Модели случайных графов экспоненциального семейства

Экспоненциальные модели случайных графов (ERGM) — это семейство статистических моделей для анализа данных из социальных и других сетей . Примеры сетей, исследованных с использованием ERGM, включают сети знаний, организационные сети, сети коллег, социальные сети, сети научных разработок, и другие.

Фон

Существует множество метрик для описания структурных особенностей наблюдаемой сети, таких как плотность, центральность или ассортативность. Однако эти метрики описывают наблюдаемую сеть, которая является лишь одним экземпляром большого количества возможных альтернативных сетей. Этот набор альтернативных сетей может иметь схожие или разные структурные особенности. Для поддержки статистических выводов о процессах, влияющих на формирование сетевой структуры, статистическая модель должна учитывать набор всех возможных альтернативных сетей, взвешенных по их сходству с наблюдаемой сетью. Однако, поскольку сетевые данные по своей сути являются реляционными, они нарушают предположения о независимости и идентичном распределении стандартных статистических моделей, таких как линейная регрессия . Альтернативные статистические модели должны отражать неопределенность, связанную с данным наблюдением, позволять делать выводы об относительной частоте сетевых подструктур, представляющих теоретический интерес, устранять неоднозначность влияния мешающих процессов, эффективно представлять сложные структуры и связывать процессы локального уровня со свойствами глобального уровня. рандомизация с сохранением степени Например, — это особый способ, с помощью которого наблюдаемую сеть можно рассматривать с точки зрения множества альтернативных сетей.

Определение

Семейство Exponential — это широкое семейство моделей, охватывающих многие типы данных, а не только сети. ERGM — это модель из этого семейства, описывающая сети.

Формально случайный граф $Y\in {\mathcal {Y}}$ состоит из набора $n$ узлы и набор связанных переменных $\{Y_{ij}:i=1,\dots ,n;j=1,\dots ,n\}$, индексированный парами узлов $ij$, где $Y_{ij}=1$ если узлы $(i,j)$ соединены ребром и $Y_{ij}=0$ в противном случае. Пара узлов $ij$ называется диадой, а диада является ребром, если $Y_{ij}=1$.

Основное предположение этих моделей состоит в том, что структура наблюдаемого графа $y$ можно объяснить заданным вектором достаточной статистики $s(y)$ которые являются функцией наблюдаемой сети и, в некоторых случаях, узловых атрибутов. Таким образом можно описать любую зависимость между недвоичными переменными:

$P(Y=y|\theta )={\frac {\exp(\theta ^{T}s(y))}{c(\theta )}},\quad \forall y\in {\mathcal {Y}}$

где $\theta$ вектор параметров модели, связанный с $s(y)$ и $c(\theta )=\sum _{y'\in {\mathcal {Y}}}\exp(\theta ^{T}s(y'))$ является нормирующей константой.

Эти модели представляют распределение вероятностей в каждой возможной сети на $n$ узлы. Однако размер множества возможных сетей для неориентированной сети (простого графа) размера $n$ является $2^{n(n-1)/2}$. Поскольку количество возможных сетей в наборе значительно превышает количество параметров, которые могут ограничить модель, идеальным распределением вероятностей является то, которое максимизирует энтропию Гиббса .

Пример

Позволять $V=\{1,2,3\}$ быть набором из трех узлов и пусть ${\mathcal {Y}}$ быть множеством всех неориентированных графов без петель на $V$. Loopless подразумевает, что для всех $i=1,2,3$ это $Y_{ii}=0$ и ненаправленный означает, что для всех $i,j=1,2,3$ это $Y_{ij}=Y_{ji}$, так что есть три двоичные переменные связи ( $Y_{12},Y_{13},Y_{23}$) и $2^{3}=8$ в этом примере разные графики.

Определите двумерный вектор статистики с помощью $s(y)=[s_{1}(y),s_{2}(y)]^{T}$, где $s_{1}(y)=edges(y)$ определяется как количество ребер в графе $y$ и $s_{2}(y)=triangles(y)$ определяется как количество замкнутых треугольников в $y$. Наконец, пусть вектор параметров определяется формулой $\theta =(\theta _{1},\theta _{2})^{T}=(-\ln 2,\ln 3)^{T}$, так что вероятность каждого графа $y\in {\mathcal {Y}}$ в этом примере определяется:

$P(Y=y|\theta )={\frac {\exp(-\ln 2\cdot edges(y)+\ln 3\cdot triangles(y))}{c(\theta )}}$

Заметим, что в этом примере существует всего четыре класса изоморфизма графа : граф с нулевыми ребрами, три графа ровно с одним ребром, три графа ровно с двумя ребрами и граф с тремя ребрами. Поскольку изоморфные графы имеют одинаковое количество ребер и одинаковое количество треугольников, они также имеют одинаковую вероятность в этом примере ERGM. Для представителя $y$ каждого класса изоморфизма мы сначала вычисляем член $x(y)=\exp(-\ln 2\cdot edges(y)+\ln 3\cdot triangles(y))$, что пропорционально вероятности $y$ (с точностью до нормирующей константы $c(\theta )$).

Если $y$ граф с нулевыми ребрами , то это $edges(y)=0$ и $triangles(y)=0$, так что

$x(y)=\exp(-\ln 2\cdot 0+\ln 3\cdot 0)=\exp(0)=1.$

Если $y$ является графом ровно с одним ребром , то это $edges(y)=1$ и $triangles(y)=0$, так что

$x(y)=\exp(-\ln 2\cdot 1+\ln 3\cdot 0)={\frac {\exp(0)}{\exp(\ln 2)}}={\frac {1}{2}}.$

Если $y$ является графом ровно с двумя ребрами , то это $edges(y)=2$ и $triangles(y)=0$, так что

$x(y)=\exp(-\ln 2\cdot 2+\ln 3\cdot 0)={\frac {\exp(0)}{\exp(\ln 2)^{2}}}={\frac {1}{4}}.$

Если $y$ граф ровно с тремя ребрами , то он $edges(y)=3$ и $triangles(y)=1$, так что

$x(y)=\exp(-\ln 2\cdot 3+\ln 3\cdot 1)={\frac {\exp(\ln 3)}{\exp(\ln 2)^{3}}}={\frac {3}{8}}.$

Нормализующая константа вычисляется путем суммирования $x(y)$ по всем восьми различным графикам $y\in {\mathcal {Y}}$. Это дает:

$c(\theta )=1+3\cdot {\frac {1}{2}}+3\cdot {\frac {1}{4}}+{\frac {3}{8}}={\frac {29}{8}}.$

Наконец, вероятность каждого графа $y\in {\mathcal {Y}}$ дается $P(Y=y|\theta )={\frac {x(y)}{c(\theta )}}$. В явном виде мы получаем, что граф с нулевыми ребрами имеет вероятность ${\frac {8}{29}}$, каждый граф, имеющий ровно одно ребро, имеет вероятность ${\frac {4}{29}}$, каждый граф, имеющий ровно два ребра, имеет вероятность ${\frac {2}{29}}$, и граф ровно с тремя ребрами имеет вероятность ${\frac {3}{29}}$ в этом примере.

Интуитивно понятно, что структура вероятностей графа в этом примере ERGM соответствует типичным моделям социальных или других сетей . Отрицательный параметр ( $\theta _{1}=-\ln 2$), связанное с количеством ребер, означает, что при прочих равных условиях сети с меньшим количеством ребер имеют более высокую вероятность, чем сети с большим количеством ребер. Это согласуется с разреженностью , которая часто встречается в эмпирических сетях, а именно с тем, что эмпирическое количество ребер обычно растет медленнее, чем максимально возможное количество ребер. Положительный параметр ( $\theta _{2}=\ln 3$), связанное с количеством замкнутых треугольников, означает, что при прочих равных условиях сети с большим количеством треугольников имеют более высокую вероятность, чем сети с меньшим количеством треугольников. Это согласуется с тенденцией к триадной замкнутости , которая часто встречается в определенных типах социальных сетей. Сравните эти шаблоны с вероятностями на графике, вычисленными выше. Сложение каждого ребра делит вероятность на два. Однако при переходе от графа с двумя ребрами к графу с тремя ребрами количество треугольников увеличивается на один – что дополнительно умножает вероятность на три.

Заметим, что явный расчет всех вероятностей графов возможен только потому, что в этом примере очень мало разных графов. Поскольку количество различных графов экспоненциально масштабируется по количеству связующих переменных, что, в свою очередь, квадратично масштабируется по количеству узлов, вычисление нормализующей константы, как правило, вычислительно сложно , уже для умеренного количества узлов.

Выборка из ERGM

Точная выборка из данного ERGM в целом вычислительно сложна, поскольку вычисление нормализующей константы требует суммирования по всем $y\in {\mathcal {Y}}$. Эффективная приблизительная выборка из ERGM может быть выполнена с помощью цепей Маркова и применяется в современных методах для аппроксимации ожидаемых значений и оценки параметров ERGM. Неформально, если ERGM задан на множестве графов ${\mathcal {Y}}$ с функцией массы вероятности $P(Y=y|\theta )={\frac {\exp(\theta ^{T}s(y))}{c(\theta )}}$, выбирается исходный граф $y^{(0)}\in {\mathcal {Y}}$ (который может быть выбран произвольно или случайно или может представлять собой наблюдаемую сеть) и неявно определяет вероятности перехода (или вероятности скачка) $\pi (y,y')=P(Y^{(t+1)}=y'|Y^{(t)}=y)$, которые представляют собой условные вероятности того, что цепь Маркова находится на графе $y'$ после шага $t+1$, учитывая, что оно находится на графике $y$ после шага $t$. Вероятности перехода не зависят от графиков на предыдущих шагах ( $y^{(0)},\dots ,y^{(t-1)}$), что является определяющим свойством цепей Маркова и они не зависят от $t$, то есть цепь Маркова однородна во времени. Цель состоит в том, чтобы определить такие вероятности перехода, чтобы для всех $y\in {\mathcal {Y}}$ это

$\lim _{t\to \infty }P(Y^{(t)}=y)={\frac {\exp(\theta ^{T}s(y))}{c(\theta )}},$

не зависит от исходного графа $y^{(0)}$. Если это будет достигнуто, можно будет запустить цепь Маркова на большое количество шагов, а затем вернуть текущий граф как случайную выборку из данного ERGM. Вероятность вернуть график $y\in {\mathcal {Y}}$ после конечного, но большого количества шагов обновления примерно соответствует вероятности, определенной ERGM.

Современные методы отбора проб из ERGM с цепями Маркова обычно определяют шаг обновления двумя подэтапами: сначала случайным образом выбирают кандидата $y'$ в окрестности текущего графа $y$ и, во-вторых, принять $y'$ с вероятностью, которая зависит от отношения вероятностей текущего графа $y$ и кандидат $y'$. (Если кандидат не принят, цепь Маркова остается на текущем графике $y$.) Если множество графов ${\mathcal {Y}}$ не имеет ограничений (т. е. содержит любую комбинацию значений двоичных связующих переменных), простой метод выбора кандидата — выбрать одну связующую переменную $y_{ij}$ равномерно случайным образом и определить кандидата, перевернув эту единственную переменную (т. е. установив $y'_{ij}=1-y_{ij}$; все остальные переменные принимают то же значение, что и в $y$). Обычный способ определить вероятность принятия — принять $y'$ с условной вероятностью

$P(Y=y'|Y=y'\vee Y=y)={\frac {P(Y=y')}{P(Y=y')+P(Y=y)}},$

где вероятности графа определяются ERGM. Важно отметить, что нормировочная константа $c(\theta )$ сокращается в этой дроби, так что вероятности принятия могут быть вычислены эффективно.

Дальнейшее чтение

• Бышкин М.; Стивала, А.; Мира, А.; Робинс, Г.; Ломи, А. (2018). «Быстрая оценка максимального правдоподобия с помощью равновесного ожидания для больших сетевых данных» . Научные отчеты . 8 (1): 11509. arXiv : 1802.10311 . Бибкод : 2018НатСР...811509Б . дои : 10.1038/s41598-018-29725-8 . ПМК   6068132 . ПМИД   30065311 .
• Каймо, А.; Фрил, Н. (2011). «Байесовский вывод для моделей экспоненциальных случайных графов». Социальные сети . 33 : 41–55. arXiv : 1007.5192 . дои : 10.1016/j.socnet.2010.09.004 .
• Эрдеш, П.; Реньи, А (1959). «О случайных графах». Математические публикации . 6 : 290–297.
• Финберг, SE; Вассерман, С. (1981). «Обсуждение экспоненциального семейства вероятностных распределений для ориентированных графов Холланда и Лейнхардта». Журнал Американской статистической ассоциации . 76 (373): 54–57. дои : 10.1080/01621459.1981.10477600 .
• Франк, О.; Штраус, Д. (1986). «Марковские графики». Журнал Американской статистической ассоциации . 81 (395): 832–842. дои : 10.2307/2289017 . JSTOR   2289017 .
• Хэндкок, М.С.; Хантер, ДР; Баттс, Коннектикут; Гудро, С.М.; Моррис, М. (2008). «statnet: Программные средства для представления, визуализации, анализа и моделирования сетевых данных» . Журнал статистического программного обеспечения . 24 (1): 1–11. дои : 10.18637/jss.v024.i01 . ПМЦ   2447931 . ПМИД   18618019 .
• Харрис, Дженин К. (2014). Введение в экспоненциальное моделирование случайных графов. Мудрец.
• Хантер, ДР; Гудро, С.М.; Хэндкок, М.С. (2008). «Соответствие моделей социальных сетей». Журнал Американской статистической ассоциации . 103 (481): 248–258. CiteSeerX   10.1.1.206.396 . дои : 10.1198/016214507000000446 .
• Хантер, Д.Р.; Хэндкок, М.С. (2006). «Вывод в моделях криволинейного экспоненциального семейства для сетей». Журнал вычислительной и графической статистики . 15 (3): 565–583. CiteSeerX   10.1.1.205.9670 . дои : 10.1198/106186006X133069 .
• Хантер, ДР; Хэндкок, М.С.; Баттс, Коннектикут; Гудро, С.М.; Моррис, М. (2008). «ergm: пакет для подбора, моделирования и диагностики моделей экспоненциального семейства для сетей» . Журнал статистического программного обеспечения . 24 (3): 1–29. дои : 10.18637/jss.v024.i03 . ПМЦ   2743438 .
• Джин, Айдахо; Лян, Ф. (2012). «Подбор моделей социальных сетей с использованием алгоритма MCMC стохастической аппроксимации с различным усечением». Журнал вычислительной и графической статистики . 22 (4): 927–952. дои : 10.1080/10618600.2012.680851 .
• Коскинен, Дж. Х.; Робинс, Г.Л.; Паттисон, ЧП (2010). «Анализ моделей экспоненциального случайного графа (p-звезды) с отсутствующими данными с использованием байесовского увеличения данных» . Статистическая методология . 7 (3): 366–384. дои : 10.1016/j.stamet.2009.09.007 .
• Моррис, М.; Хэндкок, М.С.; Хантер, ДР (2008). «Спецификация моделей случайных графов экспоненциального семейства: термины и вычислительные аспекты» . Журнал статистического программного обеспечения . 24 (4): 1548–7660. дои : 10.18637/jss.v024.i04 . ПМЦ   2481518 . ПМИД   18650964 .
• Ринальдо, А.; Финберг, SE; Чжоу, Ю. (2009). «О геометрии дискретных экспоненциальных случайных семейств с применением к моделям экспоненциальных случайных графов». Электронный статистический журнал . 3 : 446–484. arXiv : 0901.0026 . дои : 10.1214/08-EJS350 .
• Робинс, Г.; Снейдерс, Т.; Ван, П.; Хэндкок, М.; Паттисон, П. (2007). «Последние разработки в моделях экспоненциального случайного графа (p *) для социальных сетей» (PDF) . Социальные сети . 29 (2): 192–215. дои : 10.1016/j.socnet.2006.08.003 . hdl : 11370/abee7276-394e-4051-a180-7b2ff57d42f5 .
• Швайнбергер, Майкл (2011). «Неустойчивость, чувствительность и вырождение дискретных экспоненциальных семейств» . Журнал Американской статистической ассоциации . 106 (496): 1361–1370. дои : 10.1198/jasa.2011.tm10747 . ПМЦ   3405854 . ПМИД   22844170 .
• Швайнбергер, Майкл; Хэндкок, Марк (2015). «Локальная зависимость в моделях случайных графов: характеристика, свойства и статистический вывод» . Журнал Королевского статистического общества, серия B. 77 (3): 647–676. дои : 10.1111/rssb.12081 . ПМЦ   4637985 . ПМИД   26560142 .
• Швайнбергер, Майкл; Стюарт, Джонатан (2020). «Результаты концентрации и согласованности для канонических и изогнутых экспоненциальных моделей случайных графов». Анналы статистики . 48 (1): 374–396. arXiv : 1702.01812 . дои : 10.1214/19-AOS1810 .
• Снейдерс, ТАБ (2002). «Оценка методом Монте-Карло экспоненциальных моделей случайных графов марковской цепью» (PDF) . Журнал социальной структуры . 3 .
• Снейдерс, TAB; Паттисон, ЧП; Робинс, Г.Л.; Хэндкок, М.С. (2006). «Новые спецификации экспоненциальных моделей случайных графов». Социологическая методология . 36 : 99–153. CiteSeerX   10.1.1.62.7975 . дои : 10.1111/j.1467-9531.2006.00176.x .
• Штраус, Д; Икеда, М. (1990). «Оценка псевдоправдоподобия для социальных сетей» . Журнал Американской статистической ассоциации . 5 (409): 204–212. дои : 10.2307/2289546 . JSTOR   2289546 .
• ван Дуйн, Массачусетс; Снейдерс, TAB; Зийлстра, Б.Х. (2004). «p2: модель случайных эффектов с ковариатами для ориентированных графов». Статистика Неерландики . 58 (2): 234–254. дои : 10.1046/j.0039-0402.2003.00258.x .
• ван Дуйн, MAJ; Джайл, Кей Джей ; Хэндкок, М.С. (2009). «Среда для сравнения оценки максимального псевдоправдоподобия и максимального правдоподобия моделей случайных графов экспоненциального семейства» . Социальные сети . 31 (1): 52–62. дои : 10.1016/j.socnet.2008.10.003 . ПМЦ   3500576 . ПМИД   23170041 .