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

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

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

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

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

Алгоритм

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

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

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

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

Еще одно следствие петель и множественных ребер состоит в том, что не все возможные сети генерируются с одинаковой вероятностью. В общем, все возможные реализации могут быть получены путем перестановки заглушек всех вершин любым возможным способом. Количество перестановок заглушек узла ${\displaystyle i}$ является ${\displaystyle k_{i}!}$, поэтому количество реализаций последовательности степеней равно ${\displaystyle N\{k_{i}\}=\Pi _{i}k_{i}!}$. Это означало бы, что каждая реализация происходит с одинаковой вероятностью. Однако петли и мультиребра могут изменить количество реализаций, поскольку перестановка собственных ребер может привести к неизменной реализации. Учитывая, что количество петель и мультизвеньев обращается в нуль как ${\displaystyle N\rightarrow \infty }$, вариация вероятностей различных реализаций будет небольшой, но присутствует.^[2]

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

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

Заглушка узла ${\displaystyle i}$ может быть подключен к ${\displaystyle 2m-1}$ другие заглушки (есть ${\displaystyle 2m}$ заглушки вообще, и мы должны исключить тот, который сейчас наблюдаем). Вершина ${\displaystyle j}$ имеет ${\displaystyle k_{j}}$ заглушки к какому узлу ${\displaystyle i}$ могут быть связаны с одинаковой вероятностью (из-за равномерного распределения). Вероятность заглушки узла ${\displaystyle i}$ будучи подключенным к одному из этих ${\displaystyle k_{j}}$ заглушки ${\displaystyle {\frac {k_{j}}{2m-1}}}$. Поскольку узел ${\displaystyle i}$ имеет ${\displaystyle k_{i}}$ заглушки, вероятность ${\displaystyle i}$ будучи связан с ${\displaystyle j}$ является ${\displaystyle {\frac {k_{i}k_{j}}{2m-1}}}$ (${\displaystyle {\frac {k_{i}k_{j}}{2m}}}$ для достаточно большого ${\displaystyle m}$). Вероятность возникновения собственных ребер нельзя описать этой формулой, но поскольку плотность собственных ребер стремится к нулю как ${\displaystyle N\rightarrow \infty }$, это обычно дает хорошую оценку.^[2]

Учитывая модель конфигурации с распределением степеней ${\displaystyle p_{k}}$, вероятность случайно выбранного узла ${\displaystyle i}$ имеющий степень ${\displaystyle k}$ является ${\displaystyle p_{k}}$. Но если мы выберем одну из вершин, в которую мы можем попасть, следуя за одним из ребер i, вероятность того, что мы получим степень k, равна ${\displaystyle {\frac {k}{2m}}*np_{k}={\frac {kp_{k}}{<k>}}}$ . (Вероятность достижения узла со степенью k равна ${\displaystyle {\frac {k}{2m}}}$, и здесь ${\displaystyle np_{k}}$ таких узлов.) Эта доля зависит от ${\displaystyle kp_{k}}$ в отличие от степени типичного узла с ${\displaystyle p_{k}}$. Таким образом, ожидается, что сосед типичного узла будет иметь более высокую степень, чем сам типичный узел. Эта особенность модели конфигурации хорошо описывает феномен «у моих друзей больше друзей, чем у меня».

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

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

${\displaystyle C_{g}=\sum _{k_{i},k_{j}=0}^{\infty }q_{k}(i)q_{k}(j)*{\frac {k_{i}k_{j}}{2m}}}$,

куда ${\displaystyle q_{k}(i),q_{k}(j)}$ обозначает вероятностные распределения вершин ${\displaystyle i}$ и ${\displaystyle j}$ имея ${\displaystyle k_{i},k_{j}}$ ребра соответственно.

${\displaystyle C_{g}={\frac {1}{2m}}\left[\sum _{k=0}^{\infty }kq_{k}\right]^{2}}$

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

${\displaystyle \thickapprox {\frac {1}{2m}}*constant\thickapprox {\frac {1}{N}}*constant}$, куда ${\displaystyle N}$ - количество вершин, а размер константы зависит от ${\displaystyle p_{k}}$.^[2] Таким образом, глобальный коэффициент кластеризации ${\displaystyle C_{g}}$становится малым при большом пределе n.

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

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

${\displaystyle \langle k^{2}\rangle -2\langle k\rangle >0,}$

куда ${\displaystyle \langle k\rangle }$ и ${\displaystyle \langle k^{2}\rangle }$ первый и второй моменты распределение степеней. Это означает, что критический порог зависит исключительно от величин, которые однозначно определяются распределением степеней ${\displaystyle p_{k}}$.

Модель конфигурации генерирует локально древовидные сети, что означает, что любое локальное окружение в такой сети принимает форму дерева. Точнее, если вы начинаете с любого узла сети и формируете набор всех удаленных узлов ${\displaystyle d}$ или меньше от этого начального узла, множество с вероятностью, стремящейся к 1 при n → ∞, примет форму дерева.^[3] В древовидных структурах количество вторых соседей, усредненное по всей сети, ${\displaystyle c_{2}}$, является: ${\displaystyle c_{2}=\langle k^{2}\rangle -\langle k\rangle .}$

Тогда в целом среднее число на расстоянии ${\displaystyle d}$ можно записать как:

${\displaystyle c_{d}=({\frac {c_{2}}{c_{1}}})^{d-1}c_{1}.}$

