Русская Википедия:Ассортативность
Шаблон:Наука о сетях Ассортати́вность, или ассортативное смешивание, это предпочтение узлов сети присоединяться к другим узлам, которые каким-либо образом похожи на них. Хотя конкретная мера сходства может различаться, теоретики сетей часто исследуют ассортативность в терминах степеней узла.[1] Добавление этой характеристики в сетевые модели часто позволяет более точно аппроксимировать поведение многих реальных сетей.
Корреляции между узлами схожих степеней часто обнаруживаются в паттернах смешивания многих наблюдаемых сетей. Например, в социальных сетях узлы имеют тенденцию соединяться с другими узлами со схожими значениями степеней. Эта тенденция обозначается как ассортативное смешивание, или ассортативность. С другой стороны, в технологических и биологических сетях типично наблюдается дизассортативное смешивание, или дизассортативность, поскольку узлы с высокими степенями имеют тенденцию присоединяться к узлам с низкими степенями.[2]
Измерение
Ассортативность часто на практике реализуется как корреляция между двумя узлами. Тем не менее, есть несколько способов оценить такую корреляцию. Две наиболее значимые меры это коэффициент ассортативности и neighbor connectivity (связность соседей). Эти меры более детально рассматриваются ниже.
Коэффициент ассортативности
Коэффициент ассортативности это коэффициент корреляции Пирсона степени между парами соединённых узлов.[2] Положительные значения r обозначают корреляцию между узлами схожих степеней, а отрицательные значения обозначают отношения между узлами разных степеней. В целом, r лежит между −1 и 1. Когда r = 1, о сети говорят, что в ней наблюдаются истинные паттерны ассортативного смешивания (perfect assortative mixing patterns), когда r = 0 сеть неассортативна, а при r = −1 сеть полностью дизассортативна.
Коэффициент ассортативности задаётся формулой: <math>r = \frac{\sum_{jk}{jk (e_{jk} - q_j q_k)}}{\sigma_{q}^{2}}</math>, где <math>q_{k}</math> это распределение остаточных степеней (remaining degree). Оно фиксирует число рёбер, исходящих из узла, за исключением одного ребра, соединяющего пару. Это распределение получается из распределения степеней <math>p_{k}</math> как <math>q_{k} = \frac{(k+1)p_{k+1}}{\sum_{j \geq 1} j p_j}</math>. Наконец, <math>e_{jk}</math> обозначает совместное распределение остаточных степеней двух вершин. Это количество симметрично для ненаправленного графа и следует правилам суммирования: <math>\sum_{jk}{e_{jk}} = 1\,</math> и <math>\sum_{j}{e_{jk}} = q_{k}\,</math>.
В направленном графе ассортативность входящих степеней (in-assortativity, <math>r( \text{in}, \text{in})</math>) и ассортативность исходящих степеней (out-assortativity, <math>r( \text{out}, \text{out})</math>) измеряют тенденцию узлов соединяться с другими узлами, имеющими схожие с ними входящие и исходящие степени, соответственно.[4][5] Развивая это, можно рассмотреть четыре типа ассортативности (смотрите [4][6]). Принимая условные обозначения той статьи, возможно определить четыре метрики: <math>r( \text{in}, \text{in})</math>, <math>r( \text{in}, \text{out})</math>, <math>r( \text{out}, \text{in})</math>, and <math>r( \text{out}, \text{out})</math>. Пусть <math>(\alpha,\beta)</math> это одна из словесных пар in/out (например, <math>(\alpha,\beta)=(\text{out},\text{in})</math>). Пусть <math>E</math> это число рёбер в сети. Предположим, что мы пронумеровали рёбра сети как <math>1,\ldots,E</math>. Дано ребро с номером <math>i</math>, пусть <math>j^{\alpha}_i</math> – это <math>\alpha</math>-степень источника (например, хвоста) узловой вершины ребра, а <math>k^{\beta}_i</math> – это <math>\beta</math>-степень целевого узла (т.е. головы) <math>i</math>-го ребра. Мы обозначим средние значения чертой, так что <math>\bar{j^\alpha}</math> и <math> \bar{k^\beta}</math> – это средние <math>\alpha</math>-степень источников и <math>\beta</math>-степень целей, соответственно; средние берутся по рёбрам сети. Наконец, мы имеем:
<math> r(\alpha,\beta)=\frac{\sum_i (j^\alpha_i-\bar{j^\alpha})(k^\beta_i-\bar{k^\beta})}{ \sqrt{\sum_i (j^\alpha_i-\bar{j^\alpha})^2} \sqrt{\sum_i (k^\beta_i-\bar{k^\beta})^2} }. </math>
Связность соседей (Neighbor connectivity)
Другой способ оценить корреляцию степеней это изучить свойства <math>\langle k_{nn} \rangle</math>, или средней степени соседей узла со степенью k.[8] Формально это определяется так: <math>\langle k_{nn} \rangle = \sum_{k'}{k'P(k'|k)}</math>, где <math>P(k'|k)</math> – это условная вероятность, что ребро узла со степенью k указывает на узел со степенью k'. Если эта функция возрастает, то сеть ассортативная, поскольку она показывает, что узлы с высокими степенями соединяются, в среднем, с узлами высоких степеней. Напротив, если функция убывает, то сеть дизассортативная, поскольку узлы высоких степеней имеют тенденцию соединяться с узлами более низкой степени. Функцию можно нарисовать на графике (смотрите Рис. 2), чтобы изобразить общую закономерность ассортативности в сети.
Локальная ассортативность
В ассортативных сетях могут быть дизассортативные узлы, и наоборот. Мера локальной ассортативности[9] требуется для выявления таких аномалий в сетях. Локальная ассортативность определяется как вклад, который каждый узел делает в ассортативность сети. Локальная ассортативность в ненаправленных сетях определяется как:
<math> \rho = \frac{j\ \left(j+1\right)\left(\overline{k}-\ {\mu }_q\right)}{2M{\sigma }^2_q} </math>
Где <math>j</math> – это избыточная степень (excess degree) конкретного узла, <math>\overline{k}</math> – это средняя избыточная степень его соседей, а M – это число связей в сети.
Соответственно, локальная ассортативность в направленных сетях[5] – это вклад узла в направленную ассортативность (directed assortativity) сети. Вклад узла в ассортативность направленной сети <math>r_d</math> определяется как: <math> {\rho }_d=\ \frac{{j_{out}}^2\left({\overline{k}}_{in}-\ {\mu }^{in}_q\right)+\ {j_{in}}^2\left({\overline{k}}_{out}-\ {\mu }^{out}_q\right)}{2\ M{\sigma }^{in}_q{\sigma }^{out}_q} </math>
Где <math>j_{out}</math> – это исходящая степень (out-degree) рассматриваемого узла, <math>j_{in}</math> – входящая степень (in-degree), <math>{\overline{k}}_{in}</math> – средняя входящая степень его соседей (в какие узлы у <math>v</math>}-го узла есть ребро) и <math>{\overline{k}}_{out}</math> – это средняя исходящая степень его соседей (из каких узлов у <math>v</math>-го узла есть ребро). <math>{\sigma }^{in}_q\ \ne 0</math>,<math>\ {\ \sigma }^{out}_q\ \ne 0</math>.
Включая масштабирующие члены <math>{\sigma }^{in}_q</math> и <math>{\ \sigma }^{out}_q</math>, мы обеспечиваем, что уравнение локальной ассортативности для направленной сети удовлетворяет условию <math>r_d=\ \sum^N_{i=1}{{\rho }_d}</math>.
Далее, в зависимости от того, рассматривается ли входящая степень или исходящая, возможно определения локальную входящую ассортативность (local in-assortativity) и локальную исходящую ассортативность (local out-assortativity) как соответствующие меры локальной ассортативности в направленной сети.[5]
Паттерны ассортативного смешивания в реальных сетях
Исследованы ассортативные паттерны для множества сетей реального мира. Например, на Рис. 3 перечислены значения r для нескольких сетей. Заметим, что социальные сети (первые пять строк) имеют очевидное ассортативное смешивание. С другой стороны, все технологические и биологические сети (средние шесть строк) оказываются дизассортативными. Предполагается, что это из-за того, что большинство сетей имеют тенденцию развиваться, если не ограничены иным способом, в сторону состояния с максимальной энтропией — которое обычно дизассортивно.[10]
В таблице также указаны значения r, рассчитанные аналитически для двух моделей сетей:
- случайный граф Эрдёша — Реньи;
- модель Барабаши — Альберт.
В модели Эрдёша-Реньи, поскольку рёбра располагаются случайно, вне зависимости от степеней вершин, в результате получается, что r = 0 в пределе большого размера графа. Безмасштабная модель Барабаши-Альберт также сохраняет это свойство. Для модели Барабаши-Альберт в особом случае при m=1 (где каждый новый узел присоединяется только к одному из существующих узлов с вероятностью, пропорциональной степени) получаем <math>r \to 0</math> как <math>(\log^2 N)/N</math> в пределе большого <math>N</math>.[2]
Приложения
Свойства ассортативности полезны в области эпидемиологии, поскольку они помогают понимать распространение заболеваний или лекарств. Например, удаление части вершин сети может соответствовать исцелению, вакцинации или помещению в карантин индивидов или клеток. Поскольку в социальных сетях наблюдается ассортативное смешивание, заболевания, поражающие индивидов с высокими степенями с большей вероятностью распространятся к другим узлам с высокими степенями. Напротив, в клеточных сетях — которые, как биологические сети, вероятно, дизассортивны — стратегии вакцинации, специфично направленные на вершины высоких степеней, могут быстро уничтожить эпидемическую сеть.
Структурная дизассортативность
Шаблон:Main Базовая структура сети может привести к тому, что эти показатели будут указывать на дизассортативность, не соответствующую реальному ассортативному или дизассортативному смешиванию. Особая осторожность должна быть предпринята, чтобы избежать структурной дизассортативности.
См. также
Ссылки
- ↑ Шаблон:Cite journal
- ↑ 2,0 2,1 2,2 2,3 Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ 4,0 4,1 Braha, D.; Bar-Yam, Y. (2007). “The statistical mechanics of complex product development: Empirical and analytical results” Шаблон:Wayback. Management Science. 53(7): 1127-1145.
- ↑ 5,0 5,1 5,2 Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
_distribution_for_two_real-world_networks.gif){kind=link}
_and_assortativity_coefficient_(r)_for_various_networks.jpg){kind=link}