Наука о сетях
Граф Комплексные сети Мир тесен Безмасштабная сеть Перколяция Визуализация Социальный капитал Анализ связей Оптимизация Гомофилия Транзитивность Теория когнитивного баланса Сетевой эффект Социальное влияние
Типы сетей
Вычислительная Коммуникационная Социальная Биологическая Нейронная Семантическая Граф потоков
Графы
Термины Клика Компонента связности Разрез Цикл Структура данных Ребро Петля Окрестность Путь Вершина Список / матрица смежности Список, матрица инцидентности Типы Двудольный Полный Ориентированный Гипер Мульти Случайный Взвешенный
Центральность Степень Посредничество Близость PageRank Распределение степеней Расстояние
Модели
Топология Случайный граф Эрдёша-Реньи Барабаши — Альберт Динамика Агентное моделирование /
Списки Категории
Теория сетей Теория графов

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

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

Измерение

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

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

Коэффициент ассортативности — это коэффициент корреляции Пирсона степени между парами соединённых узлов. Положительные значения 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}})}$ ) измеряют тенденцию узлов соединяться с другими узлами, имеющими схожие с ними входящие и исходящие степени, соответственно. Развивая это, можно рассмотреть четыре типа ассортативности (смотрите ). Принимая условные обозначения той статьи, возможно определить четыре метрики: ${\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}}}}}.}$

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

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

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

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

${\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 — это число связей в сети.

Соответственно, локальная ассортативность в направленных сетях — это вклад узла в направленную ассортативность (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) как соответствующие меры локальной ассортативности в направленной сети.

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

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

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

Приложения

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

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

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

См. также

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

Примечания