Ассортативность (Gvvkjmgmnfukvm,)

Перейти к навигации Перейти к поиску

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

Коэффициент ассортативности задаётся формулой: , где это распределение остаточных степеней (remaining degree). Оно фиксирует число рёбер, исходящих из узла, за исключением одного ребра, соединяющего пару. Это распределение получается из распределения степеней как . Наконец, обозначает совместное распределение остаточных степеней двух вершин. Это количество симметрично для ненаправленного графа и следует правилам суммирования: и .

В направленном графе ассортативность входящих степеней (in-assortativity, ) и ассортативность исходящих степеней (out-assortativity, ) измеряют тенденцию узлов соединяться с другими узлами, имеющими схожие с ними входящие и исходящие степени, соответственно.[4][5] Развивая это, можно рассмотреть четыре типа ассортативности (смотрите[4][6]). Принимая условные обозначения той статьи, возможно определить четыре метрики: , , , and . Пусть это одна из словесных пар in/out (например, ). Пусть это число рёбер в сети. Предположим, что мы пронумеровали рёбра сети как . Дано ребро с номером , пусть  — это -степень источника (например, хвоста) узловой вершины ребра, а  — это -степень целевого узла (то есть головы) -го ребра. Мы обозначим средние значения чертой, так что и  — это средние -степень источников и -степень целей, соответственно; средние берутся по рёбрам сети. Наконец, мы имеем:

Связность соседей (Neighbor connectivity)

[править | править код]

Другой способ оценить корреляцию степеней это изучить свойства , или средней степени соседей узла со степенью k.[7] Формально это определяется так: , где  — это условная вероятность, что ребро узла со степенью k указывает на узел со степенью k'. Если эта функция возрастает, то сеть ассортативная, поскольку она показывает, что узлы с высокими степенями соединяются, в среднем, с узлами высоких степеней. Напротив, если функция убывает, то сеть дизассортативная, поскольку узлы высоких степеней имеют тенденцию соединяться с узлами более низкой степени.

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

[править | править код]

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

Где  — это избыточная степень (excess degree) конкретного узла,  — это средняя избыточная степень его соседей, а M — это число связей в сети.

Соответственно, локальная ассортативность в направленных сетях[5] — это вклад узла в направленную ассортативность (directed assortativity) сети. Вклад узла в ассортативность направленной сети определяется как:

Где  — это исходящая степень (out-degree) рассматриваемого узла,  — входящая степень (in-degree),  — средняя входящая степень его соседей (в какие узлы у }-го узла есть ребро) и  — это средняя исходящая степень его соседей (из каких узлов у -го узла есть ребро). ,.

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

Далее, в зависимости от того, рассматривается ли входящая степень или исходящая, возможно определения локальную входящую ассортативность (local in-assortativity) и локальную исходящую ассортативность (local out-assortativity) как соответствующие меры локальной ассортативности в направленной сети.[5]

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

[править | править код]

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

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

Приложения

[править | править код]

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

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

[править | править код]

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

Примечания

[править | править код]
  1. Newman, M. E. J. (27 February 2003). "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. 1 2 3 Newman, M. E. J. (28 October 2002). "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. 1 2 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. 1 2 3 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. (11 March 2010). "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.