Паттерны смешивания

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

Конкретные характеристики узлов, вовлечённых в процесс образования связей между парами, формируют паттерны смешивания сети. Например, в сети сексуальных отношений, вероятно, обнаружится преобладание связей мужчина-женщина, тогда как в сети дружбы могут преобладать связи мужчина-мужчина и женщина-женщина. Изучение различных наборов характеристик узлов, таким образом, может выявить сообщества или другие структурные свойства сети. В целом, есть два типа методов для использования этих свойств. Один из них основан на аналитических вычислениях с помощью производящих функций. Другой из них — численный и основан на симуляциях по методу Монте-Карло для генерации графов.[1]

При изучении паттернов смешивания в сетях М. Ньюман (M.E.J. Newman) начинает с классификации характеристик узлов на две категории. В то время как число характеристик узлов реального мира виртуально неограниченно, их можно разделить на два типа: дискретные и скалярные/топологические. В последующих разделах определены различия между этими категориями и приведены примеры для каждой из них. Для каждой категории Ньюманом введены и кратко описаны модели сетей с ассортативным смешиванием.

Дискретные характеристики узла — категориальные, номинальные или исчислительные и зачастую качественные. Например, раса, пол и сексуальная ориентация — это часто исследуемые дискретные характеристики.

Для измерения смешивания в сети на основе дискретных характеристик Ньюман[1] определяет количество ${\displaystyle e_{ij}}$ как долю рёбер в сети, которые соединяют узлы типа ${\displaystyle i}$ с типом ${\displaystyle j}$ (см. Рис. 1)^[где?]. В ненаправленной сети это количество симметрично относительно своих индексов ${\displaystyle e_{ij}=e_{ji}}$, тогда как в направленной сети оно может быть асимметричным. Оно удовлетворяет правилам суммирования:

${\displaystyle \sum _{ij}{e_{ij}=1},\quad \sum _{j}{e_{ij}=a_{i}},\quad \sum _{i}{e_{ij}=b_{j}}~,}$

где ${\displaystyle a_{i}}$ и ${\displaystyle b_{i}}$ — доли каждого типа конца ребра, присоединённого к узлам типа ${\displaystyle i}$.

В ненаправленных графах, где нет физического различия между концами связи, т.е. концы рёбер все одного типа, ${\displaystyle a_{i}=b_{i}}$.

Тогда коэффициент ассортативности — это мера силы сходства или несходства между двумя узлами на множестве дискретных характеристик, которая может быть определена как:

${\displaystyle r={\frac {\sum _{i}{e_{ii}}-\sum _{i}{a_{i}b_{i}}}{1-\sum _{i}{a_{i}b_{i}}}}}$

с

${\displaystyle r_{min}=-{\frac {\sum _{i}{a_{i}b_{i}}}{1-\sum _{i}{a_{i}b_{i}}}}~.}$

В этой формуле ${\displaystyle r=0}$, если нет ассортативного смешивания, поскольку в этом случае ${\displaystyle e_{ij}=a_{i}b_{j}}$, и ${\displaystyle r=1}$, если сеть полностью ассортативна. Если сеть полностью дизассортативна, т.е. каждая связь соединяет два узла разных типов, тогда ${\displaystyle r=r_{min}}$, который, в целом, принадлежит диапазону ${\displaystyle -1\leq r<0}$. Этот диапазон для ${\displaystyle r_{min}}$ говорит о том, что полностью дизассортативная сеть в общем случае ближе к сети со случайным смешиванием, чем полностью ассортативная. Когда есть несколько различных типов узлов, тогда случайное смешивание в большинстве случаев будет объединять несхожие узлы, в результате чего такая сеть выглядит преимущественно дизассортативной. Следовательно, закономерно, что значение ${\displaystyle r=0}$ для случайной сети должно быть ближе к значению для полностью дизассортативной сети, чем для полностью ассортативной сети.

Метод производящих функций основан на идее каждый раз вычисления подходящей производящей функции для интересующих распределений и позволяет извлекать данные, относящиеся к структуре сети путём их дифференциации. Предполагая, что распределение степеней ${\displaystyle p_{k}^{(i)}}$ для узлов типа ${\displaystyle i}$ и значение матрицы ${\displaystyle e_{ij}}$ (и, следовательно, значения ${\displaystyle a_{i}}$ и ${\displaystyle b_{i}}$) известны. Из ансамбля графов с указанными ${\displaystyle p_{k}^{(i)}}$ и ${\displaystyle e_{ij}}$ получаются коллективные (макроскопические) характеристики сети. В целом, производящие функции для ${\displaystyle p_{k}^{(i)}}$ и их первый момент задаются как

