Ассортативность

Ассортати́вность, или ассортативное смешивание — предпочтение узлов сети присоединяться к другим узлам, которые каким-либо образом похожи на них. Хотя конкретная мера сходства может различаться, теоретики сетей часто исследуют ассортативность в терминах степеней узла. Добавление этой характеристики в сетевые модели часто позволяет более точно аппроксимировать поведение многих реальных сетей.

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

Измерение

Безмасштабные сети с различными степенями ассортативности: (a) A = 0 (некоррелированная сеть), (b) A = 0,26, (c) A = 0,43, где A обозначает r (коэффициент ассортативности, как он определён в этом подразделе).

Ассортативность часто на практике реализуется как корреляция между двумя узлами. Тем не менее, есть несколько способов оценить такую корреляцию. Две наиболее значимые меры это коэффициент ассортативности и neighbor connectivity (связность соседей). Эти меры более детально рассматриваются ниже.

Коэффициент ассортативности

Коэффициент ассортативности — это коэффициент корреляции Пирсона степени между парами соединённых узлов. Положительные значения r обозначают корреляцию между узлами схожих степеней, а отрицательные значения обозначают отношения между узлами разных степеней. В целом, r лежит между −1 и 1. Когда r = 1, о сети говорят, что в ней наблюдаются истинные паттерны ассортативного смешивания (perfect assortative mixing patterns), когда r = 0 сеть неассортативна, а при r = −1 сеть полностью дизассортативна.

Коэффициент ассортативности задаётся формулой: $r={\frac {\sum _{jk}{jk(e_{jk}-q_{j}q_{k})}}{\sigma _{q}^{2}}}$, где $q_{k}$ это распределение остаточных степеней (remaining degree). Оно фиксирует число рёбер, исходящих из узла, за исключением одного ребра, соединяющего пару. Это распределение получается из распределения степеней $p_{k}$ как $q_{k}={\frac {(k+1)p_{k+1}}{\sum _{j\geq 1}jp_{j}}}$. Наконец, $e_{jk}$ обозначает совместное распределение остаточных степеней двух вершин. Это количество симметрично для ненаправленного графа и следует правилам суммирования: $\sum _{jk}{e_{jk}}=1\,$ и $\sum _{j}{e_{jk}}=q_{k}\,$.

В направленном графе ассортативность входящих степеней (in-assortativity, $r({\text{in}},{\text{in}})$) и ассортативность исходящих степеней (out-assortativity, $r({\text{out}},{\text{out}})$) измеряют тенденцию узлов соединяться с другими узлами, имеющими схожие с ними входящие и исходящие степени, соответственно. Развивая это, можно рассмотреть четыре типа ассортативности (смотрите). Принимая условные обозначения той статьи, возможно определить четыре метрики: $r({\text{in}},{\text{in}})$, $r({\text{in}},{\text{out}})$, $r({\text{out}},{\text{in}})$, and $r({\text{out}},{\text{out}})$. Пусть $(\alpha ,\beta )$ это одна из словесных пар in/out (например, $(\alpha ,\beta )=({\text{out}},{\text{in}})$). Пусть $E$ это число рёбер в сети. Предположим, что мы пронумеровали рёбра сети как $1,\ldots ,E$. Дано ребро с номером $i$, пусть $j_{i}^{\alpha }$ — это $\alpha$-степень источника (например, хвоста) узловой вершины ребра, а $k_{i}^{\beta }$ — это $\beta$-степень целевого узла (то есть головы) $i$-го ребра. Мы обозначим средние значения чертой, так что ${\bar {j^{\alpha }}}$ и ${\bar {k^{\beta }}}$ — это средние $\alpha$-степень источников и $\beta$-степень целей, соответственно; средние берутся по рёбрам сети. Наконец, мы имеем:

