Nächste Seite: Clustering-Koeffizient
Aufwärts: Grundbegriffe
Vorherige Seite: Degree
Inhalt
Die Weglänge zwischen zwei Knoten ist als die Anzahl von
Verbindungen definiert, die auf dem Weg von nach beschritten wird.
Als Abstand dieser Knoten voneinander bezeichnet man üblicherweise
den kürzesten existierenden Weg von nach . 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 eines Netzwerks.
wird oft auch als Durchmesser eines Netzwerks
bezeichnet.
In einem vollständig verbundenen Netzwerk
ist . Für Zufallsgraphen läßt sich
abschätzen: Sei die mittlere Anzahl nächster Nachbarn eines Knotens,
dann sind etwa
Knoten mit Abstand oder weniger in der
Umgebung des Knotens. Dem folgend ist
und
. Somit ist der Duchmesser auch für
große Netzwerke vergleichsweise klein. Diese Eigenschaft wird auch als
``Small-World-Effekt'' bezeichnet.
Autor:Lutz-Ingo Mielsch