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

Ассортативность, или же ассортативное смешивание это предпочтение для узлов сети присоединяться к другим, которые в чем-то похожи. Хотя конкретный мера сходства могут варьироваться, теоретики сетей часто рассматривают ассортативность с точки зрения узлов степень.^[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 (\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}}}}}.}$

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

Рис. 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 _{i=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 (\log ^{2}N)/N}$ в пределе большого${\displaystyle N}$.^[2]

Заявление

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

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

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

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

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

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

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

1. Ньюман, М. Э. Дж. (27 февраля 2003 г.). «Смешивание паттернов в сетях». Физический обзор E. Американское физическое общество (APS). 67 (2): 026126. arXiv:cond-mat / 0209450. Bibcode:2003PhRvE..67b6126N. Дои:10.1103 / Physreve.67.026126. ISSN  1063-651X.
2. Ньюман, М. Э. Дж. (28 октября 2002 г.). «Ассортативное смешение в сетях». Письма с физическими проверками. Американское физическое общество (APS). 89 (20): 208701. arXiv:cond-mat / 0205405. Bibcode:2002ПхРвЛ..89т8701Н. Дои:10.1103 / Physrevlett.89.208701. ISSN  0031-9007. PMID  12443515.
3. Xulvi-Brunet, R .; Соколов, И.М. (2005). «Изменение корреляций в сетях: ассортативность и диссортативность». Acta Physica Полоника B. 36 (5): 1431.
4. Пиравеенан, М .; Прокопенко, М .; Зомая, А. (2008). «Ассортативное перемешивание в направленных биологических сетях». IEEE / ACM Transactions по вычислительной биологии и биоинформатике. 9 (1): 66–78. Дои:10.1109 / TCBB.2010.80. PMID  20733240.
5. Фостер, Джейкоб; Дэвид В. Фостер; Питер Грассбергер; Майя Пачуски (июнь 2010 г.). «Направление края и структура сетей». Труды Национальной академии наук. 107 (24): 10815–20. arXiv:0908.4288. Bibcode:2010PNAS..10710815F. Дои:10.1073 / pnas.0912671107. ЧВК  2890716. PMID  20505119.
6. Ли, Сан Хун; Ким, Пан-Джун; Чон, Хоунг (4 января 2006 г.). «Статистические свойства выбранных сетей». Физический обзор E. Американское физическое общество (APS). 73 (1): 016102. arXiv:cond-mat / 0505232. Дои:10.1103 / Physreve.73.016102. ISSN  1539-3755.
7. Пастор-Саторрас, Ромуальдо; Васкес, Алексей; Веспиньяни, Алессандро (2001). «Динамические и корреляционные свойства Интернета». Письма с физическими проверками. Американское физическое общество (APS). 87 (25): 258701. arXiv:cond-mat / 0105161. Bibcode:2001ПхРвЛ..87у8701П. Дои:10.1103 / Physrevlett.87.258701. ISSN  0031-9007. PMID  11736611.
8. Пиравеенан, М .; Прокопенко, М .; Зомая, А. (2008). «Локальная ассортативность в безмасштабных сетях». EPL (Еврофизические письма). 84 (2): 28002. Bibcode:2008ЭЛ ..... 8428002П. Дои:10.1209/0295-5075/84/28002.
9. Джонсон, Самуэль; Торрес, Хоакин Дж .; Marro, J .; Муньос, Мигель А. (11 марта 2010 г.). «Энтропийное происхождение дезассортативности в сложных сетях». Письма с физическими проверками. Американское физическое общество (APS). 104 (10): 108702. arXiv:1002.3286. Bibcode:2010PhRvL.104j8702J. Дои:10.1103 / Physrevlett.104.108702. ISSN  0031-9007. PMID  20366458.