$r(\alpha ,\beta )={\frac {\sum _{i}(j_{i}^{\alpha }-{\bar {j^{\alpha }}})(k_{i}^{\beta }-{\bar {k^{\beta }}})}{{\sqrt {\sum _{i}(j_{i}^{\alpha }-{\bar {j^{\alpha }}})^{2}}}{\sqrt {\sum _{i}(k_{i}^{\beta }-{\bar {k^{\beta }}})^{2}}}}}.$

Связность соседей (Neighbor connectivity)

Другой способ оценить корреляцию степеней это изучить свойства $\langle k_{nn}\rangle$, или средней степени соседей узла со степенью k. Формально это определяется так: $\langle k_{nn}\rangle =\sum _{k'}{k'P(k'|k)}$, где $P(k'|k)$ — это условная вероятность, что ребро узла со степенью k указывает на узел со степенью k'. Если эта функция возрастает, то сеть ассортативная, поскольку она показывает, что узлы с высокими степенями соединяются, в среднем, с узлами высоких степеней. Напротив, если функция убывает, то сеть дизассортативная, поскольку узлы высоких степеней имеют тенденцию соединяться с узлами более низкой степени.

Локальная ассортативность

В ассортативных сетях могут быть дизассортативные узлы, и наоборот. Мера локальной ассортативности требуется для выявления таких аномалий в сетях. Локальная ассортативность определяется как вклад, который каждый узел делает в ассортативность сети. Локальная ассортативность в ненаправленных сетях определяется как:

$\rho ={\frac {j\ \left(j+1\right)\left({\overline {k}}-\ {\mu }_{q}\right)}{2M{\sigma }_{q}^{2}}}$

Где $j$ — это избыточная степень (excess degree) конкретного узла, ${\overline {k}}$ — это средняя избыточная степень его соседей, а M — это число связей в сети.

Соответственно, локальная ассортативность в направленных сетях — это вклад узла в направленную ассортативность (directed assortativity) сети. Вклад узла в ассортативность направленной сети $r_{d}$ определяется как: ${\rho }_{d}=\ {\frac {{j_{out}}^{2}\left({\overline {k}}_{in}-\ {\mu }_{q}^{in}\right)+\ {j_{in}}^{2}\left({\overline {k}}_{out}-\ {\mu }_{q}^{out}\right)}{2\ M{\sigma }_{q}^{in}{\sigma }_{q}^{out}}}$

Где $j_{out}$ — это исходящая степень (out-degree) рассматриваемого узла, $j_{in}$ — входящая степень (in-degree), ${\overline {k}}_{in}$ — средняя входящая степень его соседей (в какие узлы у $v$}-го узла есть ребро) и ${\overline {k}}_{out}$ — это средняя исходящая степень его соседей (из каких узлов у $v$-го узла есть ребро). ${\sigma }_{q}^{in}\ \neq 0$,$\ {\ \sigma }_{q}^{out}\ \neq 0$.

Включая масштабирующие члены ${\sigma }_{q}^{in}$ и ${\ \sigma }_{q}^{out}$, мы обеспечиваем, что уравнение локальной ассортативности для направленной сети удовлетворяет условию $r_{d}=\ \sum _{i=1}^{N}{{\rho }_{d}}$.

Далее, в зависимости от того, рассматривается ли входящая степень или исходящая, возможно определения локальную входящую ассортативность (local in-assortativity) и локальную исходящую ассортативность (local out-assortativity) как соответствующие меры локальной ассортативности в направленной сети.

Паттерны ассортативного смешивания в реальных сетях

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

В модели Эрдёша-Реньи, поскольку рёбра располагаются случайно, вне зависимости от степеней вершин, в результате получается, что r = 0 в пределе большого размера графа. Безмасштабная модель Барабаши-Альберт также сохраняет это свойство. Для модели Барабаши-Альберт в особом случае при m=1 (где каждый новый узел присоединяется только к одному из существующих узлов с вероятностью, пропорциональной степени) получаем $r\to 0$ как $(\log ^{2}N)/N$ в пределе большого $N$.

Приложения

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

Структурная дизассортативность

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

См. также

• Ассортативное смешивание
• Гомофилия