Это означает, что если соотношение ${\displaystyle {\frac {c_{2}}{c_{1}}}}$ больше единицы, то в сети может быть гигантский компонент. Это известно как критерий Моллоя-Рида.^[4] Интуиция, лежащая в основе этого критерия, заключается в том, что если гигантский компонент существует, то средняя степень случайно выбранной вершины ${\displaystyle i}$ в компоненте связности должно быть не менее 2. Критерий Моллоя-Рида также может быть выражен как: ${\displaystyle \sum _{i}k_{i}(k_{i}-2)>0,}$ что означает, что, хотя размер GC может зависеть от ${\displaystyle p_{0}}$и ${\displaystyle p_{2}}$количество узлов степени 0 и 2 не вносит вклада в существование гигантской компоненты.^[3]

Диаметр

Модель конфигурации может предполагать любое распределение степеней и показывает эффект маленького мира, поскольку в первом порядке диаметр модели конфигурации просто ${\displaystyle d={\frac {ln(N)}{ln(c_{2}/c_{1})}}}$.^[5]

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

Как общее количество вершин ${\displaystyle N}$ стремится к бесконечности, вероятность найти две гигантские компоненты равна нулю. Это означает, что в разреженном режиме модель состоит из одного гигантского компонента (если есть) и нескольких связанных компонентов конечного размера. Размеры соединяемых компонентов характеризуются их распределением по размерам. ${\displaystyle w_{n}}$- вероятность того, что случайно выбранная вершина принадлежит компоненту связности размера ${\displaystyle n.}$ Существует соответствие между распределением степеней ${\displaystyle p_{k}}$ и распределение по размерам ${\displaystyle w_{n}.}$ Когда общее количество вершин стремится к бесконечности, ${\displaystyle N\rightarrow \infty }$, имеет место следующее соотношение:^[6]

${\displaystyle w_{n}={\begin{cases}{\frac {\langle k\rangle }{n-1}}u_{1}^{*n}(n-2),&n>1,\\p_{0}&n=1,\end{cases}}}$

куда ${\displaystyle u_{1}(k):={\frac {k+1}{\langle k\rangle }}p_{k+1},}$ и ${\displaystyle u_{1}^{*n}}$ обозначает ${\displaystyle n}$-складывать мощность свертки. Более того, явные асимптоты для ${\displaystyle w_{n}}$ известны когда ${\displaystyle n\gg 1}$и ${\displaystyle |\langle k^{2}\rangle -2\langle k\rangle |}$близка к нулю.^[6] Аналитические выражения для этих асимптот зависят от конечности моментов ${\displaystyle p_{k},}$ показатель хвоста распределения степеней ${\displaystyle \beta }$(когда ${\displaystyle p_{k}}$имеет тяжелый хвост), а также знак критерия Моллоя-Рида. В следующей таблице приведены эти отношения (константы указаны в^[6]).

Моменты ${\displaystyle p_{k}}$	Хвост ${\displaystyle p_{k}}$	${\displaystyle {\text{sign}}(\langle k^{2}\rangle -2\langle k\rangle )}$	${\displaystyle w_{n},\;n\gg 1,\;\alpha =\beta -2}$
${\displaystyle \langle k^{3}\rangle <\infty }$	легкий хвост	-1 или 1	${\displaystyle C_{1}e^{-C_{2}n}n^{-3/2}}$
		0	${\displaystyle C_{1}n^{-3/2}}$
	тяжелый хвост, ${\displaystyle \beta >4}$	-1	${\displaystyle C_{3}n^{-\alpha -1}}$
		0	${\displaystyle C_{1}n^{-3/2}}$
		1	${\displaystyle C_{1}e^{-C_{2}n}n^{-3/2}}$
${\displaystyle \langle k^{3}\rangle =\infty ,}$ ${\displaystyle \langle k^{2}\rangle <\infty ,}$	тяжелый хвост, ${\displaystyle \beta =4}$	-1	${\displaystyle C_{3}n^{-\alpha -1}}$
		0	${\displaystyle C_{1}'{\frac {n^{-3/2}}{\sqrt {\log n}}}}$
		1	${\displaystyle C_{1}'{\frac {n^{-3/2}}{\sqrt {\log n}}}e^{-C_{2}'{\frac {n}{\log n}}}}$
	тяжелый хвост, ${\displaystyle 3<\beta <4}$	-1	${\displaystyle C_{3}n^{-\alpha -1}}$
		0	${\displaystyle C_{4}n^{-{\frac {1}{\alpha }}-1}}$
		1	${\displaystyle C_{5}e^{-C_{6}n}n^{-3/2}}$
${\displaystyle \langle k^{2}\rangle =\infty ,}$ ${\displaystyle \langle k\rangle <\infty ,}$	тяжелый хвост, ${\displaystyle \beta =3}$	1	${\displaystyle C_{7}e^{-C_{8}-C_{9}n^{\frac {2}{\pi }}}n^{{\frac {1}{\pi }}-2}}$
	тяжелый хвост, ${\displaystyle 2<\beta <3}$	1	${\displaystyle C_{10}e^{-C_{11}n}n^{-3/2}}$

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

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

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

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

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

${\displaystyle Q={\frac {1}{2L}}\sum _{i\neq j}{\Bigl (}A_{ij}-{\frac {k_{i}k_{j}}{2L}}{\Bigr )}\delta (C_{i},C_{j})}$^[10]

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

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

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

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

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

1. Сетевые науки Альберта-Ласло Барабаши.
2. Ньюман, Марк (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. Кривень, 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.