Kerngetal

Kerngetal is een begrip uit de graaftheorie en netwerkwetenschap. Het verwijst naar de kerngetallen van knopen in een ongerichte graaf en wordt gebruikt om de lokale en globale structuur van netwerken te beschrijven. Voor een graaf G=(V,E) is het kerngetal van een knoop v de grootste waarde k waarvoor v behoort tot de k-kern van G.

Een k-kern is een maximale subgraaf waarin elke knoop ten minste k buren heeft binnen die subgraaf. De k-kernen vormen een hiërarchie in de graaf, vaak gezien als de k-shells: elke knoop heeft een kerngetal gelijk aan de hoogste k waarin hij voorkomt. Het globale kerngetal van de graaf is het grootste k waarvoor een k-kern bestaat; dit komt overeen met de degeneracy van de graaf.

Eigenschappen van kerngetallen omvatten dat ze niet-negatief zijn en liggen tussen 0 en de maximale graad Δ van de graaf. Kerngetallen geven een maat voor de lokale connectiviteit: hoger kernaalduidt op deelname aan dichter verbonden delen van de graaf. De kerndecompositie biedt een gescheiden, maar samenhangende indeling van de knopen in shells waar elke knoop precies één kerngetal heeft.

Berekening gebeurt via een peeling-algoritme dat de knopen in oplopende volgorde van graad verwijdert en de graden van hun buren bijwerkt. Met een bucket-queue kan deze core-decomposition in O(n+m) tijd worden uitgevoerd, waarbij n het aantal knopen en m het aantal randen is.

Toepassingen van kerngetallen zijn onder meer het identificeren van invloedrijke knopen, analysen van robuustheid en kwetsbaarheden van netwerken, en het ontdekken van densere subgraaf-structuren in sociale, biologische of communicatienetwerken. Zie ook k-core, core-decompositie, k-shell en degeneracy.