Смешивание паттернов - Mixing patterns

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

Типы смешивания паттернов

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

Очевидно, что конкретные характеристики узлов, задействованные в процессе создания связи между парой, будут формировать паттерны микширования сети. Например, в сети сексуальных отношений можно обнаружить преобладание связей между мужчиной и женщиной, тогда как в сети дружбы могут преобладать сети мужчины-мужчины и женщины-женщины. Таким образом, изучение различных наборов характеристик узлов может выявить интересные сообщества или другие структурные свойства сети. В принципе, для использования этих свойств используются два вида методов. Один основан на аналитических расчетах с использованием методов производящей функции. Другой - числовой и основан на моделировании Монте-Карло для генерации графов.^[1]

В исследовании паттернов микширования в сетях M.E.J. Ньюман начинает с классификации характеристик узлов на две категории. Хотя количество характеристик реальных узлов практически неограничено, они, как правило, подпадают под два заголовка: дискретные и скалярные / топологические. В следующих разделах определяются различия между категориями и приводятся примеры каждой из них. Для каждой категории кратко обсуждаются модели ассортативно смешанных сетей, введенные Ньюманом.

Смешивание на основе дискретных характеристик

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

Для измерения перемешивания сети по дискретным характеристикам Ньюман^[1] определяет количество ${displaystyle e_{ij}}$ быть долей ребер в сети, которые соединяют узлы типа я печатать j (см. рис. 1). В неориентированной сети эта величина симметрична по своим индексам ${displaystyle e_{ij}=e_{ji}}$, а на направленных - асимметричный. Он удовлетворяет правилам сумм

${displaystyle sum _{ij}{e_{ij}=1},quad sum _{j}{e_{ij}=a_{i}},quad sum _{i}{e_{ij}=b_{j}}}$,

куда ${displaystyle a_{i}}$ и ${displaystyle b_{i}}$ - доли каждого типа конца ребра, прикрепленного к узлам типа ${displaystyle i}$. На неориентированных графах, где нет физических различий между концами связи, т.е.концы ребер одного типа, ${displaystyle a_{i}=b_{i}}$.

Затем коэффициент ассортативности, мера силы сходства или несходства между двумя узлами по набору дискретных характеристик может быть определена как:

${displaystyle r={frac {sum _{i}{e_{ii}}-sum _{i}{a_{i}b_{i}}}{1-sum _{i}{a_{i}b_{i}}}}}$

с

${displaystyle r_{min}=-{frac {sum _{i}{a_{i}b_{i}}}{1-sum _{i}{a_{i}b_{i}}}}}$

Эта формула дает ${displaystyle r=0}$ когда нет ассортативного перемешивания, так как ${displaystyle e_{ij}=a_{i}b_{j}}$ в этом случае и ${displaystyle r=1}$ когда сеть идеально ассортативна. Если сеть полностью дезассортативна, т.е. каждое звено соединяет два узла разных типов, то ${displaystyle r=r_{min}}$, которая в целом лежит в диапазоне ${displaystyle -1leq r<0}$. Этот диапазон для ${displaystyle r_{min}}$ подразумевает, что идеально дезассортативная сеть обычно ближе к случайно смешанной сети, чем идеально ассортативная. Когда есть несколько разных типов узлов, то случайное смешивание чаще всего объединяет в пары непохожие узлы, так что сеть кажется в основном дезассортативной. Поэтому целесообразно, чтобы значение ${displaystyle r=0}$ для случайной сети должно быть ближе к таковой для идеально ассортативной сети, чем для идеально ассортативной.

Метод генерирования функций основан на идее определения правильной производящей функции для интересующих нас распределений и извлечения данных, связанных со структурой сети, путем их дифференцирования. Предполагая, что распределение степеней ${displaystyle p_{k}^{(i)}}$ для узлов типа ${displaystyle i}$ и значение матрицы ${displaystyle e_{ij}}$ (а значит, и значения ${displaystyle a_{i}}$ и ${displaystyle b_{i}}$) известны, то можно рассматривать ансамбль всех графов с указанными ${displaystyle p_{k}^{(i)}}$ и ${displaystyle e_{ij}}$ для получения коллективных (макроскопических) характеристик сети. В принципе, производящая функция для ${displaystyle p_{k}^{(i)}}$ и его первый момент дается${displaystyle G_{0}^{(i)}(x_{1},...,x_{n})=sum _{k}p_{k}^{(i)}x^{k}}$, и${displaystyle G_{1}^{(i)}={frac {1}{z_{i}}}{frac {dG_{0}^{(i)}}{dx}}{Bigg |}_{x=1}}$,куда ${displaystyle x_{i}={frac {sum _{j}e_{ij}x_{j}}{sum _{j}e_{ij}}}}$ узел типа ${displaystyle i}$ (${displaystyle r_{i}}$ в номере) и ${displaystyle z_{i}}$ средняя степень для узлов этого типа. Теперь сосредоточимся на интересующих нас дистрибутивах.

