Zentralität im Netz verständlich erklärt

Ein Fluss, eine einzige Brücke: Fällt sie aus, ist die Stadt geteilt. Wie findet man solche Stellen in einem Netz aus Orten und Verbindungen? Diese Seite zeigt vier Antworten und prüft, welche den Schaden am besten voraussagt.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Eine Stadt, ein Fluss, eine Brücke

Stellen Sie sich eine Stadt vor, die ein Fluss in zwei Teile trennt. Eine einzige Brücke verbindet die Ufer. Eines Morgens wird die Brücke gesperrt. Nun kommt niemand mehr ans andere Ufer. Eine Verbindung, deren Ausfall ein Netz teilt, heißt deshalb auch im Netz Brücke, selbst wenn sie keine ist.

Solche Stellen gibt es in jedem Netz aus Orten und Verbindungen, ob Straßen, Stromleitungen, Bahnlinien oder Freundeskreise. Man möchte wissen, welcher Ort am wenigsten ausfallen darf. Dafür gibt es mehrere Antworten. Sie führen nicht immer zum selben Ort.

Vier Fragen, was „wichtig“ heißt

Ein Ort im Netz heißt im Fachwort Knoten. Wir können vier verschiedene Fragen an ihn stellen.

• Wer hat die meisten direkten Nachbarn? Das zählt der Grad. Er ist leicht zu erheben, sagt aber nichts darüber, wo der Ort im Netz liegt.
• Wer liegt im Schnitt am nächsten an allen anderen? Das misst die Closeness. Ein Ort in der Stadtmitte schneidet gut ab, einer am Stadtrand schlechter.
• Über wen laufen die meisten kürzesten Wege? Das misst die Betweenness. Man nimmt jedes Paar von Orten, sucht den kürzesten Weg und zählt, welche Orte unterwegs vorkommen. Gibt es mehrere gleich kurze Wege, teilt sich der Beitrag auf.
• Wo hält sich ein Spaziergänger am häufigsten auf? Er geht immer zufällig zu einem Nachbarn weiter und springt gelegentlich an einen beliebigen Ort. Wer dort auf Dauer am häufigsten vorbeikommt, gilt als wichtig. Das misst der PageRank. Wer mit vielen wichtigen Orten verbunden ist, wird oft besucht.

Beispiel: zwei Dörfer und eine Brücke

Nehmen wir ein Beispiel zum Nachzählen. Zwei Dörfer haben je fünf Häuser. Jedes Haus ist mit allen anderen Häusern seines Dorfes verbunden. Zwischen den Dörfern führt genau eine Brücke, von einem Haus des einen Dorfes zu einem Haus des anderen.

Der Grad unterscheidet hier wenig: vier Nachbarn bei den meisten Häusern, fünf bei den beiden Häusern, an denen die Brücke endet (Brückenhäuser). Die Betweenness unterscheidet viel mehr. Ein Haus ohne Brückenanschluss ist nie ein Zwischenstopp: Zwei Häuser desselben Dorfes sind direkt verbunden, und wer ins andere Dorf will, geht über das Brückenhaus. Für die vier anderen Häuser seines Dorfes führt jeder Weg zu den fünf Häusern drüben über dieses Haus. Das sind 20 Paare.

Die Brücke selbst liegt auf den kürzesten Wegen aller Paare aus verschiedenen Dörfern: fünf mal fünf, also 25. Das sind mehr als beim wichtigsten Haus. Der Grund: Bei einem Haus zählen nur Wege, die es als Zwischenstopp durchqueren. Ein Weg, der im Haus beginnt oder endet, zählt nicht. Die Brücke ist kein Haus und nie Start oder Ziel.

Das gilt allgemein: Trennt eine Brücke ein Netz in zwei Teile, laufen alle kürzesten Wege zwischen den Teilen über sie. Die Zahl der betroffenen Paare ist die Größe des einen Teils mal die Größe des anderen.

Welches Maß sagt den Schaden voraus?

