Kroneckergraphmodellen

Kroneckergraphmodellen är en statistisk modell för att generera och beskriva stora nätverk genom användning av Kroneckerprodukten. Modellen bygger på att en liten initiatormatris används upprepade gånger för att skapa ett mycket större adjacens- eller sannolikhetsmått, vilket ger självliknande struktur över olika skalor.

Konstructionen börjar med en initiatormatris P av storlek b×b där varje element mellan 0 och 1 representerar sannolikheten för en kant mellan två underliggande noder. För k repetitioner bildas P⊗k, den k:e Kroneckerprodukten av P. Antalet noder blir n = b^k. Varje potentiell kant mellan två noder i den färdiga grafen tilldelas en Bernoulli-sannolikhet given av motsvarande entry i P⊗k; kanterna antas oftast oberoende. Modellen kan användas för riktade grafer (anpassas till oriktade versioner genom symmetrisering av initiatorn) eller för nätverk med olika kanttyper.

Egenskaper som ofta eftersträvas hos Kroneckergrafmodellen inkluderar självliknande eller hierarkisk struktur, möjlighet till tungt svansiga gradfördelningar, och relativt små världsliknande diametrar tillsammans med övergripande clustering. Genom val av initiatorn kan graden och andra topologiska egenskaper manipuleras, vilket gör modellen lämplig för att generera realistiska syntetiska nätverk för forskning och benchmarking.

Estimering och användning: modellen används bland annat för att generera stora, realistiska nätverk samt för studier av dynamiska processer på nätverk. Parameteruppskattning är ofta komplex och kräver effektiva approximationer eller metod-moment-/sannolikhetsbaserade metoder, eftersom exakt sannolikhetsberäkning kan vara beräkningsmässigt intensiv.

Historik: Kroneckergrafmodellen introducerades i början av 2010-talet som ett sätt att modellera och förstå nätverks topologi genom upprepning av en liten grundmatris.