Распределение общего числа узлов, достижимых по ребру, которое достигает узла типа ${displaystyle i}$ имеет производящую функцию${displaystyle H_{1}^{(i)}(x)=xG_{1}^{(i)}[H_{1}^{(1)}(x),...,H_{1}^{(n)}(x)]}$. Точно так же распределение количества узлов, доступных из случайно выбранный узел типа ${displaystyle i}$ генерируется${displaystyle H_{0}^{(i)}(x)=xG_{0}^{(i)}[H_{1}^{(1)}(x),...,H_{1}^{(n)}(x)]}$. Теперь мы в состоянии предоставить некоторые свойства сети. Среднее число ${displaystyle s_{i}}$ узлов, достижимых из узла типа ${displaystyle i}$ является

${displaystyle s_{i}={frac {dH_{0}^{(i)}}{dx}}{Bigg |}_{x=1}=1+G_{0}^{(i)'}(1){frac {sum _{j}e_{ij}H_{1}^{(i)'}(1)}{sum _{j}e_{ij}}}}$

Кроме того, если ${displaystyle u_{i}}$ вероятность для узла типа ${displaystyle i}$ (достигается переходом по случайно выбранной ссылке на графике), чтобы не принадлежать к гигантскому кластеру, тогда общая доля ${displaystyle S}$ узлов, составляющих этот кластер, определяется выражением

${displaystyle S=1-sum _{i}{frac {a_{i}}{z_{i}}}G_{0}^{(i)}(u_{1},...,u_{n})}$

Численное моделирование, основанное на методах Монте-Карло, похоже, согласуется с аналитическими результатами, полученными по формулам, описанным выше.

Смешивание по скалярным или топологическим характеристикам

Скалярные характеристики узла - это количественные характеристики. Они могут быть непрерывными или дискретными порядковыми переменными, например счетчиками. Возраст, пожалуй, самый простой пример, хотя интеллект и чистый доход - другие очевидные возможности. Некоторые топологические особенности сети также могут использоваться для изучения перемешивания по скалярным свойствам. В частности, степень узла часто является очень важной характеристикой в ​​схемах смешивания сетей.^[2] Топологические скалярные функции очень полезны, потому что, в отличие от других мер, они всегда доступны. Иногда их используют в качестве прокси для реальной «общительности».^[1]

Для измерения ассортативности скалярных переменных, аналогично дискретному случаю (см. Выше), можно определить коэффициент ассортативности. Его можно измерить стандартным Корреляции Пирсона, как демонстрирует Ньюман.^[1] На рис. 2, например, расчет коэффициента корреляции Пирсона дает r = 0,574. Это указывает на довольно сильную связь между возрастом мужа и жены на момент вступления в брак.

Альтернативный коэффициент может быть вычислен для измерения смешения по степени узлов. Новичок ^[1] выводит выражение, которое оказывается

${displaystyle r={frac {sum _{jk}jk(e_{jk}-q_{j}q_{k})}{sigma _{q}^{2}}}}$ для ненаправленной сети. В этой формуле, если ${displaystyle p_{k}}$ относится к распределению степеней графа (т. е. вероятность того, что узел имеет степень k) тогда ${displaystyle q_{k}={frac {(k+1)p_{k+1}}{z}}}$. Имеется в виду избыточная степень узла или количество других ребер, кроме текущего исследуемого. В z относится к средней степени в сети, и ${displaystyle sigma _{q}}$ стандартное отклонение распределения ${displaystyle q_{k}}$. Для направленной сети эквивалентное выражение имеет вид${displaystyle r={frac {sum _{jk}jk(e_{jk}-q_{j}^{in}q_{k}^{out})}{sigma _{in}sigma _{out}}}}$.

Эта корреляция положительна, когда узлы ассортативны по степени, и отрицательна, когда сеть неассортативна. Таким образом, мера отражает общее представление о паттернах микширования в сети. Более подробный анализ этой темы см. В статье о ассортативность.

Метод создания функций по-прежнему применим и для этого случая, но вычисляемые функции редко можно вычислить в замкнутой форме. Таким образом, численное моделирование кажется единственным способом получить интересный результат. Используемая техника - снова метод Монте-Карло. В случае сетей с сила закона распределение степеней ${displaystyle p_{k}sim k^{- au }}$, ${displaystyle q_{k}}$ имеет расходящееся среднее, если только ${displaystyle au >3}$, что случается редко.^[3] Вместо этого экспоненциально усеченное степенное распределение${displaystyle p_{k}={frac {k^{- au }mathrm {e} ^{-k/kappa }}{mathrm {Li} _{ au }(mathrm {e} ^{-1/kappa })}} mathrm {for} kgeq 1}$ дает распределение избыточной степени типа ${displaystyle q_{k}sim (k+1)^{1- au }mathrm {e} ^{-(k+1)/kappa }}$. Результаты для этого случая приведены ниже.

