Наука про мережі
Теорія
Граф Складні мережі Світ тісний Безмасштабна мережа Перколяція Структура спільноти Еволюція[en] Керованість[en] Візуалізація графів Соціальний капітал Аналіз зв’язків Оптимізація Транзитивність Теорія балансу Ефект мережі Соціальний вплив
Види мереж
Інформаційна (комп'ютерна) Телекомунікаційна Транспортна Соціальна аналіз Біологічна[en] Штучна нейронна мережа Семантична Просторова Залежностей[en] Потокова
Графи
Властивості Кліка Компонент Розріз Цикл Структура даних Ребро Петля Окіл Шлях Вершина Список суміжності[en] / матриця Список інцидентності / матриця Види Двочастковий Повний Орієнтований Гіперграф Мультиграф Випадковий Зважений
Метрики[en] Алгоритми
Центральність Степінь Близькість[ru] PageRank Кластеризація Асортативність[en] Відстань Модулярність[en] Ефективність[en]
Моделі
Топологія Випадковий граф Модель Ердеша — Реньї Модель Барабаші — Альберт Модель Воттса — Строгаца Гіперболічна (HGN)[en] Ієрархічна[en] Стохастична блокова модель Динаміка Булева мережа Агентне моделювання Епідемічні/SIR
Списки Категорії
Категорія:Теорія мереж Категорія:Теорія графів
п о р

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

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

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

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

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

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

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

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

${\displaystyle C_{i}={\frac {2n_{i)){k_{i}(k_{i}-1))),}$

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

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

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

• Ю. Головач, О. Олємской, К. фон Фербер, Т. Головач, О. Мриглод, І. Олємской, В. Пальчиков. Складні мережі. - Журн. Фіз. Досл. 10 № 4 (2006) c.247-289.
• Ландэ Д.В., Снарский А.А., Безсуднов И.В. Интернетика: Навигация в сложных сетях: модели и алгоритмы. — М. : Либроком (Editorial URSS), 2009. — 264 с. — ISBN 978-5-397-00497-8.
• Снарский А.А., Ландэ Д.В. Моделирование сложных сетей: учебное пособие. — К. : Инжиниринг, 2015. — 212 с. — ISBN 978-966-2344-44-8.