Середня довжина шляху

Середня довжина шляху — це поняття з топології мережі, яке визначається як середня кількість кроків у найкоротших шляхах для всіх можливих пар мережевих вузлів. Це міра ефективності інформації в мережі.

Концепція

Середня довжина шляху — одна з трьох найнадійніших характеристик топології мережі, як і коефіцієнт кластеризації та розподіл ступеня. Ось кілька прикладів: середня кількість кліків, які приведуть вас з одного вебсайту до іншого, або кількість людей, з якими ви будете спілкуватися, в середньому, щоб зв'язатися з незнайомою особою. Не слід плутати з діаметром мережі, яка визначається як найдовша геодезична лінія, тобто найдовший найкоротший шлях між будь-якими двома вузлами мережі (див. відстань (теорія графів)).

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

Визначення

Розглянемо незбалансований спрямований граф ${\displaystyle G}$ з множиною вершин ${\displaystyle V}$. Нехай ${\displaystyle d(v_{1},v_{2})}$, де ${\displaystyle v_{1},v_{2}\in V}$ позначає найкоротшу відстань між ${\displaystyle v_{1}}$ і ${\displaystyle v_{2}}$. Припустимо, що ${\displaystyle d(v_{1},v_{2})=0}$, якщо ${\displaystyle v_{2}}$ від ${\displaystyle v_{1}}$. Тоді середня довжина шляху ${\displaystyle l_{G}}$ має значення:

${\displaystyle l_{G}={\frac {1}{n\cdot (n-1)}}\cdot \sum _{i\neq j}d(v_{i},v_{j}),}$

де ${\displaystyle n}$ — це число вершин у ${\displaystyle G}$.

Застосування

У реальній мережі, такій як всесвітнє павутиння, коротка середня довжина шляху полегшує швидку передачу інформації та зменшує витрати. Про ефективність масового перенесення в ^[en] можна судити за вивченням його середньої довжини шляху. Електрична мережа матиме менші втрати, якщо її середня довжина шляху буде мінімізована.

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

У результаті більшість моделей реальних мереж створюються з урахуванням цього стану. Однією з перших моделей, яка намагалася пояснити реальні мережі, була модель випадкової мережі. Це було наслідувано у моделі Воттса — Строгаца, а ще пізніше було наслідувано в безмасштабних мережах, починаючи з моделі Барабаші — Альберта. Всі ці моделі мали одну спільну річ: усі вони передбачали дуже коротку середню довжину шляху. Середня довжина шляху деяких мереж вказана в табл. [1].

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

Примітки

1. Barabási, A.-L., and R. Albert, 2002, Rev. Mod. Phys. 74, 47.