${\displaystyle G_{0}^{(i)}(x_{1},...,x_{n})=\sum _{k}p_{k}^{(i)}x^{k}}$

и

${\displaystyle G_{1}^{(i)}={\frac {1}{z_{i}}}{\frac {dG_{0}^{(i)}}{dx}}{\Bigg |}_{x=1}~,}$

где:

${\displaystyle x_{i}={\frac {\sum _{j}e_{ij}x_{j}}{\sum _{j}e_{ij}}}}$ – узел типа ${\displaystyle i}$ (${\displaystyle r_{i}}$ в числе);

${\displaystyle z_{i}}$ – средняя степень узлов этого типа.

Отдельный интерес представляют нижеследующие распределения.

Распределение общего числа узлов, достижимых при следовании по ребру, входящему в узел типа ${\displaystyle i}$, имеет производящую функцию ${\displaystyle H_{1}^{(i)}(x)=xG_{1}^{(i)}[H_{1}^{(1)}(x),...,H_{1}^{(n)}(x)]}$. Аналогично, распределение числа узлов, достижимых из случайно выбранного узла типа ${\displaystyle i}$, имеет производящую функцию ${\displaystyle H_{0}^{(i)}(x)=xG_{0}^{(i)}[H_{1}^{(1)}(x),...,H_{1}^{(n)}(x)]}$. Из этого можно получить некоторые характеристики сети. Среднее число ${\displaystyle s_{i}}$ узлов, достижимых из узла типа ${\displaystyle i}$ равно

${\displaystyle s_{i}={\frac {dH_{0}^{(i)}}{dx}}{\Bigg |}_{x=1}=1+G_{0}^{(i)'}(1){\frac {\sum _{j}e_{ij}H_{1}^{(i)'}(1)}{\sum _{j}e_{ij}}}~.}$

Далее, если ${\displaystyle u_{i}}$ – это вероятность для узла типа ${\displaystyle i}$ (отобранный путём следования случайно выбранной связи в графе) не принадлежать гигантскому кластеру (giant cluster), тогда общая доля ${\displaystyle S}$ узлов, составляющих этот кластер, задаётся как

${\displaystyle S=1-\sum _{i}{\frac {a_{i}}{z_{i}}}G_{0}^{(i)}(u_{1},...,u_{n})~.}$

Численные вычисления на основе метода Монте-Карло, по-видимому, находятся в согласии с аналитическими результатами, полученными по формулам, описанным выше.

Скалярные характеристики узла — это численные характеристики. Они могут быть непрерывными или дискретными порядковыми переменными, как например количеством (count). Возраст, вероятно, самый простой пример, хотя интеллект и сырьевой доход — другие очевидные возможные примеры. Некоторые топологические особенности сети также могут быть использованы для исследования смешивания на основе скалярных свойств. В частности, степень узла — зачастую очень важная характеристика в паттернах смешивания в сетях.[2] Очень полезны топологические скалярные особенности, поскольку, в отличие от других показателей, они всегда доступны. Иногда они используются как приблизительный показатель реальной «социабельности» (sociability, склонность устанавливать социальные связи).[1]

Для измерения ассортативности скалярных переменных, аналогично дискретному случаю (см. выше) можно определить коэффициент ассортативности. Его можно измерить с помощью стандартной корреляции Пирсона, как показал Ньюман.[1] На Рис. 2^[где?], например, расчёт коэффициента корреляции Пирсона даёт r = 0.574. Это обозначает довольно сильную ассоциацию между возрастом мужей и жён на момент свадьбы.

Альтернативный коэффициент можно рассчитать, измеряя смешивание по степеням вершин. Ньюман[1] вывел следующее выражение

${\displaystyle r={\frac {\sum _{jk}jk(e_{jk}-q_{j}q_{k})}{\sigma _{q}^{2}}}}$