Nun zum Test. Alle Zahlen in diesem Teil gelten für erfundene Beispielnetze, nicht für die Wirklichkeit. Der Computer sperrt jeden Ort einmal, samt seinen Verbindungen. Dann zählt er, wie viel Erreichbarkeit verloren geht. Jedes Paar von Orten bringt Punkte: je kürzer der Weg, desto mehr, und ohne Weg keine. Fällt ein Ort weg, sinkt die Punktsumme. Denn Wege werden länger oder verschwinden, und auch die Wege von und zu dem Ort selbst gehen verloren. Der Verlust an Punkten ist der Schaden (Fachwort: Vitalität).

Dann werden zwei Reihenfolgen verglichen: die Orte nach ihrem Schaden und die Orte nach einem der vier Maße. Je ähnlicher sie sind, desto besser sagt das Maß den Schaden voraus. Die Ähnlichkeit ist eine Zahl. Bei eins sind die Reihenfolgen gleich, bei null besteht kein Zusammenhang. Der Test lief für fünf erfundene Netze je Netzart, und gewertet wurde der mittlere der fünf Werte. Drei Netzarten zeigen, ob das Ergebnis vom Netz abhängt.

• Straßenraster, 30 % der Straßen gesperrt: Beste Vorhersage: Betweenness. Schwächste: Closeness.
• Zufallsnetz mit denselben Orten und gleich vielen oder weniger Straßen als das volle Raster: Beste Vorhersage: Betweenness. Schwächste: Closeness. Nur bei halb so vielen Straßen wie im vollen Raster liegt der Grad knapp vorn und PageRank hinten.
• Regelmäßiges Raster ohne jede Sperrung (die fünf Netze sind hier dasselbe): Beste Vorhersage: Betweenness, dicht gefolgt von Closeness. Schwächste: PageRank.

Warum liegt die Betweenness bei gesperrten Straßen vorn? Eine naheliegende Erklärung, die eine Nachrechnung im zweiten Teil stützt: Zum Schaden gehören die Umwege der anderen, und genau die zählt die Betweenness.

Warum fällt PageRank im regelmäßigen Raster so weit zurück? Dort haben die meisten Kreuzungen vier Straßen, und PageRank ordnet sie nach kleinen Unterschieden. Der Schaden ist aber in der Mitte größer als am Rand. Eine Nachrechnung dieser Seite zeigt: Unter den Kreuzungen mit vier Straßen ordnet PageRank fast genau umgekehrt wie der Schaden. Eine Ursache ist nicht geprüft. Vermutlich geben Randkreuzungen mit wenigen Straßen ihre Wichtigkeit gebündelter an die Nachbarn weiter. Closeness und Betweenness liegen dort dicht beieinander, denn die Mitte ist beides: nah an allen und auf den meisten Wegen.

Häufige Missverständnisse

• „PageRank ist ein schlechtes Maß.“ Nein. Er beantwortet eine andere Frage: wie viel Aufmerksamkeit ein Ort durch wichtige Nachbarn bekommt. Für den Schaden bei Ausfall war er in dieser Messung nie der beste Ratgeber.
• „Eine hohe Zahl heißt: Dieser Ort ist ein Schwachpunkt.“ Nein. Die Zahlen ordnen Orte, sie beweisen nichts. Der Test misst nur eine Art von Schaden, in erfundenen Netzen. Bei anderen Schäden könnte ein anderes Maß vorn liegen. Das wurde nicht geprüft.

Woran Sie das im Alltag erkennen

• Auf Ihrem Weg zur Arbeit gibt es eine Brücke, einen Tunnel oder eine Kreuzung ohne vernünftigen Umweg.
• Im Büro oder Verein läuft vieles über eine Person, obwohl sie nicht die meisten Kontakte hat. Fällt sie aus, stockt die Abstimmung.

Wie ernst ist das Rechenbild zu nehmen?

Die Beispielnetze sind ein vereinfachtes Rechenbild (Fachwort: Modell). Sie sind erzeugt und ungerichtet, Einbahnstraßen kommen nicht vor. Die Zahlen zeigen eine Richtung für diese Netze, keine Werte für ein echtes Netz.

Was Sie mitnehmen

