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

редактировать

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

Содержание

1 Предпосылки
2 Определение
3 Ссылки
4 Дополнительная литература

Предпосылки

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

Определение

Экспоненциальное семейство - это широкое семейство моделей для охвата многих типов данных, а не только сетей. ERGM - это модель из этого семейства, которая описывает сети.

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

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

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

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

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

Ссылки

Дополнительная литература

Бышкин, М.; Stivala, A.; Мира, А.; Робинс, G.; Ломи, А. (2018). «Быстрая оценка максимального правдоподобия через ожидание равновесия для больших сетевых данных». Научные отчеты. 8 (1): 11509. arXiv : 1802.10311. Bibcode : 2018NatSR... 811509B. DOI : 10.1038 / s41598-018-29725-8. PMC 6068132. PMID 30065311.
Caimo, A.; Фрил, Н. (2011). «Байесовский вывод для экспоненциальных моделей случайных графов». Социальные сети. 33 : 41–55. arXiv : 1007.5192. doi : 10.1016 / j.socnet.2010.09.004.
Erds, P.; Реньи, А (1959). «На случайных графах». Publicationes Mathematicae. 6 : 290–297.
Fienberg, S.E.; Вассерман, С. (1981). "Обсуждение экспоненциального семейства распределений вероятностей для ориентированных графов Холландом и Лейнхардтом". Журнал Американской статистической ассоциации. 76 (373): 54–57. doi : 10.1080 / 01621459.1981.10477600.
Frank, O.; Штраус, Д. (1986). «Марковские графы». Журнал Американской статистической ассоциации. 81 (395): 832–842. doi : 10.2307 / 2289017. JSTOR 2289017.
Handcock, M. S.; Хантер, Д. Р.; Butts, C. T.; Goodreau, S.M.; Моррис, М. (2008). «statnet: программные средства для представления, визуализации, анализа и моделирования сетевых данных». Журнал статистического программного обеспечения. 24 : 1–11. doi : 10.18637 / jss.v024.i01.
Харрис, Дженин К. (2014). Введение в моделирование экспоненциального случайного графа. Сейдж.
Хантер, Д.Р.; Goodreau, S.M.; Хэндкок, М.С. (2008). «Степень соответствия моделей социальных сетей». Журнал Американской статистической ассоциации. 103 (481): 248–258. CiteSeerX 10.1.1.206.396. doi : 10.1198 / 016214507000000446.
Хантер, Д. Р.; Хэндкок, М.С. (2006). «Вывод в изогнутых экспоненциальных моделях семейства для сетей». Журнал вычислительной и графической статистики. 15 (3): 565–583. CiteSeerX 10.1.1.205.9670. doi : 10.1198 / 106186006X133069.
Хантер, Д.Р.; Handcock, M. S.; Butts, C. T.; Goodreau, S.M.; Моррис, М. (2008). «ergm: пакет для подгонки, моделирования и диагностики моделей экспоненциального семейства для сетей». Журнал статистического программного обеспечения. 24 (3): 1-29. doi : 10.18637 / jss.v024.i03.
Jin, I.H.; Лян, Ф. (2012). «Подгонка моделей социальных сетей с использованием алгоритма MCMC варьирующейся стохастической аппроксимации усечения». Журнал вычислительной и графической статистики. 22 (4): 927–952. doi : 10.1080 / 10618600.2012.680851.
Koskinen, J. H.; Робинс, Г. Л.; Паттисон, П. Э. (2010). «Анализ моделей экспоненциального случайного графа (p-star) с отсутствующими данными с использованием байесовского увеличения данных». Статистическая методология. 7 (3): 366–384. doi : 10.1016 / j.stamet.2009.09.007.
Morris, M.; Handcock, M. S.; Хантер, Д. Р. (2008). «Спецификация моделей случайных графов экспоненциального семейства: термины и вычислительные аспекты». Журнал статистического программного обеспечения. 24 (4). doi : 10.18637 / jss.v024.i04.
Rinaldo, A.; Fienberg, S.E.; Чжоу, Ю. (2009). «О геометрии дискретных экспоненциальных случайных семейств с применением к моделям экспоненциальных случайных графов». Электронный статистический журнал. 3 : 446–484. arXiv : 0901.0026. doi : 10.1214 / 08-EJS350.
Робинс, Дж.; Snijders, T.; Wang, P.; Handcock, M.; Паттисон, П. (2007). «Последние разработки в моделях экспоненциального случайного графа (p *) для социальных сетей» (PDF). Социальные сети. 29 (2): 192–215. doi : 10.1016 / j.socnet.2006.08.003.
Швайнбергер, Майкл (2011). «Неустойчивость, чувствительность и вырождение дискретных экспоненциальных семейств». Журнал Американской статистической ассоциации. 106 (496): 1361–1370. doi : 10.1198 / jasa.2011.tm10747. PMC 3405854. PMID 22844170.
Швайнбергер, Михаэль; Хэндкок, Марк (2015). «Локальная зависимость в моделях случайных графов: характеристика, свойства и статистический вывод». Журнал Королевского статистического общества, серия B. 77 (3): 647–676. doi : 10.1111 / rssb.12081. PMC 4637985. PMID 26560142.
Швайнбергер, Майкл; Стюарт, Джонатан (2020). «Концентрация и согласованность результатов для канонических и криволинейных моделей экспоненциального семейства случайных графов». Летопись статистики. 48 (1): 374–396. arXiv : 1702.01812. doi : 10.1214 / 19-AOS1810.
Снайдерс, Т.А.Б. (2002). "Оценка методом Монте-Карло цепью Маркова моделей экспоненциальных случайных графов" (PDF). Журнал социальной структуры. 3.
Снайдерс, Т.А.Б.; Pattison, P.E.; Робинс, Г. Л.; Хэндкок, М.С. (2006). «Новые спецификации для экспоненциальных моделей случайных графов». Социологическая методология. 36 : 99–153. CiteSeerX 10.1.1.62.7975. doi : 10.1111 / j.1467-9531.2006.00176.x.
Strauss, D; Икеда, М. (1990). «Оценка псевдодостоверности социальных сетей». Журнал Американской статистической ассоциации. 5 (409): 204–212. DOI : 10.2307 / 2289546. JSTOR 2289546.
ван Дуйн, М.А.; Снайдерс, Т.А.Б.; Зийлстра, Б. Х. (2004). «p2: модель случайных эффектов с ковариатами для ориентированных графов». Statistica Neerlandica. 58 (2): 234–254. doi : 10.1046 / j.0039-0402.2003.00258.x.
van Duijn, M.A.J.; Джайл, К. Дж. ; Хэндкок, М. С. (2009). «Структура для сравнения оценок максимального псевдоядия и максимального правдоподобия моделей экспоненциального семейства случайных графов». Социальные сети. 31 (1): 52–62. doi : 10.1016 / j.socnet.2008.10.003. PMC 3500576. PMID 23170041.

^Харрис, Дженин К. (2014). Введение в моделирование экспоненциального случайного графа. ISBN 9781452220802. OCLC 870698788.