1) Положение фазового перехода, при котором появляется гигантский кластер, смещается в сторону более высоких значений ${displaystyle kappa }$ как ценность ${displaystyle r}$ уменьшается. То есть, чем более ассортативной является сеть, тем ниже будет порог плотности краев для появления гигантского кластера.

2) Размер гигантского кластера в пределе больших ${displaystyle kappa }$ для ассортативно-смешанного графа меньше, чем для нейтрального и дизассортативного.

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

Замечательный результат о зависимости устойчивости сети от перемешивания узлов можно объяснить следующим образом. Согласно их определению, узлы высокой степени в ассортативных сетях, как правило, образуют среди них основную группу. Такая основная группа обеспечивает надежность сети, концентрируя все очевидные целевые узлы вместе в одной части графа. Удаление этих высокоуровневых узлов по-прежнему является одним из наиболее эффективных способов разрушения сетевых подключений, но он менее эффективен (по сравнению с нейтральными сетями), потому что, удаляя их все из одной и той же части графа, мы не можем атаковать другие части. Если эти другие части сами просачиваются, то гигантский кластер будет существовать, даже если узлы наивысшей степени исчезнут. С другой стороны, неассортативно смешанная сеть особенно восприимчива к удалению узлов высокой степени, потому что эти узлы разбросаны по сети далеко друг от друга, так что атака на них подобна атаке всех частей сети одновременно.

Примеры и приложения

Обычное применение моделей смешивания - изучение передачи болезней. Например, во многих исследованиях смешивание использовалось для изучения распространения ВИЧ / СПИДа и других заразных заболеваний.^[4][5][6] В этих статьях обнаруживается сильная связь между паттернами смешивания и скоростью распространения болезней. Результаты также могут быть использованы для моделирования роста сети в реальном мире, например,^[7] или найдите сообщества в сетях.

Рекомендации

1. Ньюман, М. Э. Дж. (27 февраля 2003 г.). «Смешивание паттернов в сетях». Физический обзор E. 67 (2): 026126. arXiv:cond-mat / 0209450. Bibcode:2003PhRvE..67b6126N. Дои:10.1103 / Physreve.67.026126. ISSN  1063-651X. PMID  12636767.
2. Ньюман, М. Э. Дж. (2002-10-28). «Ассортативное смешение в сетях». Письма с физическими проверками. 89 (20): 208701. arXiv:cond-mat / 0205405. Bibcode:2002ПхРвЛ..89т8701Н. Дои:10.1103 / Physrevlett.89.208701. ISSN  0031-9007. PMID  12443515.
3. Альберт, Река; Барабаши, Альберт-Ласло (30 января 2002 г.). «Статистическая механика сложных сетей». Обзоры современной физики. 74 (1): 47–97. arXiv:cond-mat / 0106096. Bibcode:2002РвМП ... 74 ... 47А. Дои:10.1103 / revmodphys.74.47. ISSN  0034-6861.
4. Арал, С.О; Хьюз, Дж. П; Стоунер, Б. Уиттингтон, Вт; Хэндсфилд, H H; Андерсон, Р. М.; Холмс, К. К. (1999). «Модели полового смешения в распространении гонококковых и хламидийных инфекций». Американский журнал общественного здравоохранения. Американская ассоциация общественного здравоохранения. 89 (6): 825–833. Дои:10.2105 / ajph.89.6.825. ISSN  0090-0036. ЧВК  1508665. PMID  10358670.
5. Гарнетт, Джеффри П .; Хьюз, Джеймс П .; Андерсон, Рой М .; Стоунер, Брэдли П.; Арал, Севги О .; и другие. (1996). «Модели сексуального смешения пациентов, посещающих клиники болезней, передающихся половым путем». Заболевания, передающиеся половым путем. Ovid Technologies (Wolters Kluwer Health). 23 (3): 248–257. Дои:10.1097/00007435-199605000-00015. ISSN  0148-5717. PMID  8724517.
6. Форд, Кэтлин; Sohn, Woosung; Лепковски, Джеймс (2002). «Американские подростки: сексуальные модели смешивания, партнеры-мосты и одновременность». Заболевания, передающиеся половым путем. Ovid Technologies (Wolters Kluwer Health). 29 (1): 13–19. Дои:10.1097/00007435-200201000-00003. ISSN  0148-5717. PMID  11773873.
7. Катандзаро, Микеле; Калдарелли, Гвидо; Пьетронеро, Лучано (2004). «Рост социальной сети с ассортативным перемешиванием». Physica A: Статистическая механика и ее приложения. Elsevier BV. 338 (1–2): 119–124. Bibcode:2004PhyA..338..119C. Дои:10.1016 / j.physa.2004.02.033. ISSN  0378-4371.