Graaddistributie

Graaddistributie is een term uit de grafentheorie en netwerktheorie die de kansverdeling beschrijft van de graad van knopen in een graf. De graad van een knoop is het aantal randen dat ermee is verbonden (bij een gerichte graaf spreken we van in- en out-degree).

P(k) = Prob[knopen heeft graad k]. In een netwerk met N knopen en E randen wordt dit vaak geschat door een histogram of door de cumulatieve verdeling. De graaddistributie bepaalt in welke mate knopen met veel connecties voorkomen.

Veel onderzochte modellen: het Erdős–Rényi model G(n,p) levert een binomiale verdeling die voor grote n en kleine p (met np constant) afloopt naar een Poisson-verdeling. Veel natuurlijke netwerken vertonen daarentegen een lange staart en volgen een machtverdeling P(k) ~ k^(-γ) met vaak γ tussen ~2 en ~3. Dergelijke schaalvrije netwerken bevatten hub-knopen met hoge graad en hebben bijzondere robuustheidskenmerken.

Bij het analyseren wordt vaak gekeken naar de verwachting E[k] = Σ k P(k) en de variantie, evenals hogere momenten. Empirisch kan de verdeling worden weergegeven als een histogram of via de complementaire cumulatieve verdeling.

Toepassingen en relevantie: de graaddistributie beïnvloedt factoren zoals percolatie, diffusie en de veerkracht tegen storingen op netwerken. Netwerken met zware staarten vertonen vaak grotere kwetsbaarheid voor gerichte aanvallen op de hoog-graade knopen.

Dit is een beknopte beschrijving van graaddistributie en zijn rol bij het karakteriseren van netwerken.