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

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

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

Измерение

Безмасштабные сети с различными степенями ассортативности: (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\ge 1}j{p}_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,\dots ,E$. Дано ребро с номером $i$, пусть $j_i^{\alpha }$ — это $\alpha$-степень источника (например, хвоста) узловой вершины ребра, а $k_i^{\beta }$ — это $\beta$-степень целевого узла (то есть головы) $i$-го ребра. Мы обозначим средние значения чертой, так что $\overline{j^{\alpha }}$ и $\overline{k^{\beta }}$ — это средние $\alpha$-степень источников и $\beta$-степень целей, соответственно; средние берутся по рёбрам сети. Наконец, мы имеем:

$r(\alpha ,\beta )=\frac{\sum _i(j_i^{\alpha }-\overline{j^{\alpha }})(k_i^{\beta }-\overline{k^{\beta }})}{\sqrt{\sum _i(j_i^{\alpha }-\overline{j^{\alpha }}{)}^2}\sqrt{\sum _i(k_i^{\beta }-\overline{k^{\beta }}{)}^2}}.$

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

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

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

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

$\rho =\frac{j(j+1)(\bar{k}-{\mu }_q)}{2M{\sigma }_q^2}$

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

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

Где $j_{out}$ — это исходящая степень (out-degree) рассматриваемого узла, $j_{in}$ — входящая степень (in-degree), ${\bar{k}}_{in}$ — средняя входящая степень его соседей (в какие узлы у $v$}-го узла есть ребро) и ${\bar{k}}_{out}$ — это средняя исходящая степень его соседей (из каких узлов у $v$-го узла есть ребро). ${\sigma }_q^{in}\ne 0$,${\sigma }_q^{out}\ne 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$.

Приложения

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

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

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

См. также

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