Складні мережі

Мережа інтернету (IP-адреси є вузлами) є складною мережею.

Складні мережі (Шаблон:Lang-en) — мережі (графи), що володіють нетривіальними топологічними властивостями. Складні мережі широко поширені у природі.

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

Так відносини між людьми в групі (див. соціальна мережа), відносини між фірмами, комп'ютерні мережі, Веб, відносини між генами в ДНК — все це приклади мереж.

Топологічні властивості цих мереж (див. топологія), що розглядаються абстрактно від їх фізичної природи, але істотно визначають функціонування мереж, і становлять предмет дослідження комплексних мереж.

Основні характеристики складних мереж

Орієнтовані і неорієнтовані мережі

Кожен вузол мережі може бути пов'язаний з іншими вузлами певним числом зв'язків. Зв'язки між вузлами можуть мати напрямок. В цьому випадку мережа називається орієнтованою (Шаблон:Lang-en). Якщо мережа складається із вузлів, що пов'язані між собою симетричиними зв'язками, то вона називається неорієнтованою (Шаблон:Lang-en). Наприклад, Веб це орієнтована мережа, а інтернет це неорієнтована мережа. Іноді питання про орієнтованість мережі не настільки тривіальне. Наприклад, відносини між людьми. Якщо вважати що зв'язок існує, якщо дві особи є близькими друзями, то мережа буде неорієнтованою. Якщо вважати що зв'язок існує, якщо одна особа вважає себе другом іншої, то утворена мережа буде орієнтованою.

Розподіл ступенів вузлів (Шаблон:Lang-en)

Число зв'язків вузла будемо називати ступенем (Шаблон:Lang-en) вузла. Для орієнтованих мереж розрізняють вихідні і вхідні ступеня вузла (Шаблон:Lang-en та iШаблон:Lang-en). Розподіл ступенів вузлів є важливою характеристикою складної мережі. Більшість складних мереж мають близький до степеневого закону розподіл ступенів вузлів з показником ступеня між 2 і 3.

Діаметр мережі

Мінімальне число зв'язків, яке необхідно подолати, щоб потрапити з вузла у вузол, називається відстанню між вузлами. Усереднена відстань між усіма парами вузлів мережі, для яких існує шлях переходу з одного в інший, називається середньою відстанню між вузлами (або діаметром мережі) $d$. Для більшості комплексних мереж $d\sim \log (N)$, де $N$ — кількість вузлів у мережі.

Кластерний коефіцієнт

Будемо називати два вузли сусідніми, якщо існує зв'язок між ними. Для комплексних мереж характерно, що два вузли, які сусідні до якого-небудь вузла, часто також є сусідами між собою. Щоб охарактеризувати це явище і був запропонований кластерний коефіцієнт $C_i$ вузла $i$. Припустимо, що вузол має ступінь $k_i$, це означає, що у нього $k_i$ сусідів і між ними може бути максимум $k_i(k_i-1)/2$ зв'язків. Тоді

$C_i=\frac{2n_i}{k_i(k_i-1)},$

де $n_i$ число зв'язків між сусідами вузла $i$. Очевидно, що завжди $0⩽C_i⩽1$. Усереднений кластерний коефіцієнт вузлів, називається кластерним коефіцієнтом мережі. Для більшості складних мереж він істотно більший, ніж кластерний коефіцієнт випадкового графа таких же розмірів.

Коефіцієнт асортативності

У мережі можлива ситуація, коли вузли, що мають велику ступінь (Шаблон:Lang-en), переважно пов'язані з вузлами, що мають велику ступінь. Іншими словами «хаби» «воліють» бути пов'язаними з іншими «хабами». Такі мережі називають асортативними. Можлива також зворотна ситуація: «хаби» пов'язані з іншими «хабами» через ланцюжки вузлів, що мають мале число сусідів. Такі мережі називають дизасортативними. Щоб охарактеризувати цю властивість користуються коефіцієнтом асортативності (Шаблон:Lang-en) $r$, так називається коефіцієнт кореляції Пірсона між ступенем сусідніх вузлів. За визначенням, $-1⩽r⩽1$. Для асортативних мереж $r>0$, для дизассортативних мереж $r<0$. Соціальні мережі є асортативними. Мережі пов'язані з біологічними та технічними явищами найчастіше дизасортативні. Існують мережі, що не мають вираженої асортативності з $r$ близьким до нуля.

Див. також

• Структура спільноти
• Світ тісний (граф)

Джерела

• Ю. Головач, О. Олємской, К. фон Фербер, Т. Головач, О. Мриглод, І. Олємской, В. Пальчиков. Складні мережі. - Журн. Фіз. Досл. 10 № 4 (2006) c.247-289.
• Шаблон:Книга
• Шаблон:Книга