imported>Ulanwp: Fehlenden Sprachparameter eingefügt

2026-02-20T10:27:28Z

Fehlenden Sprachparameter eingefügt

Neue Seite

Der '''Clusterkoeffizient''' (engl. ''clustering coefficient'') ist in der [[Graphentheorie]] ein Maß für die [[vollständiger Graph|Cliquenbildung]] bzw. [[Transitive Relation|Transitivität]] in einem [[Graph (Graphentheorie)|Netzwerk]]. Sind alle Nachbarn eines [[Knoten (Graphentheorie)|Knotens]] paarweise verbunden, also jeder mit jedem, dann bilden sie eine [[Clique (Graphentheorie)|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.<ref name="newman">M. E. J. Newman: ''The Structure and Function of Complex Networks'', SIAM Review '''45''', 167 (2003), S. 183</ref>
Man unterscheidet zwischen dem '''globalen Clusterkoeffizienten''', der das gesamte Netzwerk charakterisiert und dem '''lokalen Clusterkoeffizienten''', der einen einzelnen Knoten charakterisiert.

== Globaler Clusterkoeffizient ==
[[Datei:triple.svg|mini|Drei Knoten sind oben zu einem Dreieck verbunden, unten bilden drei Knoten ein „verbundenes Tripel“. Der Graph hat einen globalen Clusterkoeffizienten von <math>\frac{3}{4}</math>, da man 1 Dreieck zählt und 4 „verbundene Tripel“]]
Der ''globale Clusterkoeffizient'' <math>C</math>, auch ''Transitivität'' genannt,<ref name="boccaletti">S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. U. Hwang: ''Complex networks: Structure and dynamics, Physics Reports'' '''424''', 175 (2006)</ref> ist definiert als das Verhältnis der Anzahl von Dreiecken zu „verbundenen Tripeln“ in einem Netzwerk (siehe nebenstehende Abbildung).
:<math>C=\frac{3\times \text{Anzahl der Dreiecke}}{\text{Anzahl der verbundenen Tripel}}</math>.
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.<ref name="newman" /> Jedes Dreieck bildet somit 3 verbundene Tripel. Der Faktor 3 im Zähler der Formel kompensiert dies.<ref name="boccaletti" /> Nur mit dem Faktor 3 erhält ein Netzwerk bestehend aus einem einzigen Dreieck den Clusterkoeffizient <math>C=1</math>, was einer perfekten Clique entspricht.

== Lokaler Clusterkoeffizient ==
Der von [[Duncan Watts]] und [[Steven Strogatz]] definierte<ref name=WattsStrogatz1998>{{cite journal |author=[[D. J. Watts]] and [[Steven Strogatz]] |title=Collective dynamics of 'small-world' networks |journal=[[Nature]] |volume=393 |issue=6684 |pages=440–442 |bibcode=1998Natur.393..440W |doi=10.1038/30918 |pmid=9623998 |date=1998-06 |url=https://www.nature.com/articles/30918 |language=en}}</ref> ''lokale Clusterkoeffizient'' eines Knotens <math>i</math> in einem Graphen <math>G</math> bezeichnet in der Graphentheorie den [[Quotient]]en aus der Anzahl der Kanten, die zwischen seinen <math>k_i</math> [[Nachbarschaft (Graphentheorie)|Nachbarn]] tatsächlich verlaufen (<math>= n</math>), und der Anzahl an Kanten, die zwischen diesen Nachbarn maximal verlaufen könnten ([[ungerichteter Graph]]: <math>\tfrac{1}{2} k_i (k_i-1)</math>):
:<math>C_i = \frac{2n}{k_i (k_i-1)}.</math>
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.
[[Datei:6n-graf.svg|mini|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 <math>C_1=1</math> 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 <math>C_2</math> ist daher <math>\tfrac{1}{3}</math>. 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 <math>C_i=0</math>.<ref name="newman" />

Mit der letztgenannten Konvention ergeben sich für nebenstehendes Bild folgende lokale Clusterkoeffizienten <math>C_1</math> bis <math>C_6</math>:

<math>1,\frac{1}{3},0,0,\frac{1}{3},0</math>.

Der lokale Clusterkoeffizient kann äquivalent auch als
:<math>C_i=\frac{\text{Anzahl der Dreiecke verbunden mit Knoten }\,i}{\text{Anzahl der „verbundenen Tripel“ zentriert an Knoten }\,i}</math>
definiert werden.

Als globaler Clusterkoeffizient wird oft auch das Mittel aller lokalen Clusterkoeffizienten bezeichnet:
:<math>C'=\frac{1}{N}\sum^N_i C_i</math>.
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.<ref name="newman" /> Beide Definitionen <math>C</math> und <math>C'</math> können sehr unterschiedliche Ergebnisse liefern: Für das gezeigte Netzwerk ergibt sich <math>C=\tfrac{3}{11}</math> und <math>C'=\tfrac{5}{18}</math>.

<math>C'</math> lässt sich auf dem Computer einfacher berechnen und wird daher in numerischen Studien häufig verwendet.<ref name="newman" />

[[Kleine-Welt-Phänomen|Kleine-Welt-Netzwerk]]e haben – unabhängig von der gewählten Definition – meist hohe Clusterkoeffizienten, [[Zufallsgraph]]en dagegen eher niedrige.

== Siehe auch ==
* [[Clusteranalyse]]
* [[Vernetzung]]

== Weblinks ==
{{Commonscat|Clustering coefficient}}

== Einzelnachweise ==
<references />

[[Kategorie:Graphentheorie]]

Clusterkoeffizient - Versionsgeschichte

imported>Ulanwp: Fehlenden Sprachparameter eingefügt