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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Мережа інтернету (IP-адреси є вузлами) є складною мережею.

Складні мережі (англ. Complex networks) — це мережі (графи), що володіють нетривіальними топологічними властивостями. Складні мережі широко поширені у природі.

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

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

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

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

Орієнтовані і неорієнтовані мережі[ред.ред. код]

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

Розподіл ступенів вузлів (англ. Degree distribution of nodes)[ред.ред. код]

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

Діаметр мережі[ред.ред. код]

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

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

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

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

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

Коефіцієнт асортативності (англ. Assortativity coefficient)[ред.ред. код]

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

Примітки[ред.ред. код]

  1. Dorogovtsev SN, Mendes JFF Evolution of Networks: From Biological Networks to the Internet and WWW. — Oxford, USA: Oxford University Press, 2003. — P. 280. — ISBN 978-0198515906
  2. Mark Newman, Albert-Laszlo Barabasi, Duncan J. Watts The Structure and Dynamics of Networks: (Princeton Studies in Complexity). — Princeton, USA: Princeton University Press, 2006. — P. 624. — ISBN 978-0691113579

Посилання[ред.ред. код]