Betweennesszentralität

BetweennessZentralität ist eine Kennzahl in der Netzwerkanalyse, die angibt, wie stark ein Knoten als Vermittler zwischen anderen Knoten fungiert. Im deutschsprachigen Raum wird dieses Konzept üblicherweise als Betweennesszentralität bezeichnet. Für einen Knoten v wird der Anteil aller kürzesten Pfade zwischen Paaren von Knoten summiert, die durch v verlaufen. Formal ist bc(v) die Summe über alle Paare (s,t) von der Fraktion der kürzesten Pfade, die s–t durchqueren und bei denen v ein Zwischenknoten ist. In ungerichteten Graphen zählt man typischerweise jedes Paar s≠t einmal; bei gerichteten Graphen werden oft alle geordneten Paare berücksichtigt. Eine Normalisierung erfolgt häufig durch Division durch (n−1)(n−2)/2 für ungerichtete Graphen bzw. durch (n−1)(n−2) für gerichtete Graphen.

Betweenness kann sowohl in ungewichteten als auch in gewichteten Graphen verwendet werden; bei gewichteten Graphen berücksichtigt bc(v) die Längen oder Kosten der Pfade statt deren bloßer Anzahl. Der gängige Berechnungsansatz ist der Brandes-Algorithmus, der bc für alle Knoten in Zeit O(nm) berechnet (ungewichtete Graphen) bzw. O(nm) bei gewichteten Graphen; bei sehr großen Netzwerken kann man auf approximative oder samplingsbasierte Verfahren zurückgreifen.

Anwendungsfelder finden sich in der Identifikation von Brücken oder Engpässen, der Bestimmung zentraler Vermittler in sozialen Netzen, der Modellierung von Informations- oder Ausbreitungsprozessen sowie in der Infrastrukturplanung und Resilienzbewertung. Zu den Einschränkungen zählen die Abhängigkeit des Ergebnisses von der Netzkonstruktion, Empfindlichkeit gegenüber Ausdünnung oder Rauschen sowie Skalierungsprobleme bei sehr großen Graphen. In gerichteten Graphen kann die Interpretation komplexer sein, weshalb Kontext und Richtung der Kanten berücksichtigt werden sollten.