• Legen Sie fest, welchen Schaden Sie vermeiden wollen, bevor Sie ein Maß für „wichtig“ wählen.
• Prüfen Sie ein Maß am Ausfall selbst: Nehmen Sie jeden Ort einmal weg und sehen Sie, was passiert.
• Suchen Sie nicht nur wichtige Orte, sondern auch einzelne Verbindungen, über die alles läuft.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, die Demo. Der erste Knopf unten öffnet es, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er beschreibt vier klassische Zentralitätsmaße (Grad, Closeness, Betweenness, PageRank) auf erzeugten, ungerichteten und ungewichteten Netzen und prüft, welches Maß den Schaden beim Entfernen eines Knotens am besten vorhersagt.

• Netze: ein gestörtes Straßenraster mit \(L \times L\) Kreuzungen als Knoten (Voreinstellung \(12 \times 12 = 144\) Knoten), in dem ein Anteil der Straßen zufällig und ohne Rücksicht auf den Zusammenhang gesperrt ist (Voreinstellung 30 %); das Netz darf zerfallen. Alternativ ein Zufallsgraph mit derselben Knoten- und Kantenzahl wie das Raster nach dem Sperren. Als Lehrbuchfall dient der Barbell-Graph: zwei vollständige Graphen \(K_k\) mit \(k = 3\) bis \(10\), durch eine einzige Kante, die Brücke, verbunden. Straßenlängen spielen für die Maße keine Rolle.
• Schaden: die Vitalität \(\mathrm{Vit}(v)\), der Rückgang der globalen Effizienz beim Entfernen von \(v\) (Formeln unten). Sie ist nie negativ.
• Messung: für jedes Maß die Spearman-Rangkorrelation gegen die Vitalität über alle Knoten; bei Gleichstand gelten mittlere Ränge, und Werte, die sich um weniger als ein Zehnmillionstel (relativ) unterscheiden, zählen als gleich. Angegeben ist, sofern nicht anders genannt, der Median über 5 feste, zufällig erzeugte Instanzen je Netzart und Sperranteil. Die Sperranteile laufen von ohne Sperrung bis zur Hälfte der Straßen in Schritten von einem Zehntel; beim Zufallsgraph bezeichnet der Anteil, um wie viel weniger Kanten er gegenüber dem vollen Raster hat. Die Vitalität wird bei mehr als 200 Knoten nicht automatisch berechnet, ihr Aufwand wächst etwa mit \(n^2 (n+m)\).
• Aufwandsmaß: Elementarschritte. Jeder abgearbeitete Knoten und jede von einem Ende angesehene Kante zählt 1; die naive Betweenness zählt zusätzlich die Länge jedes aufgezählten Weges. Das ist ein Näherungsmaß, keine Laufzeit.

Die Formeln

Das Netz \(G\) hat \(n\) Knoten und \(m\) Kanten, \(N(v)\) sind die Nachbarn von \(v\), \(d(u,v)\) ist der Abstand, also die Zahl der Kanten eines kürzesten Weges. Der Grad ist \(\deg(v) = |N(v)|\).

Closeness in der Variante von Wasserman und Faust (wie in der Bibliothek networkx). \(R(v)\) sind die von \(v\) erreichbaren Knoten einschließlich \(v\), und \(r(v) = |R(v)|\):

\[C(v) = \frac{r(v)-1}{\sum_{u \in R(v)} d(v,u)} \cdot \frac{r(v)-1}{n-1}\]

Im zusammenhängenden Netz ist \(r(v) = n\), und der Ausdruck wird zu \((n-1)/\sum_u d(v,u)\), dem Kehrwert des mittleren Abstands. Der zweite Faktor wertet Knoten ab, die nur einen kleinen Teil des Netzes erreichen.

Betweenness (Freeman 1977), unnormiert. \(\sigma_{st}\) ist die Zahl der kürzesten Wege von \(s\) nach \(t\), \(\sigma_{st}(v)\) die Zahl davon über \(v\). Die Summe läuft über ungeordnete Paare \(\{s,t\}\) mit \(s \neq t\), jedes Paar zählt einmal. Für eine Kante \(e\) gilt dieselbe Definition mit \(\sigma_{st}(e)\):

