Klyngekoefficienten

Klyngekoefficienten, også kendt som clustering coefficient eller lokal klyngekoefficient, er et mål i grafteori, der beskriver graden af klyngedannelse i en graf. For en given node i en graf måler klyngekoefficienten, hvor tæt forbundne dens naboer er indbyrdes. Med andre ord angiver den, hvor stor en del af mulige forbindelser mellem en nodes naboer, der rent faktisk eksisterer.

Formlen for klyngekoefficienten C_i for en node i er defineret som forholdet mellem antallet af kanter mellem naboerne til i, og det maksimale mulige antal kanter mellem disse naboer. Hvis en node i har k_i naboer, er det maksimale antal mulige kanter mellem disse naboer lig med k_i * (k_i - 1) / 2. Klyngekoefficienten C_i er således givet ved: C_i = (antal kanter mellem naboerne til i) / (k_i * (k_i - 1) / 2).

Værdien af klyngekoefficienten ligger mellem 0 og 1. En klyngekoefficient på 1 betyder, at alle naboerne til noden er forbundet indbyrdes, hvilket danner en komplet subgraf. En klyngekoefficient på 0 indikerer, at ingen af nodens naboer er forbundet indbyrdes.

Ud over den lokale klyngekoefficient for individuelle noder kan man også beregne en global klyngekoefficient for hele grafen. Dette kan gøres ved at tage gennemsnittet af de lokale klyngekoefficienter for alle noder i grafen. Klyngekoefficienten anvendes inden for forskellige felter, herunder analyse af sociale netværk, biologiske netværk og informationsteknologi til at forstå strukturen og organisationen af komplekse systemer. Høj klyngekoefficient antyder tendensen til at danne tætte grupper eller klynger.