Netzwerkdurchmesser

Der Netzwerkdurchmesser ist in der Netzwerkanalyse die maximale Distanz zwischen zwei Knoten eines Netzwerks. Die Distanz wird dabei als Länge eines kürzesten Pfades zwischen den Knoten definiert. In ungewichteten Netzwerken zählt die Distanz die Anzahl der Kanten, in gewichteten Netzwerken die Summe der Kantengewichte.

Für ungerichtete Netzwerke gilt die Distanz symmetrisch; bei gerichteten Netzwerken kann sie asymmetrisch sein. Der Durchmesser wird daher oft als der maximale Wert von D(u, v) über alle Knotenpaare definiert. Falls das Netzwerk nicht stark zusammenhängend ist, existieren für viele Paare gerichteter Pfade; in solchen Fällen wird der Durchmesser oft als Durchmesser des größten stark zusammenhängenden Teilnetzes angegeben oder als unendliche Größe betrachtet.

Zusammenhänge zu anderen Maßen: Der Eccentricity e(v) eines Knotens ist der maximale Abstand von diesem Knoten zu allen anderen. Der Radius r des Netzwerks ist das Minimum der Eccentricities über alle Knoten, und der Durchmesser D ist das Maximum der Eccentricities. In vielen realen Netzwerken wird auch der effektive Durchmesser oder percentile-basierte Durchmesser verwendet, etwa der Abstand, den 90 Prozent der Paare erreichen.

Berechnung und Praxis: D(G) lässt sich mit Algorithmen für All-Pairs-S Shortest Paths bestimmen (z. B. Floyd-Warshall O(n^3), Johnsons Algorithmus O(nm log n)). Große Netzwerke erfordern oft heuristische Annäherungen oder Stichproben.

Anwendungen: Der Durchmesser dient unter anderem zur Beurteilung der Kommunikations- oder Ausbreitungseffizienz, zur Abschätzung der Netzwerklage, zur Planung robuster Netze und zur Analyse der Strukturen sozialer, technischer oder biologischer Netzwerke. Wichtige Hinweise: das Maß hängt stark von der gewählten Distanzmetrik und der Netzwerkstruktur ab.