Паттерны смешивания (Hgmmyjud vbyonfgunx)

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

Типы паттернов смешивания

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

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

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

Смешивание, основанное на дискретных характеристиках

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

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

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

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

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

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

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

с

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

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

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

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

и

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

где:

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

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

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

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

$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}}}~.$

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

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

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

Смешивание на основе скалярных или топологических характеристик

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

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

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

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

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

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

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

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

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

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

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

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

Примеры и приложения

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