\[C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}\]

Brandes (2001): Für einen festen Startknoten \(s\) liefert eine Breitensuche die Abstände und die Zahlen \(\sigma_{sv}\). \(P_s(w)\) sind die Vorgänger von \(w\) auf kürzesten Wegen von \(s\). Rückwärts, vom entferntesten Knoten zur Quelle, wird die Abhängigkeit akkumuliert:

\[\delta_s(v) = \sum_{w: v \in P_s(w)} \frac{\sigma_{sv}}{\sigma_{sw}}(1+\delta_s(w))\]

Die Betweenness ist \(C_B(v) = \tfrac12 \sum_{s \neq v} \delta_s(v)\); der Faktor \(\tfrac12\) gleicht aus, dass die Summe über die Startknoten jedes ungeordnete Paar zweimal enthält. Die Kanten-Abhängigkeit fällt als Nebenprodukt derselben Rückwärtsphase ab. Der Gesamtaufwand ist \(O(n \cdot m)\) statt des Aufzählens aller kürzesten Wege.

PageRank (Brin und Page 1998) mit Dämpfung \(\alpha\) (Voreinstellung 0,85): \(PR(v) = \frac{1-\alpha}{n} + \alpha \sum_{u \in N(v)} \frac{PR(u)}{\deg(u)}\), berechnet mit der Potenzmethode bis zum Fixpunkt (Toleranz 1e-10). Isolierte Knoten verteilen ihre Masse gleichmäßig auf alle Knoten.

Effizienz und Vitalität. Die globale Effizienz geht auf Latora und Marchiori (2001) zurück, die sie über alle Paare mitteln; hier gilt die unnormierte Summe \(E(G) = \sum_{u < v} 1/d(u,v)\) über alle ungeordneten Paare \(u \neq v\); unerreichbare Paare tragen 0 bei. Absolute Werte sind daher nicht mit denen der Literatur vergleichbar. Die Vitalität (Effizienzverlust beim Entfernen eines Knotens) ist hier \(\mathrm{Vit}(v) = E(G) - E(G \setminus v)\); in \(G \setminus v\) fehlen alle Paare mit \(v\).

Zwei Herleitungen Schritt für Schritt

Brücken-Satz. Ist \(e\) eine Brücke in einer Komponente der Größe \(S\), und trennt ihr Entfernen die Komponente in Teile der Größen \(a\) und \(S-a\), so gilt für die unnormierte Betweenness \(C_B(e) = a\,(S-a)\). Die folgende Herleitung ist eine Rechnung dieser Seite.

• Schritt 1: Seien \(A\) und \(B\) die beiden Teile mit \(|A| = a\) und \(|B| = S-a\). Die Kante \(e\) ist die einzige Verbindung zwischen ihnen.
• Schritt 2, Paare über die Brücke: Für \(s \in A\) und \(t \in B\) benutzt jeder kürzeste Weg von \(s\) nach \(t\) die Kante \(e\), sonst wäre \(e\) keine Brücke. Also gilt \(\sigma_{st}(e) = \sigma_{st}\), und das Paar trägt 1 bei. Der kürzeste Weg muss dafür nicht eindeutig sein, es genügt, dass jeder kürzeste Weg über \(e\) läuft. Eindeutig sind sie meist nicht: In der Voreinstellungs-Instanz (30 % Sperrung, eine Instanz) hat bei 20 der 21 Brücken mindestens ein Paar über die Brücke mehrere kürzeste Wege (Nachrechnung dieser Seite).
• Schritt 3, alle anderen Paare: Liegen \(s\) und \(t\) im selben Teil, müsste ein Weg über \(e\) den Teil verlassen und über dieselbe Kante zurückkehren. Ein kürzester Weg benutzt keine Kante zweimal, der Beitrag ist 0. Liegt ein Knoten in einer anderen Komponente, gibt es keinen Weg, der Beitrag ist ebenfalls 0.
• Schritt 4, Zählen: Es gibt \(a\,(S-a)\) ungeordnete Paare mit einem Knoten in \(A\) und einem in \(B\), jedes trägt 1 bei. Also ist \(C_B(e) = a\,(S-a)\). Bei normierter Betweenness käme ein Skalierungsfaktor hinzu.

