Граф «Світ тісний» (маленький світ) — різновид графа, який має таку властивість: якщо взяти дві довільні вершини a і b, то вони з великою ймовірністю не є суміжними, проте одна досяжна з іншої за допомогою невеликої кількості переходів через інші вершини. А саме, граф «Світ тісний» визначається як мережа, в якій типова відстань L між двома довільно обраними вершинами (кількість кроків, необхідних, щоб досягти одну з іншої) зростає пропорційно логарифму від числа вершин N в мережі, таким чином:
У контексті соціальної мережі це призводить до феномену «Світ тісний», тобто незнайомих людей пов'язує невелика кількість проміжних знайомих. Багато реально існуючих графів добре моделюються через графи «Світ тісний». Соціальна мережа, зв'язаність мережі Інтернет, вікі-сайти, такі, як Вікіпедія, і генні мережі виявляють властивості графа «Світ тісний». і Стівен Строгац в 1998 році ідентифікували певну категорію графів «Світ тісний» як клас випадкових графів. Вони відзначили, що такі графи можуть бути класифіковані відповідно з двома незалежними структурними особливостями, а саме коефіцієнт кластеризації та відстань від однієї вершини до іншої в середньому (також відоме як довжина найкоротшого шляху в середньому). Цілком випадкові графи, побудовані відповідно з моделлю Ердеша — Реньї, мають малу довжину найкоротшого шляху в середньому (вона росте як логарифм від кількості вершин у графі) і маленький коефіцієнт кластеризації. Воттс і Строгац з'ясували, що більшість реально існуючих мереж мають малу довжину найкоротшого шляху в середньому, але коефіцієнт кластеризації в них істотно вище, ніж очікується при випадковому виборі. Після цього Ватц і Строгац запропонували нову модель графа, в даний час звану Модель Воттса — Строгаца, для якої характерні (i) мала довжина найкоротшого шляху в середньому, і (ii) великий коефіцієнт кластеризації. Перетин в моделі Воттса і Строгаца між «великим світом» (таким, як ґратчастий граф) і маленьким світом було вперше описане Бартелмі і Амарал в 1999. Після цієї роботи сталась велика кількість досліджень.
Властивості графа «Світ тісний»
Графи «Світ тісний» мають тенденцію містити в собі кліки і майже-кліки, під якими розуміють підмережі, які мають зв'язки майже між усіма вершинами в них. Це випливає з визначення такої властивості графа, як високий коефіцієнт кластеризації. По-друге, більшість пар вершин будуть з'єднані хоча б одним коротким шляхом. Більш строго: відстань від однієї вершини до іншої в середньому (також відоме як довжина найкоротшого шляху в середньому) відносно мало. Довжина найкоротшого шляху в середньому вираховується за такою формулою:
— відстань від вершини до вершини — кількість вершин у графі
Деякі інші особливості, які будуть описані далі, часто присутні в графах «Світ тісний». Зазвичай в таких графах є достаток хабів — вершин, у яких велика ступінь вершини. Ці хаби грають роль загального з'єднання, є сполучною ланкою в найкоротшому шляху між іншими ребрами. За аналогією, граф «Світ тісний» авіарейсів має малу довжину найкоротшого шляху в середньому (тобто між будь-якими двома містами у світі буде потрібно, ймовірно, не більше трьох перельотів) через те, що більшість авіарейсів проходять через вузлові аеропорти.
Для аналізу цієї властивості (а саме, наявності хабів) враховують частку вершин в мережі, які мають специфічне кількість вхідних з'єднань (ступінь розподілу мережі). Мережі з великою кількістю хабів, ніж очікується, будуть мати велику частку вершин з високим ступенем, отже, ступінь розподілу буде збільшуватися до високих значень. У розмовній мові це називається . Наявність у мережі високого ступеня розподілу, відповідної критерієм узгодженості з степеневим законом розподілу, є ознакою того, що мережа є графом «Світ тісний». Мережі зі степеневим законом розподілу також відомі як «безмасштабні мережі». Графи дуже різною топології класифікуються як графи «Світ тісний» до тих пір, поки виконуються зазначені вище дві умови (висока ступінь розподілу та відповідність степеневому закону).
Належність до класу графів «Світ тісний» оцінюється порівнянням кластеризації та довжини шляхів даної мережі з відповідними параметрами еквівалентної випадкової мережі з такою ж мірою розподілу. Інший метод оцінювання приналежності мережі до класу графів «Світ тісний» використовує початкове визначення графа «Світ тісний», порівнюючи ступінь кластеризації даної мережі зі ступенем кластеризації еквівалентного графа-решітки і довжину середнього шляху з довжиною середнього шляху в довільному графі. Міра приналежності графа до класу «Світ тісний» () визначається, як
— довжина найкоротшого шляху в середньому в розглянутому графі — ступінь кластеризації розглянутого графа — довжина найкоротшого шляху в середньому у випадковому графі — ступінь кластеризації графа-решітки
Р. Коуен і показали аналітично, що безмасштабні мережі — ультра-малі світи. У цьому випадку, завдяки хабам, найкоротші шляхи стають істотно коротше і масштабуються, як
Приклади графів «Світ тісний» Властивості графа «світ тісний» були виявлені в багатьох об'єктах реального світу, включаючи карти доріг, харчові ланцюжки, електричні мережі, мережі протікання метаболізму (metabolite processing networks), нейронні мережі, мережі виборців, граф телефонних дзвінків та мережі соціального впливу. Білок-білкові взаємодії мають таку властивість графа «Світ тісний», як відповідність степеневому закону розподілу. Аналогічно, властивостями графа «Світ тісний» володіє регуляція транскрипції, в якій вершинам відповідають гени, причому вони пов'язані, якщо один ген має вгору або вниз регулювальний генетичний вплив на інший.
Приклади мереж, які не є графами «Світ тісний» Малоймовірно, що мережі мають властивості графа «Світ тісний», якщо зв'язки між вершинами виникають головним чином через просторової або тимчасової близькості, тому що в такому випадку може не бути короткого шляху між двома «далекими» вершинами. Скрутність фізичним простором або часом, як у системі метро або в дорожніх мережах, як правило, перешкоджає формуванню особливо довгих зв'язків, які сприяють формуванню хабів.
У теорії шести рукостискань розглядаються люди, що живуть в один час. Якщо розглядати всіх людей, коли-небудь жили на Землі, то теорія шести рукостискань перестане працювати. Наприклад, кількість ступенів поділу між Альбертом Ейнштейном і Олександром Македонським більше 30, і ця мережа не має властивостей графа «Світ тісний». Аналогічні властивості є у мережі «піти до школи з»: якщо одна людина навчається в певному коледжі через 10 років після іншого, то малоймовірно, що вони познайомилися в цьому коледжі.
Точно так само, кількість станцій, через які повідомлення повинно пройти, не завжди було маленьким. У ті дні, коли пошта доставлялася з рук в руки або кінної поштою, кількість разів, яке лист передається з рук в руки між відправником та одержувачем було набагато більше, ніж сьогодні. Кількість разів, яке повідомлення передається з рук в руки між відправником та одержувачем в роки візуального телеграфу (близько 1800—1850) було визначено вимогою, що дві станції з'єднані лінією візуального контакту.
Неявні припущення, якщо не перевірені, можуть стати причиною необ'єктивності в літературі про графах на користь помилкової ідентифікації графів «Світ тісний» (наприклад картотека, що виникла через необ'єктивності публікації).
Надійність мережі
Деякими дослідниками (наприклад, Barabási) було висловлено припущення, що поширеність графів «Світ тісний» в біологічних системах може відображати еволюційна перевага такої топології. Приводом до такого припущення стала гіпотеза, що графи «Світ тісний» стійкіші при різних зовнішніх впливах в порівнянні з іншими топологіями мережі. Якби ця гіпотеза була вірна, то це забезпечило б перевагу біологічним системам, які є суб'єктами мутацій і вірусних інфекцій.
У графах «Світ тісний» зі степеневим законом розподілу ступенів вершин видалення випадкової вершини рідко служить причиною істотного збільшення найкоротшого шляху в середньому (або істотного зменшення коефіцієнта кластеризації). Це випливає з того факту, що більшість найкоротших шляхів проходять через хаби, і якщо периферична вершина видаляється, малоймовірно, що вона втрутиться в проходження між іншими периферійними вершинами. Оскільки частка периферійних вершин у графі «Світ тісний» істотно вище, ніж частка хабів, ймовірність видалення важливої вершини вкрай мала. Наприклад, якщо маленький аеропорт в Петрозаводську перестане працювати, то це не збільшить середню кількість польотів, які потрібні пасажирам, щоб дістатися до точки призначення. Проте, якщо випадкове видалення потрапляє в хаб, довжина найкоротшого шляху в середньому може вирости досить істотно. Це можна побачити щорічно, коли північний аеропорт в США, такий, як Чиказький аеропорт О'Хара заносить снігом, і багато людей змушені летіти з пересадками і добиратися до пункту призначення обхідними шляхами.
На відміну від графа «Світ тісний», у випадковій мережі, в якій всі вершини мають приблизно однакову кількість з'єднань, видалення випадкової вершини збільшує довжину найкоротшого шляху в середньому незначно, але однаково для будь-якої віддаленої вершини. У цьому сенсі випадкові мережі уразливі до випадкових збурень в той час як графи «Світ тісний» стійкі. Однак графи «Світ тісний» уразливі до спрямованих атак на хаби в той час як у випадкових мережах не можна вибрати цілі, знищення яких призведе до катастрофічних наслідків.
Відповідно, віруси еволюціонували таким чином, щоб взаємодіяти з протеїнами — хабами, такими як p53, тим самим вносячи суттєві зміни в поведінку клітин, сприятливі для відтворення вірусів.
Конструювання графів «Світ тісний»
Основний механізм конструювання графів «Світ тісний» — Модель Ватца — Строгаца.
Побудова графів «Світ тісний» з тимчасовим запізненням, дозволяє створювати не тільки фрактали, а й хаос при правильних умовах або перехід до хаосу в динамічних мережах. При розв'язанні задачі про ступінь діаметра конструюється граф, в якому кількість сусідів кожної вершини обмежена, в той час як відстань між будь-якою парою вершин (діаметр мережі) мінімізується. Конструювання таких графів «Світ тісний» здійснюється в рамках зусиль знаходження графів порядку, близького до межі Мура.
Інший шлях конструювання графів «Світ тісний» з нуля показаний у Бармпутіса і Мюррея, де будується мережа з дуже маленьким середньою відстанню і дуже великий середньої кластеризацією. Швидкий алгоритм константної складності даний разом з вимірами надійності отриманих графів. Залежно від галузі, можна почати з одного такого «ultra small — world» графа, і потім заново включити деякі ребра, або використовувати деякі маленькі такі мережі як підграф більшого графа.
Див. також: ,
Застосування Граф «Світ тісний» використовують для моделювання в різних галузях.
Застосування в соціології Одна з переваг графів «Світ тісний» для громадського руху полягає в їх захищеності від фільтрувальних апаратів, що використовують сильно пов'язані вершини. Інша перевага — краща ефективність у передачі інформації при збереженні кількості посилань, необхідних для підключення до мережі на мінімальному рівні.