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

{\frac {3}{4}}

, da man 1 Dreieck zählt und 4 „verbundene Tripel“

Der globale Clusterkoeffizient $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).

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 $C=1$ , was einer perfekten Clique entspricht.

Lokaler Clusterkoeffizient

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

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

Diese Formel gilt für einen ungerichteten Graph, für einen gerichteten Graph entfällt der Faktor 2, da doppelt so viele Kanten zwischen den Nachbarn möglich sind wie in 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 $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 $C_{2}$ ist daher ${\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 $C_{i}=0$ .^[1] Mit der letztgenannten Konvention ergeben sich für nebenstehendes Bild folgende lokale Clusterkoeffizienten $C_{1}$ bis $C_{6}$ :

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

Der lokale Clusterkoeffizient kann äquivalent auch als

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 wird oft auch das Mittel aller lokalen Clusterkoeffizienten bezeichnet:

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 $C$ und $C'$ können sehr unterschiedliche Ergebnisse liefern: Für das gezeigte Netzwerk ergibt sich $C={\tfrac {3}{11}}$ und $C'={\tfrac {5}{18}}$ .

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

Kleine-Welt-Netzwerke haben – unabhängig von der gewählten Definition – meist hohe Clusterkoeffizienten, Zufallsgraphen dagegen eher niedrige.

Siehe auch

Weblinks

Commons: Clustering coefficient – Sammlung von Bildern, Videos und Audiodateien

Quellen

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

[newman-1] M. E. J. Newman: The Structure and Function of Complex Networks, SIAM Review 45, 167 (2003), S. 183

[boccaletti-2] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. U. Hwang: Complex networks: Structure and dynamics, Physics Reports 424, 175 (2006)

[WattsStrogatz1998-3] D. J. Watts and Steven Strogatz: Collective dynamics of 'small-world' networks. In: Nature. 393. Jahrgang, Nr. 6684, Juni 1998, S. 440–442, doi:10.1038/30918, PMID 9623998, bibcode:1998Natur.393..440W (nature.com).

[1]

[2]

[3]