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

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

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

Фон [ править ]

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

Определение [ править ]

Семейство Exponential - это широкое семейство моделей, охватывающих многие типы данных, а не только сети. 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 (я, 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'))}$

Эти модели представляют собой распределение вероятностей для каждой возможной сети на узлах. Однако размер множества возможных сетей для неориентированной сети (простого графа) составляет . Поскольку количество возможных сетей в наборе значительно превышает количество параметров, которые могут ограничивать модель, идеальное распределение вероятностей - это то, которое максимизирует энтропию Гиббса . ^[11]${\ displaystyle n}$${\ displaystyle n}$${\ Displaystyle 2 ^ {п (п-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 .
• Erdős, P .; Реньи, А (1959). «На случайных графах». Publicationes Mathematicae . 6 : 290–297.
• Fienberg, SE; Вассерман, С. (1981). "Обсуждение экспоненциального семейства распределений вероятностей для ориентированных графов Холландом и Лейнхардтом". Журнал Американской статистической ассоциации . 76 (373): 54–57. DOI : 10.1080 / 01621459.1981.10477600 .
• Франк, O .; Штраус, Д. (1986). «Марковские графы». Журнал Американской статистической ассоциации . 81 (395): 832–842. DOI : 10.2307 / 2289017 . JSTOR  2289017 .
• Handcock, MS; Хантер, DR; Окурки, CT; Гудро, С. М.; Моррис, М. (2008). «statnet: программные средства для представления, визуализации, анализа и моделирования сетевых данных» . Журнал статистического программного обеспечения . 24 : 1–11. DOI : 10,18637 / jss.v024.i01 .
• Харрис, Дженин К. (2014). Введение в моделирование экспоненциального случайного графа. Мудрец. ^[1]
• Хантер, DR; Гудро, С. М.; Handcock, MS (2008). «Степень соответствия моделей социальных сетей». Журнал Американской статистической ассоциации . 103 (481): 248–258. CiteSeerX  10.1.1.206.396 . DOI : 10.1198 / 016214507000000446 .
• Хантер, Д. Р.; Handcock, MS (2006). «Вывод в криволинейных экспоненциальных моделях семейства для сетей». Журнал вычислительной и графической статистики . 15 (3): 565–583. CiteSeerX  10.1.1.205.9670 . DOI : 10.1198 / 106186006X133069 .
• Хантер, DR; Handcock, MS; Окурки, CT; Гудро, С. М.; Моррис, М. (2008). «ergm: пакет для подгонки, моделирования и диагностики моделей экспоненциального семейства для сетей» . Журнал статистического программного обеспечения . 24 (3): 1-29. DOI : 10,18637 / jss.v024.i03 .
• Джин, IH; Лян, Ф. (2012). «Подгонка моделей социальных сетей с использованием алгоритма MCMC с варьирующейся стохастической аппроксимацией усечения». Журнал вычислительной и графической статистики . 22 (4): 927–952. DOI : 10.1080 / 10618600.2012.680851 .
• Koskinen, JH; Робинс, Г.Л .; Паттисон, ЧП (2010). «Анализ моделей экспоненциального случайного графа (p-star) с отсутствующими данными с использованием байесовского увеличения данных». Статистическая методология . 7 (3): 366–384. DOI : 10.1016 / j.stamet.2009.09.007 .
• Morris, M .; Handcock, MS; Хантер, Д.Р. (2008). "Спецификация моделей случайных графов экспоненциального семейства: термины и вычислительные аспекты" . Журнал статистического программного обеспечения . 24 (4). DOI : 10,18637 / jss.v024.i04 .
• Ринальдо, А .; Fienberg, SE; Чжоу, Ю. (2009). «О геометрии дискретных экспоненциальных случайных семейств с применением к моделям экспоненциальных случайных графов». Электронный статистический журнал . 3 : 446–484. arXiv : 0901.0026 . DOI : 10.1214 / 08-EJS350 .
• Робинс, G .; 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). «Локальная зависимость в моделях случайных графов: характеристика, свойства и статистический вывод» . Журнал Королевского статистического общества, Series 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 .
• Снайдерс, ТАБ; Паттисон, ЧП; Робинс, Г.Л .; Handcock, MS (2006). «Новые спецификации для экспоненциальных моделей случайных графов». Социологическая методология . 36 : 99–153. CiteSeerX  10.1.1.62.7975 . DOI : 10.1111 / j.1467-9531.2006.00176.x .
• Штраус, Д; Икеда, М. (1990). «Оценка псевдодостоверности социальных сетей» . Журнал Американской статистической ассоциации . 5 (409): 204–212. DOI : 10.2307 / 2289546 . JSTOR  2289546 .
• ван Дуйн, Массачусетс; Снайдерс, ТАБ; Zijlstra, BH (2004). «p2: модель случайных эффектов с ковариатами для ориентированных графов». Statistica Neerlandica . 58 (2): 234–254. DOI : 10,1046 / j.0039-0402.2003.00258.x .
• ван Дуйн, Массачусетс; Gile, KJ ; Handcock, MS (2009). «Основа для сравнения максимальной псевдо-правдоподобия и оценки максимального правдоподобия моделей экспоненциального семейства случайных графов» . Социальные сети . 31 (1): 52–62. DOI : 10.1016 / j.socnet.2008.10.003 . PMC  3500576 . PMID  23170041 .