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

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

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

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

Измерение

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

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

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

Коэффициент ассортативности — это коэффициент корреляции Пирсона степени между парами соединённых узлов.[2] Положительные значения 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}})}$) измеряют тенденцию узлов соединяться с другими узлами, имеющими схожие с ними входящие и исходящие степени, соответственно.[4][5] Развивая это, можно рассмотреть четыре типа ассортативности (смотрите[4][6]). Принимая условные обозначения той статьи, возможно определить четыре метрики: ${\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.[7] Формально это определяется так: ${\displaystyle \langle k_{nn}\rangle =\sum _{k'}{k'P(k'|k)}}$, где ${\displaystyle P(k'|k)}$ — это условная вероятность, что ребро узла со степенью k указывает на узел со степенью k'. Если эта функция возрастает, то сеть ассортативная, поскольку она показывает, что узлы с высокими степенями соединяются, в среднем, с узлами высоких степеней. Напротив, если функция убывает, то сеть дизассортативная, поскольку узлы высоких степеней имеют тенденцию соединяться с узлами более низкой степени.

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

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

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

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

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

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

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

Приложения

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

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

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

См. также

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

Примечания

1. Newman, M. E. J. (2003-02-27). Mixing patterns in networks. Physical Review E. 67 (2). American Physical Society (APS): 026126. arXiv:cond-mat/0209450. Bibcode:2003PhRvE..67b6126N. doi:10.1103/physreve.67.026126. ISSN 1063-651X.
2. Newman, M. E. J. (2002-10-28). Assortative Mixing in Networks. Physical Review Letters. 89 (20). American Physical Society (APS): 208701. arXiv:cond-mat/0205405. Bibcode:2002PhRvL..89t8701N. doi:10.1103/physrevlett.89.208701. ISSN 0031-9007. PMID 12443515.
3. Xulvi-Brunet, R.; Sokolov, I.M. (2005). Changing correlations in networks: assortativity and dissortativity. Acta Physica Polonica B. 36 (5): 1431. Архивировано 9 мая 2021. Дата обращения: 9 мая 2021.
4. Braha, D.; Bar-Yam, Y. (2007). «The statistical mechanics of complex product development: Empirical and analytical results» Архивная копия от 14 февраля 2021 на Wayback Machine. Management Science. 53(7): 1127—1145.
5. Piraveenan, M.; Prokopenko, M.; Zomaya, A.Y. (2008). Assortative mixing in directed biological networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics. 9 (1): 66–78. doi:10.1109/TCBB.2010.80. PMID 20733240.
6. Foster, Jacob; David V. Foster; Peter Grassberger; Maya Paczuski (June 2010). Edge direction and the structure of networks. Proceedings of the National Academy of Sciences. 107 (24): 10815–20. arXiv:0908.4288. Bibcode:2010PNAS..10710815F. doi:10.1073/pnas.0912671107. PMC 2890716. PMID 20505119.
7. Pastor-Satorras, Romualdo; Vázquez, Alexei; Vespignani, Alessandro (2001). Dynamical and Correlation Properties of the Internet. Physical Review Letters. 87 (25). American Physical Society (APS): 258701. arXiv:cond-mat/0105161. Bibcode:2001PhRvL..87y8701P. doi:10.1103/physrevlett.87.258701. ISSN 0031-9007. PMID 11736611.
8. Piraveenan, M.; Prokopenko, M.; Zomaya, A.Y. (2008). Local assortativeness in scale-free networks. EPL (Europhysics Letters). 84 (2): 28002. Bibcode:2008EL.....8428002P. doi:10.1209/0295-5075/84/28002.
9. Johnson, Samuel; Torres, Joaquín J.; Marro, J.; Muñoz, Miguel A. (2010-03-11). Entropic Origin of Disassortativity in Complex Networks. Physical Review Letters. 104 (10). American Physical Society (APS): 108702. arXiv:1002.3286. Bibcode:2010PhRvL.104j8702J. doi:10.1103/physrevlett.104.108702. ISSN 0031-9007. PMID 20366458.