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

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

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

Измерение

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

Ассортативность часто интерпретируется как корреляция между двумя узлами. Однако существует несколько способов уловить такую ​​корреляцию. Двумя наиболее важными показателями являются коэффициент ассортативности и связность соседей . Эти меры более подробно изложены ниже.

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

Коэффициент ассортативности представляет собой коэффициент корреляции Пирсона степени между парами связанных узлов. Положительные значения r указывают на корреляцию между узлами одинаковой степени, а отрицательные значения указывают на связи между узлами разной степени. В общем, r лежит между -1 и 1. Когда r = 1, говорят, что сеть имеет идеальные модели ассортативного смешивания, когда r = 0 сеть неассортативна, а при r = -1 сеть полностью неассортативна.

Коэффициент ассортативности определяется выражением $r={\frac {\sum _{jk}{jk(e_{jk}-q_{j}q_{k})}}{\sigma _{q}^{2}}}$. Термин $q_{k}$ — распределение оставшейся степени . При этом фиксируется количество ребер, выходящих из узла, кроме того, которое соединяет пару. Распределение этого термина получено из распределения степеней $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}\,$.

В ориентированном графе неассортативность ( $r({\text{in}},{\text{in}})$) и внеассортативность ( $r({\text{out}},{\text{out}})$) измеряют склонность узлов соединяться с другими узлами, которые имеют аналогичную степень входа и выхода соответственно. Развивая это дальше, можно рассмотреть четыре типа ассортативности (см. ). Приняв обозначения этой статьи, можно определить четыре метрики. $r({\text{in}},{\text{in}})$, $r({\text{in}},{\text{out}})$, $r({\text{out}},{\text{in}})$, и $r({\text{out}},{\text{out}})$. Позволять $(\alpha ,\beta )$, быть одной из пар входных / выходных слов (например, $(\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}}}}}.$

Связь с соседями

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

Местная ассортативность

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

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

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

Соответственно, локальная ассортативность для направленных сетей — вклад узла в направленную ассортативность сети. Вклад узла в ассортативность направленной сети $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}$ - это степень выхода рассматриваемого узла и $j_{in}$ это входящая степень, ${\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}}$.

Кроме того, в зависимости от того, рассматривается ли распределение входящей или исходящей степени, можно определить локальную инассортативность и локальную внеассортативность как соответствующие меры локальной ассортативности в направленной сети.

смешивания реальных

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

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

1. случайный граф Эрдеша и Реньи
2. Модель BA (модель Барабаши-Альберта)

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

Приложение

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

Структурная

Основная статья: структурное отсечение

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

См. также

• Ассортативное смешивание
• Предпочтительное вложение
• Гомофилия
• Структурное отсечение
• Коэффициент богатого клуба