Zentralitätsindizes

Zentralitätsindizes sind Maßzahlen für die Bedeutung eines einzelnen Knoten für ein Netzwerk. Da es viele unterschiedliche Sichtweisen bzgl. der Bedeutung eines Knotens gibt, existieren einige verschiedene Definitionen für Zentralitätsmaße nebeneinander. Die hier vorgestellten Indizes sind distanzbasiert, d.h. sie beziehen sich auf die Anzahl und Länge der kürzesten Pfade zwischen den Knoten.


Im folgenden sei G = (V,E) ein ungerichteter, zusammenhängender Graph, V die Knotenmenge, E die Kantenmenge.
Für zwei Knoten v, w aus V sei d(v,w) die Länge des kürzesten Pfades von v nach w.
 

1) Ekzentrizität (Eccentricity)

Die Ekzentrizität eines Knotens v gibt die Länge des längsten aller kürzesten Pfade von v zu allen anderen Knoten an.

E(v) = max { d(v,w) | w aus V }

Der Knoten mit der niedrigsten Ekzentrität bildet das "Zentrum" des Graphen.

Dieser Knoten wäre z.B. ein idealer Ort für ein Krankenhaus, da der längstmögliche Weg zu einer eventuellen Unfallstelle minimiert wird.


2) Closeness-Zentralität

Die Closeness-Zentralität eines Knotens v gibt die Summe der Länge aller kürzesten Pfade von v zu allen anderen Knoten an. Der Index ergibt sich in der Regel aus dem reziproken Wert der Summe, d.h. damit der Zentralitätsindex mit steigender Summe immer kleiner wird.
 

Der Knoten mit der höchsten Closeness-Zentralität wird auch "Median" des Graphen genannt.

Dieser Knoten könnte z.B. für eine Geschäftseröffnung interessant sein, da die Summe der Wege, den alle Kunden hierhin zurücklegen müssen minimiert wird.

(Anm.: Im Programm wird nur die Summe berechnet und im Knoten vermerkt um ein ganzzahliges Ergebnis zu erhalten. Der Median ist dann der Punkt mit dem kleinsten Wert.)


3) Radiality-Zentralität

Die Radiality-Zentralität verfolgt die gleiche Sichtweise wie die Closeness-Zentralität. Nach beiden Formeln erhält man eine gleiche Rangfolge der Knoten, da die Summe aller kürzesten Pfade alleiniges Kriterium ist. Nach der Radiality-Methode wird der Wert jedoch noch normiert.
 

ΔG := Länge des längsten aller kürzesten Pfade zwischen allen Knoten ("Durchmesser" des Graphen)
n = Anzahl der Knoten in G


4) Centroid Values

Um eine andere Perspektive handelt es sich beim Centroid-Index. Angenommen man wählt einen Knotenpunkt aus um ein Geschäft zu eröffnen. Danach wählt ein Konkurrent einen anderen Knotenpunkt. Die Kunden werden dort einkaufen, wohin sie es kürzer haben. Der Centroid Value eines Knotens v gibt nun an, wieviele Knoten näher am Konkurrenzgeschäft liegen, wenn der Konkurrent die für sich beste Wahl trifft.

Der Knoten mit dem größten Centroid Value (der "Centroid") ist dann also der Knoten, an dem die wenigsten Kunden verloren gehen. Ist der Wert negativ, werden mehr Kunden zum Konkurrenten abwandern als bleiben.

CF(u) = min{ f(u,v) | v aus V-u }

f(u,v) = γu (v) - γv (u)

γu (v) = #{w aus V | d(w,u) < d(v,u) }

γu (v) gibt an, für wieviele Knoten der kürzeste Pfad nach u kürzer ist als der kürzeste Pfad nach v


5) Stress-Zentralität

Die vorherigen Indizes betrachteten alle jeweils die Länge der kürzesten Pfade. Der Stress-Index für einen Knoten v dagegen gibt an, auf wievielen kürzesten Pfade zwischen allen Knoten im Graph v liegt. Dabei soll v ein echter "Durchgangsknoten" sein, also weder am Anfang noch am Ende des Pfades liegen.
 

σst(v) = Anzahl aller kürzesten Pfade von s nach t, die v enthalten.

Mit dem Stress-Index können z.B. in einem Computernetzwerk, in dem alle Rechner miteinander kommunzieren, einzelne Rechner oder Leitungen identifiziert werden, durch die besonders viel Information fließt bzw. die besonders stark belastet sind.

(Anm.: Während die anderen Indizes einen zusammenhängenden Graph vorraussetzen, kann der Stress-Index auch für nicht zusammenhängende Graphen berechnet werden.)


6) Betweenness-Zentralität

Der Betweenness-Index verfolgt das gleiche Prinzip wie der Stress-Index. Die Indizes unterscheiden sich nicht, wenn es zwischen allen Knotenpaaren genau einen kürzesten Weg gibt. Die Betweenness-Zentralität beachtet aber auch die Möglichkeit, dass es mehrere (gleichlange) kürzeste Pfade zwischen zwei Knoten gibt und misst für einen Knoten v dann jeweils den Anteil der kürzesten Pfade, die v enthalten, an der Gesamtzahl.
 

σst(v) = Anzahl aller kürzesten Pfade von s nach t, die v enthalten.
σst     = Anzahl aller kürzesten Pfade von s nach t