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

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

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

• 1 Измерение
  • 1,1 Коэффициент ассортативности
  • 1,2 Связность между соседями
  • 1.3 Локальная ассортативность
• 2 Ассортативные модели смешивания реальных сетей
• 3 Применение
• 4 Структурная дезассортативность
• 5 См. Также
• 6 Ссылки

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

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

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

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

Коэффициент ассортативности определяется как $r\; =\; \sum \; jkjk\; (ejk\; -\; qjqk)\; \sigma \; q\; 2\; \{\backslash \; displaystyle\; r\; =\; \{\backslash \; frac\; \{\backslash \; sum\; \_\; \{jk\}\; \{jk\; (e\_\; \{jk\}\; -\; q\_\; \{j\}\; q\_\; \{k\})\}\}\; \{\backslash \; sigma\; \_\; \{q\}\; ^\; \{2\}\}\}\}$. Член $q\; k\; \{\backslash \; displaystyle\; q\_\; \{k\}\}$представляет собой распределение оставшейся степени. Это фиксирует количество ребер, выходящих из узла, кроме того, которое соединяет пару. Распределение этого члена получается из распределения степеней $pk\; \{\backslash \; displaystyle\; p\_\; \{k\}\}$как $qk\; =\; (k\; +\; 1)\; pk\; +\; 1\; \sum \; j\; \ge \; 1\; jpj\; \{\backslash \; displaystyle\; q\_\; \{k\}\; =\; \{\backslash \; frac\; \{(k\; +\; 1)\; p\_\; \{k\; +\; 1\}\}\; \{\backslash \; sum\; \_\; \{j\; \backslash \; geq\; 1\}\; jp\_\; \{j\}\}\}\}$. Наконец, $e\; j\; k\; \{\backslash \; displaystyle\; e\_\; \{jk\}\}$относится к совместному распределению вероятностей оставшихся степеней двух вершин. Эта величина симметрична на неориентированном графе и подчиняется правилам сумм $\sum \; jkejk\; =\; 1\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{jk\}\; \{e\_\; \{jk\}\}\; =\; 1\; \backslash ,\}$и $\sum \; jejk\; =\; qk\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{j\}\; \{e\_\; \{jk\}\}\; =\; q\_\; \{k\}\; \backslash ,\}$.

В ориентированном графе, ассортативность ($r\; (in,\; in)\; \{\; \backslash \; displaystyle\; r\; (\{\backslash \; text\; \{in\}\},\; \{\backslash \; text\; \{in\}\})\}$) и внеасортативность ($r\; (out,\; out)\; \{\backslash \; displaystyle\; r\; (\{\backslash \; text\; \{out\}\},\; \{\backslash \; text\; \{out\}\})\}$) измеряют тенденции узлов к соединению с другими узлами, которые имеют такие же внутренние и внешние степени, как и они сами, соответственно. Расширяя это дальше, можно рассмотреть четыре типа ассортативности (см.). Принимая обозначения этой статьи, можно определить четыре метрики $r\; (in,\; in)\; \{\backslash \; displaystyle\; r\; (\{\backslash \; text\; \{in\}\},\; \{\backslash \; text\; \{in\}\})\}$, $r\; (\; вход,\; выход)\; \{\backslash \; displaystyle\; r\; (\{\backslash \; text\; \{in\}\},\; \{\backslash \; text\; \{out\}\})\}$, $r\; (out,\; in)\; \{\backslash \; displaystyle\; r\; (\{\backslash \; text\; \{out\}\},\; \{\backslash \; text\; \{in\}\})\}$и $r\; (out,\; out)\; \{\backslash \; displaystyle\; r\; (\{\backslash \; text\; \{out\}\},\; \{\backslash \; text\; \{out\}\})\}$. Пусть $(\alpha ,\; \beta )\; \{\backslash \; displaystyle\; (\backslash \; alpha,\; \backslash \; beta)\}$будет одной из пар слов ввода / вывода (например, $(\alpha ,\; \beta )\; =\; (out,\; in)\; \{\backslash \; displaystyle\; (\backslash \; alpha,\; \backslash \; beta)\; =\; (\{\backslash \; text\; \{out\}\},\; \{\backslash \; text\; \{in\}\})\}$). Пусть $E\; \{\backslash \; displaystyle\; E\}$будет количеством ребер в сети. Предположим, мы помечаем края сети $1,\dots ,\; E\; \{\backslash \; displaystyle\; 1,\; \backslash \; ldots,\; E\}$. Для данного ребра $i\; \{\backslash \; displaystyle\; i\}$пусть $ji\; \alpha \; \{\backslash \; displaystyle\; j\_\; \{i\}\; ^\; \{\backslash \; alpha\}\}$будет $\alpha \; \{\; \backslash \; displaystyle\; \backslash \; alpha\}$- степень вершины исходного (т. е. хвостового) узла ребра, и $ki\; \beta \; \{\backslash \; displaystyle\; k\_\; \{i\}\; ^\; \{\backslash \; beta\}\}$быть $\beta \; \{\backslash \; displaystyle\; \backslash \; beta\}$-градусом целевого (то есть головного) узла края $i\; \{\backslash \; displaystyle\; i\}$. Мы обозначаем средние значения полосами, так что $j\; \alpha \; ¯\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{j\; ^\; \{\backslash \; alpha\}\}\}\}$и $k\; \beta \; ¯\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{k\; ^\; \{\backslash \; beta\}\}\}\}$- это средняя $\alpha \; \{\backslash \; displaystyle\; \backslash \; alpha\}$-степень источников, а $\beta \; \{\backslash \; displaystyle\; \backslash \; beta\}$-степень целей соответственно; усреднение по краям сети. Наконец, имеем

