Асортативність, або асортативне змішування, — це перевага вузлів мережі приєднуватися до інших, які є подібними певним чином. Хоча конкретна міра подібності може відрізнятися, теоретики мереж часто досліджують асортативність з точки зору ступеня вузла. Додавання цієї характеристики до мережевих моделей точніше наближає поведінку багатьох реальних мереж.

Кореляції між вузлами подібного ступеня часто зустрічаються у схемах змішування багатьох спостережуваних мереж. Наприклад, у соціальних мережах вузли, як правило, пов'язані з іншими вузлами з подібними значеннями ступеня. Ця тенденція називається асортативним змішуванням або асортативністю.

З іншого боку, технологічні та біологічні мережі зазвичай демонструють дисартативне змішування або дисартативність, оскільки вузли високого ступеня, як правило, приєднуються до вузлів низького ступеня.

Вимірювання

Асортативність часто операціоналізується як кореляція між двома вузлами. Однак існує кілька способів фіксації такої кореляції. Двома найпоширенішими мірами є коефіцієнт асортативності та зв'язність сусідів. Ці міри описані більш детально нижче.

Коефіцієнт асортативності Коефіцієнт асортативності – це коефіцієнт кореляції Пірсона за ступенем між парами зв'язаних вузлів. Додатні значення вказують на кореляцію між вузлами подібного ступеня, тоді як від'ємні значення вказують на зв'язки між вузлами різного ступеня.

Загалом, лежить між і Коли , кажуть, що мережа має ідеальні асортативні моделі змішування, коли мережа не є асортативною, тоді як на мережа повністю дезасортативна.

Для неорієнтованих мереж коефіцієнт асортиментальності можна записати як

.

У цьому виразі індекси і позначають можливі значення залишкового степеня, який визначається як степінь вузла мінус один (тобто кількість ребер, що залишають вузол, відмінний від ребра, що розглядається на даний момент).

Кількість ​ — це ймовірність того, що випадково вибраний кінець ребра буде приєднаний до вузла із залишковим степенем . Оскільки вузли з вищим ступенем пропорційно частіше зустрічаються серед кінців ребер, ​ виводиться з розподілу ступенів ​ таким чином:

.

Термін — це спільний розподіл ймовірностей решти ступенів на двох кінцях випадково вибраного ребра. Він отримується шляхом дослідження всіх ребер у мережі, підраховуючи, як часто пара відбувається решта ступенів, та нормалізація цих показників таким чином, щоб

.

За конструкцією, маргінальні частини відтворити розподіл

.

З урахуванням цих визначень, наведений вище вираз є саме коефіцієнтом кореляції Пірсона для решти ступенів на кінцевих точках ребер.

У спрямованому графі асортативність за вхідним степенем () та асортативність за вихідним степенем () характеризують схильність вузлів з’єднуватися з іншими вузлами, які мають відповідно подібні вхідні та вихідні степені. Узагальнюючи цей підхід, можна розглядати чотири типи асортативності (див. ). Використовуючи позначення, запропоновані в цій статті, можна визначити чотири метрики: , , , та .

Нехай — одна з пар, утворених вхідним і вихідним степенями (наприклад,).

Нехай E — кількість ребер у мережі. Позначимо ребра мережі числами . Для заданого ребра нехай — це α-степінь початкового вузла (тобто вузла, з якого виходить ребро), а — -степінь кінцевого вузла (тобто вузла, у який входить ребро ). Середні значення позначатимемо рискою зверху, тому та є середніми значеннями відповідно α-степеня початкових вузлів і -степеня кінцевих вузлів; усереднення виконується за всіма ребрами мережі. Врешті, маємо:

Зв'язок із сусідами Іншим способом визначення ступеня кореляції є вивчення властивостей , або середній степінь сусідів вузла зі ступенем k. Цей термін формально визначається як: , де — умовна ймовірність того, що ребро вузла ступеня k вказує на вузол ступеня k'. Якщо ця функція зростає, мережа є асортативною, оскільки вона показує, що вузли високого ступеня в середньому з'єднуються з вузлами високого ступеня. З іншого боку, якщо функція спадає, мережа є десартативною, оскільки вузли високого ступеня прагнуть з'єднуватися з вузлами нижчого ступеня.

Локальна асортативність В асортативних мережах можуть бути вузли, які є дисортативними, і навпаки. Для виявлення таких аномалій у мережах потрібна локальна асортативна міра . Локальна асортативність визначається як внесок кожного вузла в асортативність мережі. Локальна асортативність у неорієнтованих мережах визначається як,

Де є надлишковим ступенем певного вузла та – середній ступінь надлишку його сусідів, а M – кількість ланок у мережі.

Відповідно, локальна асортиментальність для спрямованих мереж – це внесок вузла в спрямовану асортиментальність мережі. Внесок вузла в асортиментальність спрямованої мережі визначається як,

Де – це вихідний ступінь розглянутого вузла, а є внутрішнім ступенем, – середній ступінь входження його сусідів (до якого вузла } має ребро) та – середній ступінь виходу його сусідів (з якого вузла має перевагу). , .

Включивши умови масштабування і , ми гарантуємо, що рівняння локальної асортиментальності для спрямованої мережі задовольняє умову .

Крім того, залежно від того, чи розглядається розподіл за внутрішнім чи зовнішнім ступенем, можна визначити локальну внутрішню асортиментальність та локальну зовнішню асортиментальність як відповідні міри локальної асортиментальності в спрямованій мережі.

Асортативні моделі змішування реальних мереж Було досліджено асортативні властивості моделей різноманітних мереж реального світу. Тоді як моделі соціальних мереж зазвичай демонструють асортативне змішування, моделі технологічних і біологічних мереж, як правило, мають дисасортативний характер. Було висунуто припущення, що це пов’язано з тим, що більшість мереж мають тенденцію еволюціонувати, якщо на них не впливають інші обмеження, до стану максимальної ентропії, який зазвичай є дисасортативним.

У таблиці також наведено значення r, розраховане аналітично для двох моделей мереж:

випадковий граф Ердеша та Реньї Модель БА (модель Барабаші-Альберта)

У моделі ER, оскільки ребра розміщуються випадковим чином незалежно від ступеня вершини, з цього випливає, що r = 0 в межах великого розміру графа. Безмасштабна модель БА також має цю властивість. Для моделі БА в окремому випадку m = 1 (де кожен вхідний вузол приєднується лише до одного з існуючих вузлів з ймовірністю, пропорційною ступеню), відомий більш точний результат: як (кількість вершин) прямує до нескінченності, r наближається до 0 з тією ж швидкістю, що й .

Застосування Властивості асортативності є важливими в епідеміології, оскільки вони можуть допомогти зрозуміти механізми поширення захворювань або впровадження методів лікування. Наприклад, видалення частини вершин мережі може відповідати лікуванню, вакцинації або карантину окремих осіб чи клітин. Оскільки соціальні мережі демонструють асортативне змішування, захворювання, що вражають вузли з високим ступенем, імовірно, поширюватимуться на інші вузли з високим ступенем. Натомість у клітинній мережі, яка як біологічна мережа, ймовірно, є дисасортативною, стратегії вакцинації, спрямовані саме на вузли з високим ступенем, можуть швидко призвести до руйнування епідемічної мережі.

Структурна дезасортативність Базова структура мережі може призвести до того, що ці показники демонструють дизасортативність, яка не є репрезентативною для будь-якого основного асортативного чи дизасортативного змішування. Необхідно бути особливо обережними, щоб уникнути цієї структурної дизасортативності.

Див. також

Пільгове прикріплення Гомофілія

Посилання