Clusterkoeffizient - LinkFang.de





Clusterkoeffizient


Der Clusterkoeffizient (engl. clustering coefficient) ist in der Graphentheorie ein Maß für die Cliquenbildung bzw. Transitivität in einem Netzwerk. Sind alle Nachbarn eines Knotens paarweise verbunden, also jeder mit jedem, dann bilden sie eine 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.[1] Man unterscheidet zwischen dem globalen Clusterkoeffizienten, der das gesamte Netzwerk charakterisiert und dem lokalen Clusterkoeffizienten, der einen einzelnen Knoten charakterisiert.

Globaler Clusterkoeffizient

Der globale Clusterkoeffizient [math]C[/math], auch Transitivität genannt,[2] 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 sind ein verbundenes Tripel 3 Knoten, von denen mindestens einer mit beiden anderen verbunden ist. Jedes Dreieck ist somit auch ein verbundenes Tripel, d.h. sämtliche Dreiecke bilden eine Teilmenge sämtlicher verbundener Tripel. Der Faktor 3 im Zähler der Formel kompensiert den Fakt, dass ein Dreieck auch als 3 verbundene Tripel gilt.[2] 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[3] lokale Clusterkoeffizient eines Knotens [math]i[/math] in einem Graphen [math]G[/math] bezeichnet in der Graphentheorie den Quotienten aus der Anzahl der Kanten, die zwischen seinen [math]k_i[/math] Nachbarn tatsächlich verlaufen ([math]n[/math]), und der Anzahl 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.

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. 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. Andere Autoren definieren den lokalen Clusterkoeffizienten für isolierte Knoten und Knoten vom Grad 1 durch [math]C_i=0[/math].[1] Für nebenstehendes Bild ergeben sich mit der letztgenannten Konvention folgende lokale Clusterkoeffizienten: [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.[1] 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.[1]

Kleine-Welt-Netzwerke haben – unabhängig von der gewählten Definition – meist hohe Clusterkoeffizienten, Zufallsgraphen dagegen eher niedrige. Natürliche Netzwerke sind meist vom Kleine-Welt-Typ.

Siehe auch

Quellen

  1. 1,0 1,1 1,2 1,3 M. E. J. Newman: The Structure and Function of Complex Networks, SIAM Review 45, 167 (2003), S. 183
  2. 2,0 2,1 S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. U. Hwang: Complex networks: Structure and dynamics, Physics Reports 424, 175 (2006)
  3. D. J. Watts and Steven Strogatz: Collective dynamics of 'small-world' networks. In: Nature. 393, Nr. 6684, June 1998, S. 440–442. Bibcode: 1998Natur.393..440W . doi:10.1038/30918 . PMID 9623998 .

Kategorien: Graphentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Clusterkoeffizient (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.