$r\; (\alpha ,\; \beta )\; =\; \sum \; i\; (ji\; \alpha \; -\; j\; \alpha \; ¯)\; (ki\; \beta \; -\; k\; \beta \; ¯)\; \sum \; i\; (ji\; \alpha \; -\; j\; \alpha \; ¯)\; 2\; \sum \; i\; (ki\; \beta \; -\; k\; \beta \; ¯)\; 2.\; \{\backslash \; Displaystyle\; г\; (\backslash \; альфа,\; \backslash \; бета)\; =\; \{\backslash \; гидроразрыва\; \{\backslash \; сумма\; \_\; \{я\}\; (j\_\; \{i\}\; ^\; \{\backslash \; alpha\}\; -\; \{\backslash \; bar\; \{j\; ^\; \{\backslash \; alpha\}\}\})\; (k\_\; \{i\; \}\; ^\; \{\backslash \; beta\}\; -\; \{\backslash \; bar\; \{k\; ^\; \{\backslash \; beta\}\}\})\}\; \{\{\backslash \; sqrt\; \{\backslash \; sum\; \_\; \{i\}\; (j\_\; \{i\}\; ^\; \{\backslash \; alpha\}\; -\; \{\backslash \; bar\; \{j\; ^\; \{\; \backslash \; alpha\}\}\})\; ^\; \{2\}\}\}\; \{\backslash \; sqrt\; \{\backslash \; sum\; \_\; \{i\}\; (k\_\; \{i\}\; ^\; \{\backslash \; beta\}\; -\; \{\backslash \; bar\; \{k\; ^\; \{\backslash \; beta\}\}\})\; ^\; \{2\}\; \}\}\}\}.\}$

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

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

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

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

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

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

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

Соответственно, локальная ассортативность для направленных сетей - это вклад узла в направленную ассортативность сети. Вклад узла в ассортативность направленной сети $rd\; \{\backslash \; displaystyle\; r\_\; \{d\}\}$определяется как, $\rho \; d\; =\; jout\; 2\; (k\; ¯\; in\; -\; \mu \; qin)\; +\; jin\; 2\; (k\; ¯\; out\; -\; \mu \; qout)\; 2\; M\; \sigma \; qin\; \sigma \; qout\; \{\backslash \; displaystyle\; \{\backslash \; rho\}\; \_\; \{d\}\; =\; \backslash \; \{\backslash \; frac\; \{\{j\_\; \{out\}\}\; ^\; \{2\}\; \backslash \; left\; (\{\backslash \; overline\; \{k\; \}\}\; \_\; \{in\}\; -\; \backslash \; \{\backslash \; mu\}\; \_\; \{q\}\; ^\; \{in\}\; \backslash \; right)\; +\; \backslash \; \{j\_\; \{in\}\}\; ^\; \{2\}\; \backslash \; left\; (\{\backslash \; overline\; \{k\}\}\; \_\; \{out\}\; -\; \backslash \; \{\backslash \; mu\}\; \_\; \{q\}\; ^\; \{out\}\; \backslash \; right)\}\; \{2\; \backslash \; M\; \{\backslash \; sigma\}\; \_\; \{q\}\; ^\; \{in\}\; \{\backslash \; sigma\}\; \_\; \{q\}\; ^\; \{out\}\}\}\}$

Где $jout\; \{\backslash \; displaystyle\; j\_\; \{out\}\}$- это степень выхода рассматриваемого узла, а $jin\; \{\backslash \; displaystyle\; j\_\; \{in\}\}$- внутренняя степень, $k\; ¯\; in\; \{\backslash \; displaystyle\; \{\backslash \; overline\; \{k\}\}\; \_\; \{in\}\}$- это средняя внутренняя степень его соседей (до которой узел $v\; \{\; \backslash \; displaystyle\; v\}$} имеет край) и $k\; ¯\; out\; \{\backslash \; displaystyle\; \{\backslash \; overline\; \{k\}\}\; \_\; \{out\}\}$- средняя степень отклонения его соседи (от которого узел $v\; \{\backslash \; displaystyle\; v\}$имеет ребро). $\sigma \; qin\; \ne \; 0\; \{\backslash \; displaystyle\; \{\backslash \; sigma\}\; \_\; \{q\}\; ^\; \{in\}\; \backslash \; \backslash \; neq\; 0\}$,$\sigma \; qout\; \ne \; 0\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; \backslash \; sigma\}\; \_\; \{q\}\; ^\; \{out\}\; \backslash \; \backslash \; neq\; 0\}$.

Путем включения условий масштабирования $\sigma \; qin\; \{\backslash \; displaystyle\; \{\backslash \; sigma\}\; \_\; \{q\}\; ^\; \{in\}\}$и $\sigma \; qout\; \{\backslash \; displaystyle\; \{\backslash \; \backslash \; sigma\}\; \_\; \{q\}\; ^\; \{out\}\}$, мы гарантируем, что уравнение локальной ассортативности для направленной сети удовлетворяет условию $rd\; =\; \sum \; i\; =\; 1\; N\; \rho \; d\; \{\backslash \; displaystyle\; r\_\; \{d\}\; =\; \backslash \; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{N\}\; \{\{\backslash \; rho\}\; \_\; \{d\}\}\}$.

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

Рис. 3: Размер n и коэффициент ассортативности r для различных сетей.

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

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

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

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

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

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

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

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