Lancichinetti–Fortunato–Radicchi riktmärke
Del av serie om | ||||
nätverksvetenskapsteori | ||||
---|---|---|---|---|
Nätverkstyper | ||||
Grafer | ||||
|
||||
Modeller | ||||
|
||||
| ||||
Lancichinetti–Fortunato–Radicchi benchmark är en algoritm som genererar benchmarknätverk (konstgjorda nätverk som liknar verkliga nätverk). De har a priori kända gemenskaper och används för att jämföra olika gemenskapsdetekteringsmetoder. Fördelen med riktmärket framför andra metoder är att det tar hänsyn till heterogeniteten i fördelningarna av nodgrader och gemenskapsstorlekar.
Algoritmen
Nodgraderna och gemenskapsstorlekarna är fördelade enligt en maktlag , med olika exponenter. Riktmärket antar att både graden och gemenskapsstorleken har maktlagsfördelningar med olika exponenter, respektive . är antalet noder och medelgraden är . Det finns en blandningsparameter , som är den genomsnittliga andelen av angränsande noder till en nod som inte tillhör någon gemenskap som benchmarknoden tillhör. Den här parametern styr andelen kanter som finns mellan grupper. Således återspeglar det mängden brus i nätverket. I ytterligheterna, när är alla länkar inom community-länkar, om är alla länkar mellan noder som tillhör olika gemenskaper.
Man kan generera benchmark-nätverket med hjälp av följande steg.
Steg 1: Generera ett nätverk med noder efter en potenslagsfördelning med exponent och välj extremer av fördelningen och för att få önskad medelgrad är .
Steg 2: del av länkarna för varje nod är med noder i samma community, medan del är med de andra noderna.
Steg 3: Generera gemenskapsstorlekar från en kraftlagsfördelning med exponent . Summan av alla storlekar måste vara lika med . De minimala och maximala gemenskapsstorlekarna och måste uppfylla definitionen av gemenskap så att varje icke-isolerad nod finns i åtminstone en gemenskap:
Steg 4: Initialt tilldelas inga noder till gemenskaper. Sedan tilldelas varje nod slumpmässigt till en gemenskap. Så länge som antalet angränsande noder inom gemenskapen inte överstiger gemenskapens storlek läggs en ny nod till i gemenskapen, annars stannar den utanför. I följande iterationer tilldelas den "hemlösa" noden slumpmässigt till någon gemenskap. Om den gemenskapen är komplett, dvs. storleken är slut, måste en slumpmässigt vald nod för den gemenskapen kopplas bort. Stoppa iterationen när alla gemenskaper är kompletta och alla noder tillhör minst en gemenskap.
Steg 5: Implementera omkoppling av noder som behåller samma nodgrader men påverkar bara bråkdelen av interna och externa länkar så att antalet länkar utanför gemenskapen för varje nod är ungefär lika med blandningsparametern μ {\displaystyle \ .
Testning
Överväg en uppdelning i gemenskaper som inte överlappar varandra. Gemenskaperna av slumpmässigt valda noder i varje iteration följer en fördelning som representerar sannolikheten att en slumpmässigt utvald nod kommer från gemenskapen . Betrakta en partition av samma nätverk som förutspåddes av någon community-hittningsalgoritm och har distribution. Benchmark-partitionen har distribution. Den gemensamma fördelningen är . Likheten mellan dessa två partitioner fångas av den normaliserade ömsesidiga informationen .
Om är riktmärket och de upptäckta partitionerna identiska, och om är de oberoende av varandra.