Średnia długość ścieżki

Średnia długość ścieżki lub średnia długość najkrótszej ścieżki to pojęcie topologii sieci , które definiuje się jako średnią liczbę kroków wzdłuż najkrótszych ścieżek dla wszystkich możliwych par węzłów sieci . Jest miarą wydajności transportu informacji lub masy w sieci.

Pojęcie

Średnia długość ścieżki jest jedną z trzech najbardziej niezawodnych miar topologii sieci, wraz z jej współczynnikiem grupowania i rozkładem stopni . Oto kilka przykładów: średnia liczba kliknięć, które przeniosą Cię z jednej witryny do drugiej, lub średnia liczba osób, przez które będziesz musiał się komunikować, aby skontaktować się z zupełnie obcą osobą. Nie należy jej mylić ze średnicą sieci, która jest zdefiniowana jako najdłuższa geodezja , tj. najdłuższa najkrótsza ścieżka między dowolnymi dwoma węzłami w sieci (patrz Odległość (teoria grafów) ).

Średnia długość ścieżki odróżnia łatwo negocjowalną sieć od takiej, która jest skomplikowana i nieefektywna, przy czym bardziej pożądana jest krótsza średnia długość ścieżki. Jednak średnia długość ścieżki jest po prostu tym, jaka będzie najprawdopodobniej długość ścieżki. Sama sieć może mieć kilka bardzo oddalonych węzłów i wiele węzłów, które są ze sobą sąsiadami.

Definicja

$skierowany$ nieważony graf ze zbiorem $.$ Niech ${\ Displaystyle d (v_ {1}, v_ {2})}$ , gdzie ${\ Displaystyle v_ {1}, v_ {2} \ w V}$ oznaczają najkrótszą odległość między ${\ displaystyle v_ {1}}$ i ${\ displaystyle v_ {2}}$ . Załóżmy, że $\ Displaystyle d (v_ {1}, v_ {2}) = 0}$${1}}$ jeśli nie można osiągnąć z $v_ {2}}$$Displaystyle$ . Wtedy średnia długość ścieżki wynosi: ${\ displaystyle l_ {G}}$

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

gdzie jest liczbą wierzchołków w $displaystyle G}$$\$ .

Aplikacje

W rzeczywistej sieci, jaką jest Internet , krótka średnia długość ścieżki ułatwia szybki transfer informacji i obniża koszty. Efektywność przenoszenia masy w sieci metabolicznej można ocenić badając średnią długość drogi. Sieć elektroenergetyczna będzie miała mniejsze straty, jeśli jej średnia długość ścieżki zostanie zminimalizowana.

Większość rzeczywistych sieci ma bardzo krótką średnią długość ścieżki, co prowadzi do koncepcji małego świata , w którym wszyscy są połączeni ze wszystkimi za pomocą bardzo krótkiej ścieżki.

W rezultacie większość modeli rzeczywistych sieci jest tworzonych z myślą o tym warunku. Jednym z pierwszych modeli, który próbował wyjaśnić sieci rzeczywiste, był model sieci losowej . Później pojawił się model Wattsa i Strogatza , a jeszcze później pojawiły się sieci bezskalowe, począwszy od modelu BA . Wszystkie te modele miały jedną wspólną cechę: wszystkie przewidywały bardzo krótką średnią długość ścieżki. Średnie długości ścieżek niektórych sieci podano w tabeli.

Średnia długość ścieżki zależy od rozmiaru systemu, ale nie zmienia się drastycznie wraz z nim. Teoria małych sieci światowych przewiduje, że średnia długość ścieżki zmienia się proporcjonalnie do log n, gdzie n to liczba węzłów w sieci.