Clustering-Koeffizient

Der Clusterkoeffizient (clustering coefficient) ist in der Graphentheorie ein Maß für den Grad der Verlinkung in einem Graphen. Man unterscheidet den lokalen Clusterkoeffizienten für einen bestimmten Knoten des Graphen und den globalen Clusterkoeffizienten für den gesamten Graphen (auch Vernetzungsgrad).

Der lokale Clusterkoeffizient eines Knotens v in einem Graphen G bezeichnet in der Graphentheorie den Quotienten aus der Anzahl der Kanten die zwischen seinen Nachbarn tatsächlich verlaufen und der Anzahl Kanten, die zwischen seinen Nachbarn maximal verlaufen könnten. Die Formel für den Grad eines Knotens i berechnet sich wie folgt:

$C_i = \frac{2n}{k_{i}\left( k_{i}-1 \right) }$

Der globale Clusterkoeffizient gibt das Verhältnis der vorhandenen Links zu den möglichen Links an. Ein vollständiger Graph, in dem jeder Knoten mit jedem verbunden ist, hat den maximal möglichen Clusterkoeffizient 1. Der globale Clusterkoeffizient lässt sich auch als Mittelwert der lokalen Clusterkoeffizienten aller Knoten berechnen.

Kleine-Welt-Netzwerke haben einen sehr hohen durchschnittlichen Clusterkoeffizienten. In einem Zufallsgraphen ist der Clusterkoeffizient im Gegensatz zu natürlichen Netzwerken relativ gering.

Siehe auch: Clusteranalyse, Vernetzung