Brandes' Rekursion, eine Skizze der bekannten Herleitung (Brandes 2001), keine eigene Rechnung der Demo:

• Schritt 1: Für eine Quelle \(s\) sei \(\delta_s(v) = \sum_{t} \sigma_{st}(v)/\sigma_{st}\), summiert über alle Ziele \(t \neq s, v\). Dann ist \(C_B(v) = \tfrac12 \sum_{s \neq v} \delta_s(v)\).
• Schritt 2: Ein kürzester Weg von \(s\) über \(v\) zu einem Ziel \(t \neq v\) verlässt \(v\) über genau einen Nachfolger \(w\) mit \(v \in P_s(w)\).
• Schritt 3: Wegen \(\sigma_{sw} = \sum_{v \in P_s(w)} \sigma_{sv}\) laufen genau der Anteil \(\sigma_{sv}/\sigma_{sw}\) der kürzesten Wege von \(s\) nach \(w\) zuletzt über \(v\). Dasselbe gilt für Wege, die hinter \(w\) weiterlaufen.
• Schritt 4: Das Ziel \(t = w\) trägt 1 bei, die Ziele hinter \(w\) tragen \(\delta_s(w)\) bei. Summiert über alle Nachfolger \(w\) ergibt das die Rekursion der Formel oben.
• Schritt 5: \(\delta_s(v)\) hängt nur von Knoten ab, die weiter von \(s\) entfernt sind. Man wertet daher in umgekehrter Reihenfolge der Breitensuche aus: eine Suche und ein Rückwärtsdurchlauf je Quelle, zusammen \(O(m)\), insgesamt \(O(n \cdot m)\).

Was die Vitalität misst

Die Vitalität lässt sich in zwei Teile zerlegen. Das ist eine Rechnung dieser Seite, die die Aussagen unten einordnet.

• Schritt 1: Zerlege \(E(G)\) in die Paare mit \(v\) und die ohne \(v\): \(E(G) = \mathrm{own}(v) + E_{-v}(G)\). Dabei ist \(\mathrm{own}(v) = \sum_{u \neq v} 1/d(v,u)\) über die von \(v\) erreichbaren \(u\), und \(E_{-v}(G)\) die Summe von \(1/d\) über alle Paare ohne \(v\), gerechnet in \(G\).
• Schritt 2: \(E(G \setminus v)\) ist dieselbe Summe über die Paare ohne \(v\), gerechnet in \(G \setminus v\). Also ist \(\mathrm{Vit}(v) = \mathrm{own}(v) + \mathrm{through}(v)\) mit \(\mathrm{through}(v) = E_{-v}(G) - E(G \setminus v)\).
• Schritt 3, nie negativ: Das Entfernen von \(v\) kann Abstände nur vergrößern oder Paare trennen, jeder Summand \(1/d\) wird also nicht größer. Daher ist \(\mathrm{through}(v) \geq 0\). Auch \(\mathrm{own}(v) \geq 0\), und damit \(\mathrm{Vit}(v) \geq 0\).
• Schritt 4, Bedeutung: \(\mathrm{own}(v)\) misst, wie gut \(v\) selbst angebunden ist, verwandt mit der Closeness. \(\mathrm{through}(v)\) misst, was andere Paare durch Umwege oder Trennung verlieren, verwandt mit der Betweenness. Ein Knoten, dessen Entfernen keinen Abstand zwischen anderen Knoten vergrößert, hat \(\mathrm{through}(v) = 0\): seine Vitalität besteht nur aus dem eigenen Anteil.

