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

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Компонент Резать Цикл Структура данных Край Петля Район Дорожка Вершина Список смежности  / матрица Список заболеваемости  / матрица Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
Метрики Алгоритмы
Центральность Степень Близость Близость PageRank Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия /СЭР
Списки Категории
Темы Программного обеспечения Сетевые ученые Категория: Теория сетей Категория: Теория графов

Экспоненциальные модели случайных графов (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}: я = 1, точки, n; j = 1, точки, п }}$ куда ${ displaystyle Y_ {ij} = 1}$ если узлы ${ displaystyle (я, 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 с ( theta) = сумма _ {y ' in { mathcal {Y}}} exp ( theta ^ {T} s (y'))}$ - нормализующая постоянная.

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

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

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

• Бышкин, М .; 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.