Clusterkoeffizient
aus Wikipedia, der freien Enzyklopädie
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 Clustering-Koeffizient eines Knotens v in einem Graphen G bezeichnet man 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.
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 Clustering-Koeffizienten. In einem Zufallsgraphen ist der Clusterkoeffizient im Gegensatz zu natürlichen Netzwerken relativ gering.
Siehe auch: Clusteranalyse, Vernetzung