Nachrechnung dieser Seite mit dem Quelltext der Demo, nicht in den Messwerten unten: Die Summe aller eigenen Anteile macht an der Summe aller Vitalitäten bei ungesperrtem Raster über neun Zehntel aus, bei 30 % Sperrung knapp sechs Zehntel (Median über die 5 Instanzen). In den nachgerechneten Zeilen (Raster und Zufallsgraph, jeweils ohne Sperrung, mit 30 % Sperrung und mit halbiertem Kantenbestand) stimmt die Rangfolge der Closeness mit der des eigenen Anteils fast überein (Rangkorrelation jeweils über neun Zehntel). Die Rangfolge der Betweenness stimmt mit der des Durchgangsanteils überein, mit Rangkorrelation mindestens acht Zehntel. Das stützt, dass die Betweenness den Durchgangsanteil und die Closeness den eigenen Anteil trifft; ein eigener Test dieser Deutung auf weiteren Netzen steht aus.

Durchgerechnetes Beispiel: der Barbell-Graph mit k = 5

Zwei \(K_5\) mit zusammen 10 Knoten, verbunden durch die Brücke zwischen je einem Knoten (den Brückenenden). Die Werte für Grad und Betweenness stehen so in den Messwerten unten; die Herleitung der Zahlen ist eine Rechnung dieser Seite.

Element	Grad	Knoten-Betweenness	Kanten-Betweenness
Clique-Knoten ohne Brückenende (8 Knoten)	4	0	–
Brückenende (2 Knoten)	5	20	–
Brücke (1 Kante)	–	–	25

• Ein Brückenende: Die Paare über den Knoten sind die 4 anderen Knoten seiner Clique mal die 5 Knoten der anderen Clique, also \(4 \cdot 5 = 20\). Paare mit dem Brückenende selbst als Start oder Ziel zählen nicht.
• Die Brücke: Alle \(5 \cdot 5 = 25\) Paare aus verschiedenen Cliquen laufen über sie, also \(a\,(S-a)\) mit \(a = 5\), \(S = 10\). Die Kante ist nie Start oder Ziel, deshalb übertrifft sie das Brückenende.
• Vitalität (Rechnung dieser Seite, keine Messung): Bei einem Clique-Knoten ohne Brückenende bleibt jeder Abstand zwischen den übrigen Knoten gleich, also ist \(\mathrm{through}(v) = 0\). Sein eigener Anteil ist \(4 \cdot 1 + \tfrac{1}{2} + 4 \cdot \tfrac{1}{3}\): vier Nachbarn im Abstand 1, das andere Brückenende im Abstand 2 und vier Knoten der anderen Clique im Abstand 3. Bei einem Brückenende kommt ein Durchgangsanteil hinzu, weil die 4 Knoten seiner Clique dann die andere Clique nicht mehr erreichen. Seine Vitalität ist mehr als doppelt so groß wie die der übrigen acht Knoten.
• Grad und Betweenness bei Knoten: Hier sind die Brückenenden bei beiden Maßen vorn. Der Unterschied liegt in der Spreizung: Der Grad steigt nur von 4 auf 5, die Betweenness von 0 auf 20.

Befunde

Alle Rangkorrelationen sind Spearman-Werte gegen die Vitalität über alle Knoten eines Rasters mit \(12 \times 12 = 144\) Knoten, als Median über 5 feste Instanzen je Zeile, sofern nicht anders genannt. Alle Verfahren sind deterministisch. Die Zeilen mit Zeitangaben beruhen auf der Messung eines Rechners.

