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

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

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

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

Измерение

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

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

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

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

В коэффициент ассортативности дан кем-то ${ 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} ,}$.

В ориентированном графе ассортативность (${ displaystyle r ({ text {in}}, { text {in}})}$) и внеассортативность (${ displaystyle r ({ text {out}}, { text {out}})}$) измеряют тенденции узлов к соединению с другими узлами, которые имеют такие же внутренние и внешние степени, как и они сами, соответственно.^[4] Расширяя это, можно рассмотреть четыре типа ассортативности (см.^[5]). Принимая обозначения этой статьи, можно определить четыре показателя. ${ 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 ( альфа, бета)}$, будь одним из в/из пары слов (например, ${ displaystyle ( alpha, beta) = ({ text {out}}, { text {in}})}$). Позволять ${ displaystyle E}$ количество ребер в сети. Предположим, мы помечаем края сети ${ displaystyle 1, ldots, E}$. Данный край ${ displaystyle i}$, позволять ${ displaystyle j_ {i} ^ { alpha}}$ быть ${ displaystyle alpha}$-степень источника (т.е. хвост) узловая вершина ребра, а ${ Displaystyle к_ {я} ^ { бета}}$ быть ${ displaystyle beta}$-степень цели (т.е. голова) узел края ${ displaystyle i}$. Мы обозначаем средние значения полосами, чтобы ${ displaystyle { bar {j ^ { alpha}}}}$, и ${ displaystyle { bar {k ^ { beta}}}}$ средние ${ displaystyle alpha}$-степень источников, и ${ displaystyle beta}$-степень мишеней соответственно; усреднение по краям сети. Наконец, у нас есть

${ Displaystyle г ( альфа, бета) = { гидроразрыва { сумма _ {я} (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} }}}}.}$

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

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

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

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

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

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

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

Соответственно, локальная ассортативность для направленных сетей^[4] - это вклад узла в направленную ассортативность сети. Вклад узла в ассортативность направленной сети ${ 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 _ {я = 1} ^ {N} {{ rho} _ {d}}}$.

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

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

Рис. 3: Размер п и коэффициент ассортативности р для различных сетей.^[2]

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

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

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

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

Заявление

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

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

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

Смотрите также

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

Рекомендации