Kürzester Pfad

Die Weglänge $\ell_{ij}$ zwischen zwei Knoten $i,j$ ist als die Anzahl von Verbindungen definiert, die auf dem Weg von $i$ nach $j$ beschritten wird. Als Abstand dieser Knoten voneinander bezeichnet man üblicherweise den kürzesten existierenden Weg von $i$ nach $j$. In einem gerichteten Netzwerk ist der Hinweg nicht notwendigerweise gleich dem Rückweg zwischen den Knoten. Den Mittelwert über alle existierenden kürzesten Pfade aller Knotenpaare nennt man die mittlere kürzeste Pfadlänge $<\ell>$ eines Netzwerks. $<\ell>$ wird oft auch als Durchmesser eines Netzwerks bezeichnet.

In einem vollständig verbundenen Netzwerk ist $<\ell>=1$. Für Zufallsgraphen läßt sich $<\ell>$ abschätzen: Sei $z_1$ die mittlere Anzahl nächster Nachbarn eines Knotens, dann sind etwa $z_1^{\ell}$ Knoten mit Abstand $\ell$ oder weniger in der Umgebung des Knotens. Dem folgend ist $N \sim z_1^{<\ell>}$ und $<\ell> \sim \ln N / \ln z_1$. Somit ist der Duchmesser auch für große Netzwerke vergleichsweise klein. Diese Eigenschaft wird auch als ``Small-World-Effekt'' bezeichnet.