Clusterkoeffizient

Clusterkoeffizient

Der Clusterkoeffizient (engl. 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 i in einem Graphen G bezeichnet in der Graphentheorie den Quotienten aus der Anzahl der Kanten, die zwischen seinen ki Nachbarn tatsächlich verlaufen (n), und der Anzahl Kanten, die zwischen diesen Nachbarn maximal verlaufen können (\tfrac{1}{2} k_i (k_i-1)). Der Clusterkoeffizient Ci eines Knotens i berechnet sich daher wie folgt:

C_i = \frac{2n}{k_i (k_i-1)}.
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 Clusterkoeffizent C1 = 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 Clusterkoeffizent C2 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.

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


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • Ballungsanalyse — Unter Clusteranalyse (der Begriff Ballungsanalyse wird selten verwendet) versteht man strukturentdeckende, multivariate Analyseverfahren zur Ermittlung von Gruppen (Clustern) von Objekten, deren Eigenschaften oder Eigenschaftsausprägungen… …   Deutsch Wikipedia

  • Cluster-Analyse — Unter Clusteranalyse (der Begriff Ballungsanalyse wird selten verwendet) versteht man strukturentdeckende, multivariate Analyseverfahren zur Ermittlung von Gruppen (Clustern) von Objekten, deren Eigenschaften oder Eigenschaftsausprägungen… …   Deutsch Wikipedia

  • Clustering — Unter Clusteranalyse (der Begriff Ballungsanalyse wird selten verwendet) versteht man strukturentdeckende, multivariate Analyseverfahren zur Ermittlung von Gruppen (Clustern) von Objekten, deren Eigenschaften oder Eigenschaftsausprägungen… …   Deutsch Wikipedia

  • Clustering-Verfahren — Unter Clusteranalyse (der Begriff Ballungsanalyse wird selten verwendet) versteht man strukturentdeckende, multivariate Analyseverfahren zur Ermittlung von Gruppen (Clustern) von Objekten, deren Eigenschaften oder Eigenschaftsausprägungen… …   Deutsch Wikipedia

  • Clusterverfahren — Unter Clusteranalyse (der Begriff Ballungsanalyse wird selten verwendet) versteht man strukturentdeckende, multivariate Analyseverfahren zur Ermittlung von Gruppen (Clustern) von Objekten, deren Eigenschaften oder Eigenschaftsausprägungen… …   Deutsch Wikipedia

  • Vernetzungsgrad — Vernetzung ist ein Begriff aus der Systemtheorie. Ein System besteht aus einzelnen Teilen, die durch Ursache Wirkungs Beziehungen und allgemeine und besondere Systemeigenschaften miteinander vielfältig verknüpft sind. Bildhaft spricht man daher… …   Deutsch Wikipedia

  • Bayes'sches Netz — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel gelöscht, die nicht… …   Deutsch Wikipedia

  • Bayes'sches Netzwerk — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel gelöscht, die nicht… …   Deutsch Wikipedia

  • Bayes-Netz — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel gelöscht, die nicht… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”