Clusterkoeffizient

Der Clusterkoeffizient (engl. clustering coefficient) ist in der Graphentheorie ein Maß für die Cliquenbildung bzw. Transitivität in einem Netzwerk. Sind alle Nachbarn eines Knotens paarweise verbunden, also jeder mit jedem, dann bilden sie eine Clique. Dies ist gleichbedeutend mit dem Begriff der Transitivität, denn innerhalb einer Clique gilt: Ist A mit B verbunden und A mit C, so sind auch B und C verbunden.[1] Man unterscheidet zwischen dem globalen Clusterkoeffizienten, der das gesamte Netzwerk charakterisiert und dem lokalen Clusterkoeffizienten, der einen einzelnen Knoten charakterisiert.

Globaler Clusterkoeffizient

Drei Knoten sind oben zu einem Dreieck verbunden, unten bilden drei Knoten ein „verbundenes Tripel“. Der Graph hat einen globalen Clusterkoeffizienten von ${\displaystyle {\frac {3}{4}}}$, da man 1 Dreieck zählt und 4 „verbundene Tripel“

Der globale Clusterkoeffizient ${\displaystyle C}$, auch Transitivität genannt,[2] ist definiert als das Verhältnis der Anzahl von Dreiecken zu „verbundenen Tripeln“ in einem Netzwerk (siehe nebenstehende Abbildung).

${\displaystyle C={\frac {3\times {\text{Anzahl der Dreiecke}}}{\text{Anzahl der verbundenen Tripel}}}}$.

Ein Dreieck sind drei Knoten, die alle untereinander verbunden sind. Dagegen ist ein verbundenes Tripel ein Knoten A und ein ungeordnetes Paar von zwei Knoten B und C, wobei A Kanten zu B und C hat.[1] Jedes Dreieck bildet somit 3 verbundene Tripel. Der Faktor 3 im Zähler der Formel kompensiert dies.[2] Nur mit dem Faktor 3 erhält ein Netzwerk bestehend aus einem einzigen Dreieck den Clusterkoeffizient ${\displaystyle C=1}$, was einer perfekten Clique entspricht.

Lokaler Clusterkoeffizient

Der von Duncan Watts und Steven Strogatz definierte[3] lokale Clusterkoeffizient eines Knotens ${\displaystyle i}$ in einem Graphen ${\displaystyle G}$ bezeichnet in der Graphentheorie den Quotienten aus der Anzahl der Kanten, die zwischen seinen ${\displaystyle k_{i}}$ Nachbarn tatsächlich verlaufen (${\displaystyle =n}$), und der Anzahl an Kanten, die zwischen diesen Nachbarn maximal verlaufen könnten (ungerichteter Graph: ${\displaystyle {\tfrac {1}{2}}k_{i}(k_{i}-1)}$):

${\displaystyle C_{i}={\frac {2n}{k_{i}(k_{i}-1)}}.}$

Diese Formel g​ilt für e​inen ungerichteten Graph, für e​inen gerichteten Graph entfällt d​er Faktor 2, d​a doppelt s​o viele Kanten zwischen d​en Nachbarn möglich s​ind wie i​n einem ungerichteten Graph.

Graph mit sechs Knoten

In dem nebenstehenden Graph hat der Knoten 1 die Nachbarn 2 und 5. Zwischen diesen Nachbarn ist eine Kante möglich und auch vorhanden, so dass der Clusterkoeffizient ${\displaystyle C_{1}=1}$ ist. Der Knoten 2 hat 3 Nachbarn, zwischen denen 3 Kanten möglich sind, jedoch sind nur die Nachbarknoten 1 und 5 durch eine Kante verbunden. Der Clusterkoeffizient ${\displaystyle C_{2}}$ ist daher ${\displaystyle {\tfrac {1}{3}}}$. Der Clusterkoeffizient von Knoten 6, also sämtlicher Knoten des Grades 1, ergibt laut Berechnung die Division Null durch Null. In manchen Implementierungen wird dies mit dem Wert 1 umgesetzt; bei vielen Knoten dieser Art resultiert ein unnatürlich hoher globaler Clusterkoeffizient. Andere Autoren wiederum definieren den lokalen Clusterkoeffizienten für isolierte Knoten und Knoten vom Grad 1 durch ${\displaystyle C_{i}=0}$.[1] Mit der letztgenannten Konvention ergeben sich für nebenstehendes Bild folgende lokale Clusterkoeffizienten ${\displaystyle C_{1}}$ bis ${\displaystyle C_{6}}$:

${\displaystyle 1,{\frac {1}{3}},0,0,{\frac {1}{3}},0}$.

Der lokale Clusterkoeffizient k​ann äquivalent a​uch als

${\displaystyle C_{i}={\frac {{\text{Anzahl der Dreiecke verbunden mit Knoten }}\,i}{{\text{Anzahl der „verbundenen Tripel“ zentriert an Knoten }}\,i}}}$

definiert werden.

Als globaler Clusterkoeffizient w​ird oft a​uch das Mittel a​ller lokalen Clusterkoeffizienten bezeichnet:

${\displaystyle C'={\frac {1}{N}}\sum _{i}^{N}C_{i}}$.

Diese Definition liefert nicht denselben Wert wie die erste Definition des globalen Clusterkoeffizientens; die Reihenfolge der Berechnung des Dreieck-zu-Tripel-Verhältnisses einesteils und der Mittelung andererseits ist vertauscht. Der Unterschied besteht effektiv in der Umkehrung der Operationen der Verhältnisberechnung von Dreiecken und Tripeln und der Mittelung: Die letztere Definition ist das Mittel des Dreieck-zu-Tripel-Verhältnisses, die erstere berechnet in gewisser Weise das Verhältnis der mittleren Anzahl von Dreiecken zu der mittleren Anzahl von Tripeln.[1] Beide Definitionen ${\displaystyle C}$ und ${\displaystyle C'}$ können sehr unterschiedliche Ergebnisse liefern: Für das gezeigte Netzwerk ergibt sich ${\displaystyle C={\tfrac {3}{11}}}$ und ${\displaystyle C'={\tfrac {5}{18}}}$.

${\displaystyle C'}$ lässt sich auf dem Computer einfacher berechnen und wird daher in numerischen Studien häufig verwendet.[1]

Kleine-Welt-Netzwerke h​aben – unabhängig v​on der gewählten Definition – m​eist hohe Clusterkoeffizienten, Zufallsgraphen dagegen e​her niedrige.

Siehe auch

• Clusteranalyse
• Vernetzung

Quellen

1. M. E. J. Newman: The Structure and Function of Complex Networks, SIAM Review 45, 167 (2003), S. 183
2. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. U. Hwang: Complex networks: Structure and dynamics, Physics Reports 424, 175 (2006)
3. D. J. Watts and Steven Strogatz: Collective dynamics of 'small-world' networks. In: Nature. 393, Nr. 6684, Juni 1998, S. 440–442. bibcode:1998Natur.393..440W. doi:10.1038/30918. PMID 9623998.