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

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

Фон

Существует множество показателей для описания структурных особенностей наблюдаемой сети, таких как плотность, центральность или ассортативность.^[6][7] Однако эти показатели описывают наблюдаемую сеть, которая является лишь одним из множества возможных альтернативных сетей. Этот набор альтернативных сетей может иметь похожие или отличные структурные особенности. Поддерживать статистические выводы о процессах, влияющих на формирование сетевой структуры, статистическая модель следует рассмотреть набор всех возможных альтернативных сетей, взвешенных по их сходству с наблюдаемой сетью. Однако, поскольку сетевые данные по своей природе реляционные, они нарушают предположения о независимости и идентичном распределении стандартных статистических моделей, таких как линейная регрессия.^[8][9] Альтернативные статистические модели должны отражать неопределенность, связанную с данным наблюдением, позволять делать выводы об относительной частоте сетевых подструктур, представляющих теоретический интерес, устранять неоднозначность влияния смешивающих процессов, эффективно представлять сложные структуры и связывать процессы локального уровня со свойствами глобального уровня.^[10] Рандомизация с сохранением степени, например, это особый способ рассмотрения наблюдаемой сети с точки зрения множества альтернативных сетей.

Определение

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

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

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

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

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

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

Рекомендации

1. Харрис, Дженин К. (2014). Введение в моделирование экспоненциального случайного графа. ISBN  9781452220802. OCLC  870698788.
2. Бреннеке, Юлия; Ранг, Олаф (2017-05-01). «Сеть знаний фирмы и передача рекомендаций корпоративным изобретателям - исследование многоуровневой сети». Политика исследования. 46 (4): 768–783. Дои:10.1016 / j.respol.2017.02.002. ISSN  0048-7333.
3. Харрис, Дженин К. (2013). «Коммуникационные связи через национальную сеть местных департаментов здравоохранения». AMEPRE Американский журнал профилактической медицины. 44 (3): 247–253. Дои:10.1016 / j.amepre.2012.10.028. ISSN  0749-3797. OCLC  4937103196. PMID  23415121.
4. Бреннеке, Юлия (2019). «Диссонирующие связи в внутриорганизационных сетях: почему люди ищут помощи в решении проблем от трудных коллег». Журнал Академии менеджмента AMJ. ISSN  0001-4273. OCLC  8163488129.
5. Харрис, Дженин К.; Люк, Дуглас А; Шелтон, Сара С; Цукерман, Рэйчел Б. (2009). «Сорок лет исследований вторичного дыма. Разрыв между открытием и доставкой». Американский журнал профилактической медицины. 36 (6): 538–548. Дои:10.1016 / j.amepre.2009.01.039. ISSN  0749-3797. OCLC  6980180781. PMID  19372026.
6. Вассерман, Стэнли; Фауст, Кэтрин (1994). Анализ социальных сетей: методы и приложения. ISBN  978-0-521-38707-1.
7. Ньюман, M.E.J. (2003). «Структура и функции сложных сетей». SIAM Обзор. 45 (2): 167–256. arXiv:cond-mat / 0303516. Bibcode:2003SIAMR..45..167N. Дои:10.1137 / S003614450342480.
8. Подрядчик, Ношир; Вассерман, Стэнли; Фауст, Кэтрин (2006). «Проверка много теоретических, многоуровневых гипотез об организационных сетях: аналитическая основа и эмпирический пример» (PDF). Академия менеджмента. 31 (3): 681–703. Дои:10.5465 / AMR.2006.21318925.
9. Харрис, Дженин К. (2014). Введение в моделирование экспоненциального случайного графа. ISBN  9781452220802. OCLC  870698788.
10. Робинс, G .; Pattison, P .; Kalish, Y .; Люшер, Д. (2007). «Введение в модели экспоненциального случайного графа для социальных сетей». Социальные сети. 29 (2): 173–191. Дои:10.1016 / j.socnet.2006.08.002. HDL:1959.3/216571.
11. Ньюман, M.E.J. (2010-03-25). «Другие сетевые модели». Сети. С. 565–585. ISBN  978-0-19-920665-0.

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

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

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