In der Graphentheorie und in der Analyse sozialer Netzwerke ist der Clustering- Koeffizient eines Graphen (auch als Agglomerations- , Verbindungs- , Gruppierungs- , Aggregations- oder Transitivitätskoeffizient bezeichnet ) ein Maß für die Gruppierung von Knoten in einem Netzwerk. Genauer gesagt ist dieser Koeffizient die Wahrscheinlichkeit, dass zwei Knoten verbunden sind und wissen, dass sie einen gemeinsamen Nachbarn haben.
Dies ist einer der in sozialen Netzwerken untersuchten Parameter : Sind die Freunde meiner Freunde meine Freunde?
Es gibt zwei verschiedene Definitionen des Clustering- Koeffizienten : eine globale Version und eine lokale Version.
Der Gesamtclusterkoeffizient ist definiert als:
Dabei ist ein Dreieck eine Clique aus drei Knoten.
Wenn die Anzahl der Paare unterschiedlicher Nachbarn eines Gradknotens gleich ist , erhalten wir:
Wo ist der Grad des Knotens und die Menge der Knoten des Graphen.
Wir haben mit Gleichheit genau dann, wenn der Graph eine Menge von Cliquen mit einer Größe von mindestens 3 ist (ein vollständiger Graph, wenn der Graph verbunden ist).
Der lokale Clustering- Koeffizient eines Knotens ist definiert als:
ist
Es ist der Bruchteil seiner Paare verbundener Nachbarn, der gemäß Konvention gleich 0 ist .
Wir haben mit Gleichheit genau dann, wenn der Knoten und seine Nachbarschaft eine Clique von mindestens 3 Knoten bilden.
Indem wir den Durchschnitt der lokalen Koeffizienten nehmen, erhalten wir den durchschnittlichen lokalen Koeffizienten:
.Wir haben auch mit Gleichheit genau dann, wenn der Graph eine Menge von Cliquen mit einer Größe von mindestens 3 ist.
Der globale Koeffizient wird aus den lokalen Koeffizienten ausgedrückt als:
Es handelt sich daher um einen gewichteten Durchschnitt der lokalen Koeffizienten, der sich vom durchschnittlichen lokalen Koeffizienten unterscheidet , außer in besonderen Fällen ( z. B. regulärer Graph ). Hochgradige Knoten haben daher mehr Gewicht als niedriggradige Knoten. Bei den Gewichten kommt es darauf an, einen Knoten proportional zur Anzahl seiner Paare unterschiedlicher Nachbarn auszuwählen, sodass der globale Clusterkoeffizient als die Wahrscheinlichkeit interpretiert wird, dass zwei unterschiedliche Knoten verbunden sind und wissen, dass sie einen Nachbarn gemeinsam haben.
Durch Notieren der Adjazenzmatrix des Graphen, einer binären Matrix, deren Eingabe genau dann gleich 1 ist, wenn die Knoten Nachbarn sind, wird der Clusterkoeffizient geschrieben:
In der Tat ist der Zähler gleich dem 6-fachen der Anzahl der Dreiecke und der Nenner ist gleich .
In Abwesenheit von Schleifen (Diagonale Null) ist der Zähler die Summe der diagonalen Elemente der Matrix und der Nenner die Summe der nicht diagonalen Elemente der Matrix .
Es gibt Versionen des Koeffizienten, die für bestimmte Diagrammtypen geeignet sind, z. B. gewichtete Diagramme oder zweigeteilte Diagramme .
Das Watts-Strogatz-Modell ermöglicht die Erzeugung von Zufallsgraphen mit sowohl einem hohen Clusterkoeffizienten als auch der sogenannten Small World-Eigenschaft . Diese beiden Eigenschaften sind charakteristisch für große reale Graphen, wie sie beispielsweise von sozialen Netzwerken gebildet werden.
Der globale Koeffizient wird häufig Barrat und Weigt für den im Jahr 2000 veröffentlichten Artikel Über die Eigenschaften von Netzwerkmodellen für kleine Welten zugeschrieben. Der lokale Durchschnittskoeffizient wird Watts und Strogatz für den Artikel Kollektive Dynamik von Netzwerken für kleine Welten aus zugeschrieben 1998.