Frage	Befund
Stimmen die Implementierungen?	Grad, Closeness, Betweenness (Brandes) und PageRank stimmen mit networkx auf 326 Instanzen überein (Raster, Zufallsgraph, Barbell), ebenso die Kanten-Betweenness. Die naive Betweenness liefert dasselbe wie Brandes auf allen kleinen Testgraphen mit höchstens 10 Knoten, auch bei Gleichständen. Die Vitalität war auf den 326 Instanzen nie negativ.
Stimmt der Brücken-Satz?	Die Kanten-Betweenness ist bei 100 % von 5264 geprüften Brücken exakt \(a\,(S-a)\) (Barbell \(k = 3\) bis \(10\), Raster mit 30 bis 80 % gesperrten Straßen).
Barbell von Hand, \(k = 5\)	Grade 4 (acht Knoten) und 5 (zwei Brückenenden). Die Brücke hat Kanten-Betweenness 25, das Maximum im ganzen Graphen. Die höchste Knoten-Betweenness ist 20, an den Brückenenden.
Welches Maß sagt die Vitalität am besten vorher? Raster, alle gemessenen Sperranteile	Betweenness 0,87 bis 1,00, Grad 0,66 bis 0,78, Closeness 0,57 bis 0,99 (nicht monoton über den Sperranteil), PageRank 0,26 bis 0,67.
Dasselbe, Zufallsgraph, alle gemessenen Sperranteile	Betweenness 0,91 bis 0,96, Grad knapp unter 0,90 bis 0,93, PageRank 0,82 bis 0,91, Closeness 0,78 bis 0,86. Hier schwanken die Werte weniger als im Raster.
Raster mit 30 % gesperrten Straßen	Voreinstellungs-Instanz (eine einzelne Instanz): 144 Knoten, 185 Straßen, 4 Komponenten, 21 Brücken. Über die 5 Messinstanzen sagt die Betweenness die Vitalität am besten vorher, Median der Rangkorrelation 0,87.
Raster ohne Sperrung	Betweenness 1,00 und Closeness 0,99 fast gleichauf, Grad 0,78, PageRank 0,26 als schwächster Vorhersager der ganzen Messreihe.
PageRank gegen Grad	Beide Zeilen gelten für je eine einzelne Instanz (die Voreinstellungs-Instanz), kein Median: bei 30 % gesperrten Straßen 0,92, bei 70 % gesperrten Straßen 0,88. Bei 70 % liegen die PageRank-Werte der Knoten dieser einen Instanz zwischen 0,0014 und 0,0195.
Aufwand der Betweenness, naiv gegen Brandes (Elementarschritte, Raster mit 30 % gesperrten Straßen)	Bei \(n = 9\) Knoten 295 gegen 259 (Faktor 1,1). Bei \(n = 196\) Knoten 11.925.316 gegen 220.050 (Faktor 54,2). Der Faktor wächst über alle gemessenen Größen.
Laufzeit der naiven Betweenness auf dem ungünstigsten der gemessenen Netze	Auf dem Raster ohne Sperrung 0,39 s, 1,63 s und 6,89 s bei \(n = 64\), 81 und 100 Knoten. Bei \(n = 100\) und 30 % Sperrung 0,09 s.

Grenzen und was die Messung zeigt

Was sie belegt:

• Die Implementierungen stimmen auf den genannten Instanzen mit der Bibliothek networkx überein; der Brücken-Satz ist mit der Herleitung oben bewiesen, nicht nur beobachtet.
• Der Aufwandsvergleich gilt für das Zählmaß Elementarschritte auf dem Raster mit 30 % Sperrung, als Median über 5 Instanzen.
• Die Rangfolge der Maße gilt für diese erzeugten Netze, jeweils als Median über 5 Instanzen.

Was sie nicht belegt:

