Модель конфигурации - Configuration model - Wikipedia

Рисунок 1. Последовательность степеней и различные реализации сети в модели конфигурации.[1]

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

Обоснование модели

В модели конфигурации степень каждой вершины предопределена заранее, а не имеет распределение вероятностей, из которого выбирается данная степень.[2] В отличие от Модель Эрдеша-Реньи, последовательность степеней модели конфигурации не ограничивается Распределение Пуассона, модель позволяет пользователю задавать сети любую желаемую степень распределения.

Алгоритм

Следующий алгоритм описывает создание модели:

  1. Возьмем последовательность степеней, т.е. е. присвоить степень в каждую вершину. Степени вершин представлены в виде полузвеньев или шлейфов. Сумма заглушек должна быть четной, чтобы можно было построить граф (). Последовательность степеней может быть получена из теоретического распределения или может представлять реальную сеть (определенную из матрица смежности сети).
  2. Равномерно выберите два стержня наугад и соедините их так, чтобы получился край. Выберите другую пару из оставшихся заглушки и соедините их. Продолжайте, пока у вас не закончатся заглушки. Результатом является сеть с заранее определенной последовательностью степеней. Реализация сети меняется в зависимости от порядка, в котором выбираются заглушки, они могут включать циклы (b), петли (c) или множественные связи (d) (рисунок 1). Тем не менее, ожидаемое количество петель а мультисвязь обнуляется в N → ∞ предел.[1]

Петли, множественные ребра и последствия

Описанный выше алгоритм с одинаковой вероятностью сопоставляет любые заглушки. Равномерное распределение соответствия - важное свойство с точки зрения расчета других характеристик генерируемых сетей. Процесс создания сети не исключает случай создания петли или многоканального соединения. Если бы мы спроектировали процесс, в котором петли и множественные ребра недопустимы, соответствие заглушек не будет следовать равномерному распределению. Тем не менее, среднее количество петель и нескольких ребер является постоянным для больших сетей, поэтому плотность петель и многоканальных связей стремится к нулю при [2] (подробности см. в цитируемой книге).

Еще одно следствие петель и множественных ребер состоит в том, что не все возможные сети генерируются с одинаковой вероятностью. В общем, все возможные реализации могут быть получены путем перестановки заглушек всех вершин любым возможным способом. Количество перестановок заглушек узла является , поэтому количество реализаций последовательности степеней равно . Это означало бы, что каждая реализация происходит с одинаковой вероятностью. Однако петли и мультиребра могут изменить количество реализаций, поскольку перестановка собственных ребер может привести к неизменной реализации. Учитывая, что количество петель и мультизвеньев обращается в нуль как , вариация вероятностей различных реализаций будет небольшой, но присутствует.[2]

Характеристики

Вероятность края

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

Учитывая модель конфигурации с распределением степеней , вероятность случайно выбранного узла имеющий степень является . Но если мы выберем одну из вершин, в которую мы можем попасть, следуя за одним из ребер i, вероятность того, что мы получим степень k, равна . (Вероятность достижения узла со степенью k равна , и здесь таких узлов.) Эта доля зависит от в отличие от степени типичного узла с . Таким образом, ожидается, что сосед типичного узла будет иметь более высокую степень, чем сам типичный узел. Эта особенность модели конфигурации хорошо описывает феномен «у моих друзей больше друзей, чем у меня».

Коэффициент кластеризации

Глобальный коэффициент кластеризации (средняя вероятность того, что соседи узла связаны) вычисляется следующим образом:

,

куда обозначает вероятностные распределения вершин и имея ребра соответственно.

После преобразования приведенного выше уравнения мы получаем приблизительно

, куда - количество вершин, а размер константы зависит от .[2] Таким образом, глобальный коэффициент кластеризации становится малым при большом пределе n.

Гигантский компонент

В модели конфигурации гигантский компонент (GC) существует, если

куда и первый и второй моменты распределение степеней. Это означает, что критический порог зависит исключительно от величин, которые однозначно определяются распределением степеней .

Модель конфигурации генерирует локально древовидные сети, что означает, что любое локальное окружение в такой сети принимает форму дерева. Точнее, если вы начинаете с любого узла сети и формируете набор всех удаленных узлов или меньше от этого начального узла, множество с вероятностью, стремящейся к 1 при n → ∞, примет форму дерева.[3] В древовидных структурах количество вторых соседей, усредненное по всей сети, , является:

Тогда в целом среднее число на расстоянии можно записать как:

