Clusterkoeffizient

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Drei Knoten sind oben zu einem Dreieck verbunden, unten bilden drei Knoten ein „verbundenes Tripel“. Das Dreieck hat einen globalen Clusterkoeffizient von 1, da man 1 Dreieck zählt und 3 „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 sind ein verbundenes Tripel 3 Knoten, von denen mindestens einer mit beiden anderen verbunden ist. Jedes Dreieck ist somit auch ein verbundenes Tripel, d.h. sämtliche Dreiecke bilden eine Teilmenge sämtlicher verbundener Tripel. Der Faktor 3 im Zähler der Formel kompensiert den Fakt, dass ein Dreieck auch als 3 verbundene Tripel gillt.[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[Bearbeiten]

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 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 gerichteten 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. Dies ist in der - JUNG-Bibliothek mit dem Wert 1 umgesetzt und resultiert in unnatürlich hohen globalen Clusterkoeffizienten, wenn viele Knoten den Grad 1 haben. Andere Autoren definieren den lokalen Clusterkoeffizienten für isolierte Knoten und Knoten vom Grad 1 durch C_i=0.[1] Für nebenstehendes Bild ergeben sich mit der letztgenannten Konvention folgende lokale Clusterkoeffizienten: 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^N_i 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}{10} 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. Natürliche Netzwerke sind meist vom Kleine-Welt-Typ.

Siehe auch[Bearbeiten]

Quellen[Bearbeiten]

  1. a b c d M. E. J. Newman: The Structure and Function of Complex Networks, SIAM Review 45, 167 (2003), S. 183
  2. a b 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, S.H. Strogatz: Collective dynamics of ‘small-world’ networks, Nature 393 (1998) 440