для ненаправленной сети. В этой формуле, если ${\displaystyle p_{k}}$ относится к распределению степеней графа (т.е. вероятности, что узел имеет степень ${\displaystyle k}$), тогда ${\displaystyle \textstyle q_{k}={\frac {(k+1)p_{k+1}}{z}}}$. Это относится к избыточной степени (excess degree) узла, или числу других рёбер, помимо изучаемого в настоящий момент. ${\displaystyle z}$ обозначает среднюю степень в сети, а ${\displaystyle \sigma _{q}}$ — среднеквадратическое отклонение распределения ${\displaystyle q_{k}}$. Для направленной сети эквивалентное выражение имеет вид

${\displaystyle r={\frac {\sum _{jk}jk(e_{jk}-q_{j}^{in}q_{k}^{out})}{\sigma _{in}\sigma _{out}}}~.}$.

Эта корреляция положительна, когда узлы ассортативны по степеням, и отрицательна, когда сеть дизассортативна. Таким образом, эта мера даёт общее представление о паттернах смешивания в сети. Более глубокий анализ приведён в статье «Ассортативность».

Метод производящих функций по-прежнему применим и в этом случае, но функции, которые надо найти, редко можно определить в аналитическом виде. Таким образом, численные вычисления выглядят единственным способом получить конечный результат. В этом случае снова используется метод Монте-Карло. Для случая сетей со степенным законом распределения степеней ${\displaystyle p_{k}\sim k^{-\tau }}$, ${\displaystyle q_{k}}$ имеет расходящееся среднее, кроме случая ${\displaystyle \tau >3}$, который встречается редко.[3] Вместо этого, экспоненциально обрезанное распределение по степенному закону ${\displaystyle \textstyle p_{k}={\frac {k^{-\tau }\mathrm {e} ^{-k/\kappa }}{\mathrm {Li} _{\tau }(\mathrm {e} ^{-1/\kappa })}}\ \mathrm {for} \ k\geq 1}$ даёт распределение для избыточной степени типа ${\displaystyle q_{k}\sim (k+1)^{1-\tau }\mathrm {e} ^{-(k+1)/\kappa }}$. Результаты для этого случая описаны ниже.

1) Позиция на фазовом переходе, при которой гигантский кластер движется к более высоким значениям ${\displaystyle \kappa }$, тогда как значение ${\displaystyle r}$ снижается. Иными словами, чем более ассортативна сеть, тем ниже порог плотности рёбер для появления гигантского кластера.

2) Размер гигантского кластера в пределе большой ${\displaystyle \kappa }$ меньше для графа с ассортативным смешиванием, чем для нейтральных и дизассортативных графов.

3) Ассортативное смешивание в сети влияет на устойчивость сети при удалении узлов. Для ассортативных сетей требуется удалить примерно в десять раз больше узлов с высокими степенями, чтобы уничтожить гигантский кластер, чем в обычной сети (под обычной имеется в виду нейтральная сеть), тогда как противоположное верно для дизассортативных сетей, т.е. они более чувствительны, чем нейтральные, к удалению узлов с высокой степенью.

Этот результат о зависимости устойчивости сети от смешивания узлов можно объяснить следующим образом. По определению, узлы с высокой степенью в ассортативных сетях имеют тенденцию образовывать ядерную группу (core group) между ними. Такая ядерная группа обеспечивает устойчивость сети, концентрируя все очевидные целевые узлы вместе в одной части графа. Удаление этих узлов с высокой степенью по-прежнему является одним из наиболее эффективных способов уничтожить связность сети, но менее эффективным (в сравнении с нейтральной сетью), поскольку, удалив их все из той же части графа, мы не атакуем другие части графа. Если эти другие части сами по себе устойчиво работают, то гигантский кластер останется, даже если узлы с высокими степенями исчезнут. С другой стороны, сети с дизассортативным смешиванием особенно чувствительны к удалению узлов с высокими степенями, поскольку эти узлы рассыпаны далеко друг от друга по сети, поэтому атака на них это как атака на все части сети одновременно.

Типичным приложением паттернов смешивания является изучение передачи заболеваний. Например, многие исследования используют смешивание для изучения распространения СПИДа и других заразных заболеваний.[4][5][6] Эти статьи находят сильную связь между паттернами смешивания и скоростью распространения заболеваний. Результаты также могут быть полезны для моделирования роста сетей реального мира, как, например, в [7], или обнаружения сообществ в сетях.