Это означает, что если соотношение больше единицы, то в сети может быть гигантский компонент. Это известно как критерий Моллоя-Рида.[4] Интуиция, лежащая в основе этого критерия, заключается в том, что если гигантский компонент существует, то средняя степень случайно выбранной вершины в компоненте связности должно быть не менее 2. Критерий Моллоя-Рида также может быть выражен как: что означает, что, хотя размер GC может зависеть от и количество узлов степени 0 и 2 не вносит вклада в существование гигантской компоненты.[3]

Диаметр

Модель конфигурации может предполагать любое распределение степеней и показывает эффект маленького мира, поскольку в первом порядке диаметр модели конфигурации просто .[5]

Компоненты конечного размера

Как общее количество вершин стремится к бесконечности, вероятность найти две гигантские компоненты равна нулю. Это означает, что в разреженном режиме модель состоит из одного гигантского компонента (если есть) и нескольких связанных компонентов конечного размера. Размеры соединяемых компонентов характеризуются их распределением по размерам. - вероятность того, что случайно выбранная вершина принадлежит компоненту связности размера Существует соответствие между распределением степеней и распределение по размерам Когда общее количество вершин стремится к бесконечности, , имеет место следующее соотношение:[6]

куда и обозначает -складывать мощность свертки. Более того, явные асимптоты для известны когда и близка к нулю.[6] Аналитические выражения для этих асимптот зависят от конечности моментов показатель хвоста распределения степеней (когда имеет тяжелый хвост), а также знак критерия Моллоя-Рида. В следующей таблице приведены эти отношения (константы указаны в[6]).

Моменты Хвост
легкий хвост-1 или 1
0
тяжелый хвост, -1
0
1

тяжелый хвост, -1
0
1
тяжелый хвост, -1
0
1

тяжелый хвост, 1
тяжелый хвост, 1

Моделирование

Сравнение с реальными сетями

Три основных свойства сложные сети неоднородное распределение степеней, короткая средняя длина пути и высокая кластеризация.[1][7][8] Имея возможность определять любую произвольную последовательность степеней, первое условие может быть выполнено по дизайну, но, как показано выше, глобальный коэффициент кластеризации является обратной функцией размера сети, поэтому для сетей с большой конфигурацией кластеризация имеет тенденцию быть небольшой. Эта особенность базовой модели противоречит известным свойствам эмпирических сетей, но расширения модели могут решить эту проблему (см. [9]).

Применение: расчет модульности

Модель конфигурации применяется в качестве эталона при расчете сети. модульность. Модульность измеряет степень разделения сети на модули. Он рассчитывается следующим образом:

[10]

в которой матрица смежности сети сравнивается с вероятностью наличия края между узлами и (в зависимости от степени) в конфигурации модели (см. стр. модульность подробнее).

Модель направленной конфигурации

В DCM (модель направленной конфигурации)[11] каждому узлу дано несколько полуребер, называемых хвостами и головами. Затем хвосты и головы равномерно сопоставляются случайным образом, чтобы сформировать направленные края. Размер гигантского компонента,[11][12] типичное расстояние,[13] и диаметр[14] DCM изучены математически. Также было проведено обширное исследование случайные прогулки в DCM.[15][16][17]Некоторые сложные сети реального мира были смоделированы DCM, например нейронные сети,[18] финансы[19] и социальные сети.[20]

