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

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Составная часть Резать Цикл Структура данных Край Петля Район Дорожка Вершина Список  / матрица смежности Список  / матрица заболеваемости Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
МетрикиАлгоритмы
Центральность Степень Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес-модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия / SIR
СпискиКатегории
Темы Программное обеспечение Сетевые ученые Категория: Теория сетей Категория: Теория графов
v т е

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

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

Измерение [ править ]

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

Коэффициент ассортативности [ править ]

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

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

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

Связь с соседями [ править ]

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

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

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

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

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

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

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

Ассортативные шаблоны микширования реальных сетей [ править ]

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

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

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

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

Заявление [ править ]

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

Структурная дезассортативность [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]