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

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

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

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

${\displaystyle 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}}}}}.}$

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

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

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

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

Соответственно, локальная ассортативность в направленных сетях[5] – это вклад узла в направленную ассортативность (directed assortativity) сети. Вклад узла в ассортативность направленной сети ${\displaystyle r_{d}}$ определяется как: ${\displaystyle {\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}}}}$

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

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

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