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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Измерение[править | править код]

Рис. 1: Безмасштабные сети с различными степенями ассортативности: (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(NearestNeighbor) distribution for two real-world networks.gif
Рис. 2: knn-распределение для двух реальных сетей. Верхняя сеть (a) дизассортативна, поскольку наклон отрицательный. С другой стороны, (b) ассортативна, поскольку наклон положительный.[7]

Другой способ оценить корреляцию степеней это изучить свойства , или средней степени соседей узла со степенью k.[8] Формально это определяется так: , где – это условная вероятность, что ребро узла со степенью k указывает на узел со степенью k'. Если эта функция возрастает, то сеть ассортативная, поскольку она показывает, что узлы с высокими степенями соединяются, в среднем, с узлами высоких степеней. Напротив, если функция убывает, то сеть дизассортативная, поскольку узлы высоких степеней имеют тенденцию соединяться с узлами более низкой степени. Функцию можно нарисовать на графике (смотрите Рис. 2), чтобы изобразить общую закономерность ассортативности в сети.

Локальная ассортативность[править | править код]

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

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

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

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

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

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

Паттерны ассортативного смешивания в реальных сетях[править | править код]

Файл:Size (n) and assortativity coefficient (r) for various networks.jpg
Рис. 3: Размер n и коэффициент ассортативности r для различных сетей.[2]

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

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

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

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

Приложения[править | править код]

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

Структурная дизассортативность[править | править код]

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

См. также[править | править код]

Ссылки[править | править код]

  1. Newman, M. E. J. (27 February 2003). “Mixing patterns in networks”. Physical Review E. American Physical Society (APS). 67 (2): 026126. arXiv:cond-mat/0209450. Bibcode:2003PhRvE..67b6126N. DOI:10.1103/physreve.67.026126. ISSN 1063-651X.
  2. 1 2 3 4 Newman, M. E. J. (28 October 2002). “Assortative Mixing in Networks”. Physical Review Letters. American Physical Society (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.; Sokolov, I.M. (2005). “Changing correlations in networks: assortativity and dissortativity”. Acta Physica Polonica B. 36 (5): 1431.
  4. 1 2 Braha, D.; Bar-Yam, Y. (2007). “The statistical mechanics of complex product development: Empirical and analytical results”. 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. Lee, Sang Hoon; Kim, Pan-Jun; Jeong, Hawoong (4 January 2006). “Statistical properties of sampled networks”. Physical Review E. American Physical Society (APS). 73 (1): 016102. arXiv:cond-mat/0505232. DOI:10.1103/physreve.73.016102. ISSN 1539-3755.
  8. Pastor-Satorras, Romualdo; Vázquez, Alexei; Vespignani, Alessandro (2001). “Dynamical and Correlation Properties of the Internet”. Physical Review Letters. American Physical Society (APS). 87 (25): 258701. arXiv:cond-mat/0105161. Bibcode:2001PhRvL..87y8701P. DOI:10.1103/physrevlett.87.258701. ISSN 0031-9007. PMID 11736611.
  9. 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.
  10. 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. American Physical Society (APS). 104 (10): 108702. arXiv:1002.3286. Bibcode:2010PhRvL.104j8702J. DOI:10.1103/physrevlett.104.108702. ISSN 0031-9007. PMID 20366458.