Clustering-Koeffizient

Eine bekannte Eigenschaft von sozialen Netzwerken ist die Cliquenbildung. In einer Clique aus Freunden oder Bekannten kennt jede einzelne Person alle anderen Personen der Clique. Diese Neigung, Gruppen (Cluster) zu bilden, wird durch den Clustering-Koeffizient quantifiziert [10]. Dazu wird ein bestimmter Knoten $j$ mit $k_j$ Verbindungen zu $k_j$ anderen Knoten in einem Netzwerk betrachtet. Wenn diese Nachbarn Teil der Clique sind, dann existieren $k_j(k_j-1)/2$ Verbindungen zwischen diesen Knoten. Der Quotient zwischen der tatsächlichen Anzahl Verbindungen $E_j$ zwischen diesen $k_j$ Knoten und der Anzahl Verbindungen in einer vollständigen Clique ergibt den Clustering-Koeffizient des Knoten $j$

$$C_j = \frac{2E_j}{k_j(k_j-1)}$$ (2.4)

Der Clustering-Koeffizient des gesamten Netzwerks ist der Mittelwert über alle $C_j$ der einzelnen Knoten. In Zufallsgraphen entspricht der Clustering-Koeffizient $C=p$, da jede einzelne der möglichen Verbindungen mit der Wahrscheinlichkeit $p$ existiert. In den meisten realen Netzwerken ist der Clustering-Koeffizient deutlich größer als bei Zufallsgraphen mit der gleichen Anzahl Knoten und Verbindungen.