Модель направленной конфигурации

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

  1. ^ а б c Сетевые науки Альберта-Ласло Барабаши.
  2. ^ а б c d е Ньюман, Марк (25 марта 2010 г.). Сети: Введение - Оксфордская стипендия. Издательство Оксфордского университета. Дои:10.1093 / acprof: oso / 9780199206650.001.0001. ISBN  9780191594175.
  3. ^ а б Ньюман, Марк (2018-10-18). Сети. 1. Издательство Оксфордского университета. Дои:10.1093 / осо / 9780198805090.001.0001. ISBN  978-0-19-880509-0.
  4. ^ Моллой, Майкл; Рид, Брюс (1995-03-01). «Критическая точка для случайных графов с заданной последовательностью степеней». Случайные структуры и алгоритмы. 6 (2–3): 161–180. CiteSeerX  10.1.1.24.6195. Дои:10.1002 / RSA.3240060204. ISSN  1098-2418.
  5. ^ Чанг, Фань; Лу Линьюань (2002-12-10). «Средние расстояния в случайных графиках с заданными ожидаемыми градусами». Труды Национальной академии наук. 99 (25): 15879–15882. Bibcode:2002PNAS ... 9915879C. Дои:10.1073 / pnas.252631999. ISSN  0027-8424. ЧВК  138532. PMID  12466502.
  6. ^ а б c Кривень, I (2017). «Общее выражение для распределения компонентов по размерам в сетях с бесконечной конфигурацией». Физический обзор E. 95 (5): 052303. arXiv:1703.05413. Bibcode:2017PhRvE..95e2303K. Дои:10.1103 / PhysRevE.95.052303. HDL:11245.1 / fa1b270b-61a5-4f20-b496-ddf446fdfe80. PMID  28618550. S2CID  8421307.
  7. ^ Барабаши, Альберт-Ласло; Альберт, Река (1999-10-15). «Появление масштабирования в случайных сетях». Наука. 286 (5439): 509–512. arXiv:cond-mat / 9910332. Bibcode:1999Научный ... 286..509Б. Дои:10.1126 / science.286.5439.509. ISSN  0036-8075. PMID  10521342. S2CID  524106.
  8. ^ Уоттс, Дункан Дж .; Строгац, Стивен Х. (1998). «Коллективная динамика сетей« маленького мира »». Природа. 393 (6684): 440–442. Bibcode:1998 Натур.393..440Вт. Дои:10.1038/30918. ISSN  1476-4687. PMID  9623998. S2CID  4429113.
  9. ^ Ньюман, М. Э. Дж. (2009). «Случайные графы с кластеризацией». Письма с физическими проверками. 103 (5): 058701. arXiv:0903.4009. Bibcode:2009PhRvL.103e8701N. Дои:10.1103 / Physrevlett.103.058701. PMID  19792540. S2CID  28214709.
  10. ^ Ньюман, М. Э. Дж. (2004). «Поиск и оценка структуры сообщества в сетях». Физический обзор E. 69 (2): 026113. arXiv:cond-mat / 0308217. Bibcode:2004PhRvE..69b6113N. Дои:10.1103 / Physreve.69.026113. PMID  14995526. S2CID  197314.
  11. ^ а б КУПЕР, КОЛИН; ФРИЗ, АЛАН (май 2004 г.). «Размер наибольшей сильносвязной компоненты случайного орграфа с заданной порядковой последовательностью». Комбинаторика, теория вероятностей и вычисления. 13 (3): 319–337. Дои:10.1017 / S096354830400611X. ISSN  1469-2163.
  12. ^ Цай, Син Ши; Перарнау, Гиллем (10 апреля 2020 г.). «Пересмотр гигантского компонента модели направленной конфигурации». arXiv:2004.04998 [math.PR ].
  13. ^ ван дер Хорн, Пим; Ольвера-Кравиото, Мариана (июнь 2018 г.). «Типовые расстояния в модели направленной конфигурации». Анналы прикладной теории вероятностей. 28 (3): 1739–1792. arXiv:1511.04553. Дои:10.1214 / 17-AAP1342. S2CID  13683470.
  14. ^ Цай, Син Ши; Перарнау, Гиллем (10 марта 2020 г.). «Диаметр модели направленной конфигурации». arXiv:2003.04965 [math.PR ].
  15. ^ Борденаве, Чарльз; Капуто, Пьетро; Салез, Джастин (1 апреля 2018 г.). «Случайное блуждание по редким случайным орграфам». Теория вероятностей и смежные области. 170 (3): 933–960. arXiv:1508.06600. Дои:10.1007 / s00440-017-0796-7. ISSN  1432-2064. S2CID  55211047.
  16. ^ Капуто, Пьетро; Кваттропани, Маттео (1 декабря 2020 г.). «Стационарное распределение и время покрытия разреженных направленных моделей конфигурации». Теория вероятностей и смежные области. 178 (3): 1011–1066. Дои:10.1007 / s00440-020-00995-6. ISSN  1432-2064. S2CID  202565916.
  17. ^ Цай, Син Ши; Перарнау, Гиллем (14 октября 2020 г.). «Минимальные стационарные значения разреженных случайных ориентированных графов». arXiv:2010.07246 [math.PR ].
  18. ^ Амини, Хамед (1 ноября 2010 г.). "Перколяция начальной загрузки в живых нейронных сетях". Журнал статистической физики. 141 (3): 459–475. arXiv:0910.0627. Bibcode:2010JSP ... 141..459A. Дои:10.1007 / s10955-010-0056-z. ISSN  1572-9613. S2CID  7601022.
  19. ^ Амини, Хамед; Минка, Андреа (2013). «Математическое моделирование системного риска». Достижения в области сетевого анализа и его приложений. Математика в промышленности. Springer. 18: 3–26. Дои:10.1007/978-3-642-30904-5_1. ISBN  978-3-642-30903-8. S2CID  166867930.
  20. ^ Ли, Хуэй (июль 2018 г.). «Уязвимость к атакам социальных сетей в Интернете». 2018 37-я Китайская конференция по контролю (CCC): 1051–1056. Дои:10.23919 / ChiCC.2018.8482277. ISBN  978-988-15639-5-8. S2CID  52933445.