• Kein Maß gewinnt immer. Nachrechnung dieser Seite: Beim Zufallsgraph mit halbiertem Kantenbestand liegt der Grad mit 0,93 knapp vor der Betweenness mit 0,91; dort liegt auch nicht die Closeness (0,86), sondern PageRank (0,82) am weitesten hinten. Der Grad liegt in allen fünf Instanzen dieser Zeile vor der Betweenness. In allen übrigen Zeilen der Messreihe liegt die Betweenness vorn. Unterschiede von wenigen Hundertsteln sind kein Befund, denn die Messreihe nennt nur den Median und keine Streuung.
• Das ungesperrte Raster ist ein einziges Netz. Ohne Sperrung bleibt keine Zufallsquelle für die Kanten, die fünf Instanzen haben dieselbe Kantenmenge. Die Werte für Closeness, Betweenness und PageRank gelten also für ein einziges \(12 \times 12\)-Raster; andere Größen und andere regelmäßige Netze sind nicht gemessen.
• Die Vitalität mischt zwei Dinge. Sie enthält den eigenen Anteil des Knotens (siehe oben) und nicht nur die Umwege der übrigen. Der Befund „Betweenness sagt den Schaden voraus“ gilt für diese Schadensdefinition; andere, etwa die Größe der größten übrig bleibenden Komponente oder die Umwegkosten, sind nicht geprüft und könnten ein anderes Maß bevorzugen.
• Zur Schwäche des PageRank im ungesperrten Raster gibt es nur eine Vermutung, nämlich dass PageRank Unterschiede in der Gradverteilung braucht; sie ist nicht getestet. Nachrechnung dieser Seite: Unter den Knoten mit vier Nachbarn ist PageRank in der Mitte am kleinsten und nahe dem Rand am größten, die Vitalität ist dort umgekehrt verteilt (Rangkorrelation innerhalb dieser Knoten fast \(-1\)). Als Ursache liegt nahe, dass Randknoten wenige Nachbarn haben und ihre Masse stärker bündeln; auch das ist nicht getestet. PageRank und Grad stimmen im ungesperrten Raster in der Rangfolge nur zu etwa vier Fünfteln überein, bei den oben genannten Instanzen mit 30 und 70 % Sperrung stärker.
• Der Brücken-Satz ist an Beispielen geprüft, die Tests der Demo verlangen aber nur mindestens 200 geprüfte Brücken. Die Zahl 5264 ergab eine Nachrechnung dieser Seite mit Seitenlängen 3 bis 10, 5 Instanzen je Sperranteil von 30 bis 80 % und den Barbell-Graphen mit \(k = 3\) bis \(10\); das \(12 \times 12\)-Raster der übrigen Messungen kommt darin nicht vor.
• Exponentielles Wachstum der naiven Betweenness ist hier nur mit drei Messpunkten vereinbar, nicht gemessen. Eine Rechnung dieser Seite liefert den Grund: Zwischen gegenüberliegenden Ecken eines \(L \times L\)-Rasters gibt es \(\binom{2L-2}{L-1}\) kürzeste Wege, und die naive Betweenness zählt sie alle einzeln.
• Zählmaß statt Laufzeit: Die Faktoren gelten für Elementarschritte. Echte Laufzeiten hängen von der Implementierung ab; die Zeitangaben oben stammen von einem Rechner.
• Nicht umgesetzt: gerichtete Netze (Einbahnstraßen, Zitationen), die eigene Varianten von Betweenness und PageRank brauchen. Alle Netze sind erzeugt, keine echten Verkehrs- oder Sozialnetze.

Erweiterungen und Verweise

Verwandte Fragen behandeln weitere Demos und eine Erklärseite:

• Brücken finden: Die bridges-demo findet Brücken und Artikulationspunkte in einer einzigen Tiefensuche.
• Gezielter Ausfall: Die Seite Zufall oder Angriff im Netz erklärt, wie ein Netz schrumpft, wenn Knoten zufällig oder gezielt nach Grad oder Betweenness entfallen.
• Kritische Knoten absichern: Die haertung-demo härtet ein Netz mit begrenztem Budget.
• PageRank an echten Daten: Die interne-verlinkung-demo wendet PageRank auf den Linkgraphen einer Website an.

Quellen

• Freeman, L. C. (1977): A set of measures of centrality based on betweenness. Sociometry 40(1), 35–41.
• Brandes, U. (2001): A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25(2), 163–177.
• Brin, S., & Page, L. (1998): The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems 30(1–7), 107–117.
• Latora, V., & Marchiori, M. (2001): Efficient behavior of small-world networks. Physical Review Letters 87(19), 198701.
• Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/centrality-demo.

Die Literaturangaben stammen aus der Dokumentation der Demo und sind für diese Seite nicht im Original nachgeschlagen. Dass die Vitalität als Effizienzverlust bei Latora und Marchiori (2001) definiert ist, ist nicht geprüft: Sie kann auch aus einer späteren Arbeit der beiden stammen (aus dem Gedächtnis, nicht geprüft); die Seite schreibt ihnen nur die Effizienz zu. Die Closeness-Variante schreibt die Demo Wasserman und Faust (1994) zu, die Idee Bavelas (1950); beides ist nur mit Namen genannt. Zerlegung der Vitalität, Berichtigung zur Eindeutigkeit im Brücken-Satz und alle als Nachrechnung gekennzeichneten Angaben sind Rechnungen dieser Seite und keine Messungen der Demo.