Betweenness-Zentralität
- Eingeführt von
- Freeman, L. C.
- Jahr
- 1977
- Typ
- Centrality measure
- Familie
- Network science
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Die von Linton C. Freeman 1977 formalisierte Betweenness-Zentralität misst, wie oft ein Knoten auf dem kürzesten Pfad liegt, der jedes andere Knotenpaar in einem Netzwerk verbindet.
Knoten mit hoher Betweenness fungieren als Brücken oder Vermittler: Ihre Entfernung fragmentiert das Netzwerk stärker in getrennte Komponenten als die Entfernung anderer Knoten.
Die Intuition hinter der Methode
Stellen Sie sich ein städtisches Straßennetz vor, in dem alle Fernstraßen durch eine einzige Kreuzung führen. Diese Kreuzung hat eine maximale Betweenness, auch wenn sie nur eine moderate Anzahl von Straßen hat. In einem sozialen Netzwerk nimmt eine Person, die routinemäßig Informationen zwischen zwei ansonsten getrennten Gruppen weitergibt, dieselbe Position ein: Sie kennt vielleicht nicht viele Leute direkt, aber sie sitzt auf dem kritischen Pfad, der das Netzwerk zusammenhält. Die Betweenness-Zentralität quantifiziert genau diese Vermittlerrolle, unabhängig von der reinen Anzahl der Verbindungen.
Geschichte
Linton Freeman formalisierte die Betweenness-Zentralität in seinem wegweisenden Artikel in Sociometry von 1977, der auf früheren informellen Verwendungen des Konzepts durch Bavelas (1948) in Kommunikationsversuchen aufbaute. Freemans Formulierung vereinte mehrere lose Intuitionen über Knotenwichtigkeit zu einem einzigen berechenbaren Maß und wurde zur kanonischen Definition in der Netzwerkwissenschaft. Ulrik Brandes' Algorithmus von 2001 reduzierte die Berechnung von O(V^3) auf O(VE), wodurch die Betweenness-Zentralität für Netzwerke mit Tausenden von Knoten praktikabel wurde und ihren Platz als Standardwerkzeug in der Software zur Analyse sozialer Netzwerke festigte.
Wann wird sie eingesetzt?
Verwenden Sie Betweenness-Zentralität, wenn Ihre Forschungsfrage sich auf Vermittlung, Gatekeeping oder Brücken-Knoten bezieht – Akteure, deren Entfernung den Informationsfluss oder den Zusammenhalt des Netzwerks stören würde. Sie ist für gerichtete und ungerichtete Graphen sowie für gewichtete Graphen geeignet, bei denen die Kantengewichte Distanz oder Kosten darstellen. Sie ist besonders wertvoll in Kommunikationsnetzwerken, Zitationsnetzwerken, Kollaborationsgraphen und Lieferketten. Verwenden Sie sie nicht als alleiniges Zentralitätsmaß, wenn Vermittlung nicht der theoretische Fokus ist: Grad-Zentralität ist einfacher und ausreichend für reine Konnektivitätsfragen, und Eigenvektor- oder PageRank-Zentralität erfasst die Prestige-Ausbreitung besser. Vermeiden Sie sie für sehr große spärliche Netzwerke ohne effiziente Implementierung, da die naive Berechnung O(V^2 E) ist.
Grenzen und Hinweise
- Berechnungsintensiv bei sehr dichten Netzwerken, selbst mit dem Brandes-Algorithmus; für Web-Skalen-Graphen sind möglicherweise Näherungsalgorithmen erforderlich.
- Geht davon aus, dass Akteure kürzeste Pfade nutzen, was in Netzwerken, in denen Flüsse längere Routen nehmen (z. B. Zufallswanderungen in elektrischen Netzwerken), unrealistisch sein kann.
- Empfindlich gegenüber fehlenden oder verrauschten Kanten: Selbst wenige unbeobachtete Verbindungen können die Betweenness-Rankings drastisch verändern.
- Weist allen kürzesten Pfaden das gleiche Gewicht zu, auch wenn Kantenkapazitäten oder Beziehungsstärken erheblich voneinander abweichen.
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Erfasst strukturelle Vermittlungs- und Brückenrollen, die Grad- und Eigenvektor-Zentralität vollständig übersehen.
- Anwendbar auf gerichtete, ungerichtete, gewichtete und ungewichtete Netzwerke mit derselben Formel.
- Normalisierte Scores ermöglichen einen sinnvollen Vergleich von Knoten innerhalb eines Netzwerks und über Netzwerke unterschiedlicher Größe hinweg.
- Der Brandes-Algorithmus macht die Berechnung für Netzwerke mit Millionen von Knoten handhabbar, wenn er in optimierten Bibliotheken wie NetworkX oder igraph implementiert ist.
- Gut begründete theoretische Interpretation: Knoten mit hoher Betweenness sind empirisch mit Informationskontrolle, Macht und strukturellen Löchern in der Organisations- und Sozialforschung assoziiert.
Anwendungen
- Identifizierung von Gatekeepern und Informationsvermittlern in organisationalen Kommunikationsnetzwerken.
- Erkennung kritischer Infrastrukturknoten in Verkehrs-, Stromnetz- und Internet-Topologiestudien.
- Finden von wichtigen zwischengeschalteten Autoren oder Publikationen in Zitations- und Kollaborationsnetzwerken.
- Abbildung von strukturellen Löchern und Vermittlerpositionen in Netzwerken von Unternehmensallianzen.
- Lokalisierung einflussreicher Verbreiter in epidemiologischen Modellen und Modellen zur Gerüchtediffusion.
- Priorisierung von Knoten für gezielte Interventionen (z. B. Impfung, Störung) in der Forschung zu öffentlicher Gesundheit und Sicherheit.
So funktioniert es
So funktioniert es
Für jedes geordnete Paar von unterschiedlichen Knoten (s, t) im Netzwerk werden alle kürzesten Pfade (Geodäten) zwischen ihnen identifiziert. Bei gewichteten Graphen sind kürzeste Pfade durch minimale Gesamtkantengewichte definiert; bei ungewichteten Graphen durch die geringste Anzahl von Hops. Dieser Schritt etabliert das Universum der Pfade, über die die Betweenness verteilt wird.
Für jedes Paar (s, t) wird die Gesamtzahl der kürzesten Pfade sigma(s, t) gezählt. Wenn mehrere gleich kurze Pfade existieren, wird jeder separat gezählt. Dieser Nenner repräsentiert den gesamten kürzesten Pfadverkehr zwischen s und t ohne Einschränkung der Routenwahl.
Formel
\sigma(s,t) = \text{number of shortest paths from } s \text{ to } tFür jeden Kandidatenknoten v (wobei v weder s noch t ist) wird die Anzahl derjenigen sigma(s, t) kürzesten Pfade, die tatsächlich durch v verlaufen, als sigma(s, t | v) erfasst. Das Verhältnis sigma(s, t | v) / sigma(s, t) gibt den Anteil des kürzesten Pfadverkehrs zwischen s und t an, der über v geleitet wird.
Formel
\sigma(s,t|v) = \text{shortest paths from } s \text{ to } t \text{ passing through } vDiese Anteile werden über alle gültigen Paare (s, t) summiert, um den Roh-Betweenness-Score C_B(v) zu ermitteln. Ein Knoten, dessen Entfernung viele paarweise kürzeste Pfade trennen würde, sammelt eine hohe Summe an und signalisiert damit eine strukturell kritische Vermittlerposition.
Formel
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma(s,t|v)}{\sigma(s,t)}Rohwerte wachsen mit der Netzwerkgröße, was Vergleiche zwischen Netzwerken unterschiedlicher Größe bedeutungslos macht. Die Normalisierung durch (n-1)(n-2)/2 für ungerichtete Graphen (oder (n-1)(n-2) für gerichtete) skaliert die Werte auf [0, 1], wobei 1,0 bedeutet, dass der Knoten auf jedem kürzesten Pfad liegt, und 0, dass er auf keinem liegt. Brandes (2001) führte einen O(VE)-Algorithmus ein, der alle Betweenness-Scores gleichzeitig berechnet, anstatt die Suche für jeden Knoten zu wiederholen.
Formel
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}Häufige Fallstricke
- Hohe Betweenness als gleichwertig zu hohem Grad zu betrachten, ohne beides zu prüfen; ein peripherer Knoten kann bei Betweenness an erster Stelle und bei Grad an letzter Stelle rangieren.
- Vergleich von rohen (nicht normalisierten) Betweenness-Scores über Netzwerke unterschiedlicher Größe hinweg.
- Ignorieren der Kantengerichtung in gerichteten Netzwerken, was zu irreführenden Vermittleridentifikationen führen kann, wenn die Flüsse asymmetrisch sind.
- Anwendung der Standard-Betweenness auf gewichtete Netzwerke, ohne zu bestätigen, dass die Kantengewichte im kürzesten Pfad-Algorithmus korrekt als Kosten (nicht als Ähnlichkeiten) interpretiert werden.
- Übersehen von approximativen Betweenness-Methoden für große Netzwerke und Blockieren der Berechnung bei Millionen von Knoten.
Häufig gestellte Fragen
Wie unterscheidet sich die Betweenness-Zentralität von der Grad-Zentralität?
Die Grad-Zentralität zählt direkte Verbindungen; ein Hub mit vielen Verbindungen erzielt einen hohen Wert. Die Betweenness-Zentralität zählt, wie oft ein Knoten auf kürzesten Pfaden zwischen anderen liegt; eine Brücke, die zwei spärliche Cluster verbindet, erzielt auch bei wenigen direkten Verbindungen einen hohen Wert. Die beiden Maße erfassen orthogonale Aspekte der strukturellen Wichtigkeit.
Sollte ich normalisierte oder rohe Betweenness-Scores verwenden?
Verwenden Sie normalisierte Scores, wann immer Sie Knoten über Netzwerke unterschiedlicher Größe hinweg vergleichen oder Ergebnisse an Leser präsentieren, die mit dem Maß Ihres Netzwerks nicht vertraut sind. Rohe Scores sind nur für Vergleiche innerhalb eines einzelnen festen Netzwerks akzeptabel, in dem der Nenner konstant ist.
Wie gehe ich mit gewichteten Kanten um?
Setzen Sie Kantengewichte so, dass sie Distanz oder Kosten darstellen, nicht Ähnlichkeit. Die meisten Implementierungen (NetworkX, igraph) akzeptieren einen Gewichtsparameter, der als Distanz interpretiert wird; wenn Ihre Gewichte Stärke oder Ähnlichkeit darstellen, invertieren Sie sie (z. B. Gewicht = 1/Ähnlichkeit), bevor Sie die Betweenness berechnen.
Ist Betweenness-Zentralität für getrennte Netzwerke sinnvoll?
Für getrennte Graphen sind kürzeste Pfade zwischen Knoten in verschiedenen Komponenten undefiniert (unendlich). Die meisten Programme behandeln diese Paare so, dass sie Null zur Summe beitragen, was die Scores senken kann. Analysieren Sie entweder jede verbundene Komponente separat oder verwenden Sie eine Variante wie die Stress-Zentralität mit einer expliziten Behandlung von getrennten Paaren.
Mein Netzwerk hat Millionen von Knoten – kann ich trotzdem Betweenness-Zentralität berechnen?
Die exakte Berechnung mit dem Brandes-Algorithmus ist O(VE) und kann zu langsam sein. Verwenden Sie randomisierte Näherungen (z. B. Stichproben von k Quellknoten), die in NetworkX (betweenness_centrality mit dem Parameter k) oder Graph-Bibliotheken wie graph-tool verfügbar sind, welche Konfidenzintervalle für die approximierten Scores liefern.
Verwandte Methoden
Quellen
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1), 35–41.
DOI-Referenz öffnenKopiert.Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.
DOI-Referenz öffnenKopiert.