clusteringcoëfficiënt

De clusteringcoëfficiënt, vaak aangeduid als clustering coefficient, is een maatstaf uit de netwerkwetenschap en grafentheorie die aangeeft in welke mate de buurknopen van een knoop onderling met elkaar verbonden zijn. De waarde ligt tussen 0 en 1: 0 betekent dat de buurnoden geen onderlinge verbindingen hebben en 1 betekent dat alle buurnoden met elkaar verbonden zijn, waardoor een volledig subnetwerk ontstaat. De clusteringcoëfficiënt wordt gebruikt om de localisatie van verbindingen en de aanwezigheid van kleine, dichtgeknoopte groepen in een netwerk te beoordelen.

Er zijn twee veelvoorkomende vormen van de clusteringcoëfficiënt. De lokale clusteringcoëfficiënt C_i van een knoop i met graad k_i (k_i ≥ 2) is gedefinieerd als C_i = 2e_i / (k_i (k_i − 1)), waarbij e_i het aantal verbindingen tussen de buren van i aangeeft. Dit getal geeft aan hoe goed de buren van node i onderling verbonden zijn. De globale of transitivity clusteringcoëfficiënt geeft een netwerkrichtlijn van hoe vaak connecties voorkomen in het hele netwerk en wordt vaak gedefinieerd als C = (3 × aantal driehoeken) / (aantal verbonden triplets van knopen). In veel teksten geldt ook de verhouding van het werkelijke aantal driehoeken ten opzichte van het mogelijke aantal driehoeken in het netwerk.

Bij gewogen netwerken bestaan er gewogen varianten van de clusteringcoëfficiënt die rekening houden met de sterkte of lengtes van randen. Deze gewogen versies proberen de bijdrage van zwaardere of belangrijkere verbindingen mee te nemen in de maatvoering van clustering. Voor ongerichte, eenvoudige grafen geldt dat hogere waarden wijzen op sterkere lokaal gegroepeerde groepen; lagere waarden suggereren minder onderlinge verbindingen tussen buren.

Toepassingen van de clusteringcoëfficiënt komen veel voor in sociale netwerken, biologische netwerken en technologische netwerken. Ze helpen bij het karakteriseren van de structuur (bijv. small-world eigenschappen), het vergelijken van netwerken en het begrijpen van dynamische processen zoals informatie- of ziekteverspreiding.

Zie ook basisbegrippen in de netwerkwetenschap, transitivity, lokale en globale clusteringcoëfficiënt, en gewogen clusteringcoëfficiënt.