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

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

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

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

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

Алгоритм

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

1. Возьмите последовательность степеней, т.е. присвойте степень $k_{i}$к каждой вершине. Степени вершин представлены в виде полузвеньев или заглушек. Сумма заглушек должна быть четной, чтобы можно было построить граф ( $\sum k_{i}=2m$). Последовательность степеней может быть получена из теоретического распределения или может представлять собой реальную сеть (определяемую из матрицы смежности сети).
2. Выберите наугад два заглушки и соедините их, образуя край. Выберите другую пару из оставшихся $2m-2$ заглушки и соедините их. Продолжайте, пока не закончатся заглушки. В результате получается сеть с заранее определенной последовательностью степеней. Реализация сети меняется в зависимости от порядка выбора заглушек: они могут включать циклы (б), самоциклы (в) или многозвенья (г) (рис. 1).

Самоциклы, многоребра и последствия

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

Ожидаемое общее количество многоканальных каналов в сети модели конфигурации будет следующим:

${\frac {1}{2}}{\Big [}{\frac {\langle {k^{2}}\rangle }{\langle k\rangle }}-1{\Big ]}^{2}$

где $\langle {k^{n}}\rangle$ – n-й момент распределения степеней. Следовательно, среднее количество петель и многозвеньев является константой для некоторых крупных сетей, а плотность петель и многозвеньев, то есть количество на узел, стремится к нулю при $N\rightarrow \infty$ пока $\langle {k^{2}}\rangle$ является постоянным и конечным. Для некоторых степенных распределений степеней, где второй момент расходится, плотность многозвеньев может не исчезать или исчезать медленнее, чем ${N}^{-1}$.

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

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

Краевая вероятность

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

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

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

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

$C_{g}=\sum _{k_{i},k_{j}=1}^{\infty }q_{k_{i}}q_{k_{j}}{\frac {(k_{i}-1)(k_{j}-1)}{2m}},$

где $q_{k}$ обозначает вероятность того, что случайное ребро достигнет степени $k$ вершина, и факторы формы" $k_{i}-1$" скорее, чем " $k_{i}$" появляются потому, что одна заглушка была учтена тем, что это соседи общей вершины. Оценка вышеприведенного результата дает

$C_{g}={\frac {1}{2m}}\left[\sum _{k=0}^{\infty }(k-1)q_{k}\right]^{2}.$

С использованием $q_{k}=kp_{k}/\langle k\rangle$ и $2m=N\langle k\rangle$, с $p_{k}$ обозначая распределение степеней, $\langle k\rangle$ обозначающий среднюю степень, и $N$ обозначая количество вершин, приведенное выше становится

$C_{g}={\frac {1}{N\langle k\rangle ^{3}}}\left[\sum _{k=1}^{\infty }(k-1)kP(k)\right]^{2}={\frac {\left(\langle k^{2}\rangle -\langle k\rangle \right)^{2}}{N\langle k\rangle ^{3}}},$

с $\langle k^{2}\rangle$ обозначающий второй момент распределения степеней. Предполагая, что $\langle k^{2}\rangle$ и $\langle k\rangle$ постоянны, приведенное выше ведет себя как

$C_{g}\sim {\frac {\mathrm {const} }{N}},$

где константа зависит от $p_{k}$. Таким образом, коэффициент кластеризации $C_{g}$ становится маленьким в $N\gg 1$ предел.

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

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

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

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

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

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

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

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

Диаметр

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

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

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

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

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

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

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

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

Тремя общими свойствами сложных сетей являются неоднородное распределение степеней, короткая средняя длина пути и высокая кластеризация. Имея возможность определять любую произвольную последовательность степеней, первое условие может быть удовлетворено замыслом, но, как показано выше, глобальный коэффициент кластеризации является обратной функцией размера сети, поэтому для сетей с большой конфигурацией кластеризация имеет тенденцию быть небольшой. Эта особенность базовой модели противоречит известным свойствам эмпирических сетей, но расширения модели могут решить эту проблему (см. ). Все сети, созданные этой моделью, являются локально древовидными при условии, что среднее значение распределения избыточной степени либо постоянно, либо растет медленнее, чем квадратный корень из числа связей. ${\sqrt {m}}$. Другими словами, эта модель предотвращает образование подструктур, таких как петли, в пределе большого размера. Исчезновение коэффициента кластеризации является частным случаем этого более общего результата. Хотя свойство древовидности делает модель не очень реалистичной, очень много вычислений, таких как методы производящей функции . благодаря этой особенности для модели конфигурации возможно

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

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

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

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

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

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

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