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

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

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

ИзмерениеПравить

 

Рис. 1: Безмасштабные сети с различными степенями ассортативности: (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{\underset{jk}{\sum <!--\; \sum \; -->}jk(e_{jk}-<!--\; -\; -->q_j{q}_k)}{{\mathrm{\sigma <!--\; \sigma \; -->}}_q^2}$$r={\frac {\sum _{jk}{jk(e_{jk}-q_{j}q_{k})}}{\sigma _{q}^{2}}}$ , где $q_k$$q_{k}$  это распределение остаточных степеней (remaining degree). Оно фиксирует число рёбер, исходящих из узла, за исключением одного ребра, соединяющего пару. Это распределение получается из распределения степеней $p_k$$p_{{k}}$  как $q_k=\frac{(k+1)p_{k+1}}{\underset{j\ge <!--\; \ge \; -->1}{\sum <!--\; \sum \; -->}j{p}_j}$$q_{k}={\frac {(k+1)p_{k+1}}{\sum _{j\geq 1}jp_{j}}}$ . Наконец, $e_{jk}$$e_{jk}$  обозначает совместное распределение остаточных степеней двух вершин. Это количество симметрично для ненаправленного графа и следует правилам суммирования: $\underset{jk}{\sum <!--\; \sum \; -->}{e}_{jk}=1$$\sum _{jk}{e_{jk}}=1\,$  и $\underset{j}{\sum <!--\; \sum \; -->}{e}_{jk}=q_k$$\sum _{j}{e_{jk}}=q_{k}\,$ .

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

$r(\mathrm{\alpha <!--\; \alpha \; -->},\mathrm{\beta <!--\; \beta \; -->})=\frac{\underset{i}{\sum <!--\; \sum \; -->}(j_i^{\mathrm{\alpha <!--\; \alpha \; -->}}-<!--\; -\; -->\stackrel{¯<!--\; ¯\; -->}{j^{\mathrm{\alpha <!--\; \alpha \; -->}}})(k_i^{\mathrm{\beta <!--\; \beta \; -->}}-<!--\; -\; -->\stackrel{¯<!--\; ¯\; -->}{k^{\mathrm{\beta <!--\; \beta \; -->}}})}{\sqrt{\underset{i}{\sum <!--\; \sum \; -->}(j_i^{\mathrm{\alpha <!--\; \alpha \; -->}}-<!--\; -\; -->\stackrel{¯<!--\; ¯\; -->}{j^{\mathrm{\alpha <!--\; \alpha \; -->}}}{)}^2}\sqrt{\underset{i}{\sum <!--\; \sum \; -->}(k_i^{\mathrm{\beta <!--\; \beta \; -->}}-<!--\; -\; -->\stackrel{¯<!--\; ¯\; -->}{k^{\mathrm{\beta <!--\; \beta \; -->}}}{)}^2}}.$$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)Править

Файл:K(NearestNeighbor) distribution for two real-world networks.gif

Рис. 2: k_nn-распределение для двух реальных сетей. Верхняя сеть (a) дизассортативна, поскольку наклон отрицательный. С другой стороны, (b) ассортативна, поскольку наклон положительный.

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

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

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

$\mathrm{\rho <!--\; \rho \; -->}=\frac{j\left(j+1\right)\left(\stackrel{¯<!--\; ¯\; -->}{k}-<!--\; -\; -->{\mathrm{\mu <!--\; \mu \; -->}}_q\right)}{2M{\mathrm{\sigma <!--\; \sigma \; -->}}_q^2}$$\rho ={\frac {j\ \left(j+1\right)\left({\overline {k}}-\ {\mu }_{q}\right)}{2M{\sigma }_{q}^{2}}}$ 

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

Соответственно, локальная ассортативность в направленных сетях – это вклад узла в направленную ассортативность (directed assortativity) сети. Вклад узла в ассортативность направленной сети $r_d$$r_{d}$  определяется как: ${\mathrm{\rho <!--\; \rho \; -->}}_d=\frac{{j_{out}}^2\left({\stackrel{¯<!--\; ¯\; -->}{k}}_{in}-<!--\; -\; -->{\mathrm{\mu <!--\; \mu \; -->}}_q^{in}\right)+{j_{in}}^2\left({\stackrel{¯<!--\; ¯\; -->}{k}}_{out}-<!--\; -\; -->{\mathrm{\mu <!--\; \mu \; -->}}_q^{out}\right)}{2M{\mathrm{\sigma <!--\; \sigma \; -->}}_q^{in}{\mathrm{\sigma <!--\; \sigma \; -->}}_q^{out}}$${\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}$$j_{out}$  – это исходящая степень (out-degree) рассматриваемого узла, $j_{in}$$j_{in}$  – входящая степень (in-degree), ${\stackrel{¯<!--\; ¯\; -->}{k}}_{in}$${\overline {k}}_{in}$  – средняя входящая степень его соседей (в какие узлы у $v$$v$ }-го узла есть ребро) и ${\stackrel{¯<!--\; ¯\; -->}{k}}_{out}$${\overline {k}}_{out}$  – это средняя исходящая степень его соседей (из каких узлов у $v$$v$ -го узла есть ребро). ${\mathrm{\sigma <!--\; \sigma \; -->}}_q^{in}\ne <!--\; \ne \; -->0$${\sigma }_{q}^{in}\ \neq 0$ ,${\mathrm{\sigma <!--\; \sigma \; -->}}_q^{out}\ne <!--\; \ne \; -->0$$\ {\ \sigma }_{q}^{out}\ \neq 0$ .

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

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

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

Файл:Size (n) and assortativity coefficient (r) for various networks.jpg

Рис. 3: Размер n и коэффициент ассортативности r для различных сетей.

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

В таблице также указаны значения r, рассчитанные аналитически для двух моделей сетей:

1. случайный граф Эрдёша — Реньи;
2. модель Барабаши — Альберт.

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

ПриложенияПравить

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

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

Основная статья: structural cut-off

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

См. такжеПравить

• Ассортативное смешивание
• Preferential attachment
• Гомофилия
• Structural cut-off
• Rich-club coefficient