Lancichinetti – Fortunato – Radicchi målestokk - Lancichinetti–Fortunato–Radicchi benchmark

Nettverksvitenskap
Teori
Kurve Kompleks nettverk Smitte Liten verden Scale-fri Fellesskapets struktur percolation Utvikling kontrollerbarhet Grafittegning Sosial kapital Koblingsanalyse optimalisering Gjensidighet nedleggelse Homophily Transitivitet Foretrukket vedlegg Balanse teori Nettverkseffekt Sosial innflytelse
Nettverkstyper
Informasjon (databehandling) telekommunikasjon Transportere Sosial Vitenskapelig samarbeid biologisk Kunstig nevralt gjensidig avhengige av hverandre semantisk Romlig avhengighet Strømme on-Chip
grafer
Funksjoner Klikk Komponent Kutte opp Syklus Data struktur Kant Løkke Nabolag Sti Vertex Adjacency list  / matrix Insidensliste  / matrise typer bipartite Fullstendig Regissert Hyper multi Tilfeldig vektet
metrics algoritmer
sentralitet Grad Betweenness Nærhet Side rangering Motif Gruppering Grad fordeling Assortativity Avstand modularitet Effektivitet
modeller
topologi Tilfeldig graf Erdős-Rényi Barabási-Albert Treningsmodell Watts-Strogatz Eksponentiell tilfeldig (ERGM) Tilfeldig geometrisk (RGG) Hyperbolic (HGN) Hierarkisk Stokastisk blokk Maksimal entropi Myk konfigurasjon LFR Benchmark Dynamics Boolskt nettverk agentbasert Epidemi / SIR
lister kategorier
emner programvare Nettverksforskere Kategori: Nettverksteori Kategori: Grafteori
v t e

Lancichinetti – Fortunato – Radicchi (LFR) målestokk er en algoritme som genererer referansenettverk (kunstige nettverk som ligner virkelige nettverk). De har i forkant kjente samfunn og brukes til å sammenligne forskjellige metoder for deteksjon av samfunn. Fordelen med LFR fremfor andre metoder, er at den gjør rede for heterogeniteten i fordelingen av node grader og i fellesskap størrelser.

Algoritmen

Knutepunktgradene og samfunnsstørrelsene er fordelt i henhold til en strømlov , med forskjellige eksponenter. LFR antar at både grad og samfunnsstørrelse har strømlovutdelinger med forskjellige eksponenter, og hhv. er antall noder og gjennomsnittlig grad er . Det er en mikseparameter , som er den gjennomsnittlige brøkdel av naboknuter til en node som ikke tilhører noe fellesskap som referansepunktnoden tilhører. Denne parameteren kontrollerer brøkdelen av kanter som er mellom lokalsamfunn. Dermed gjenspeiler det mengden støy i nettverket. På ytterpunktene, når alle koblinger er innenfor felleskoblinger, hvis alle koblinger er mellom noder som tilhører forskjellige samfunn.${\ displaystyle \ gamma}$${\ displaystyle \ beta}$${\ displaystyle N}$${\ displaystyle \ langle k \ rangle}$${\ displaystyle \ mu}$${\ displaystyle \ mu = 0}$${\ displaystyle \ mu = 1}$

Man kan generere et LFR-referansenettverk i følgende trinn.

Trinn 1: Generer et nettverk med noder etter en strømlovdistribusjon med eksponentog velg ytterpunktene for distribusjonenog forå få ønsket gjennomsnittsgrad er. ${\ displaystyle \ gamma}$${\ displaystyle k _ {\ min}}$${\ displaystyle k _ {\ max}}$${\ displaystyle \ langle k \ rangle}$

Trinn 2: brøkdel av lenker for hver node er med noder i samme fellesskap, mens brøkdeler med de andre nodene. ${\ displaystyle (1- \ mu)}$${\ displaystyle \ mu}$

Trinn 3: Generer samfunnsstørrelser fra en strømlovdistribusjon med eksponent. Summen av alle størrelser må være lik. De minimale og maksimale samfunnsstørrelseneogmå tilfredsstille definisjonen av fellesskap, slik at hver ikke-isolerte node er i minst ett samfunn: ${\ displaystyle \ beta}$${\ displaystyle N}$${\ displaystyle s _ {\ min}}$${\ displaystyle s _ {\ max}}$

${\ displaystyle s _ {\ min}> k _ {\ min}}$

${\ displaystyle s _ {\ max}> k _ {\ max}}$

Trinn 4: Til å begynne med tildeles ingen noder til lokalsamfunn. Deretter blir hver node tilfeldig tildelt et fellesskap. Så lenge antallet nabolagene i samfunnet ikke overskrider samfunnets størrelse, legges en ny node til fellesskapet, forblir ellers ute. I de følgende iterasjoner blir den "hjemløse" noden tilfeldig tildelt til et fellesskap. Hvis det fellesskapet er komplett, dvs. størrelsen er utmattet, må en tilfeldig valgt node i det fellesskapet fjernes. Stopp iterasjonen når alle lokalsamfunnene er komplette og alle nodene tilhører minst ett samfunn.

Trinn 5: Implementere kabling av noder som holder de samme nodegradene, men bare påvirker brøkdelen av interne og eksterne lenker slik at antall lenker utenfor fellesskapet for hver node er tilnærmet lik mikseparameteren.${\ displaystyle \ mu}$

testing

Vurder en partisjon i lokalsamfunn som ikke overlapper hverandre. Samfunnene for tilfeldig valgte noder i hver iterasjon følger en fordeling som representerer sannsynligheten for at en tilfeldig valgt node er fra fellesskapet . Tenk på en partisjon av det samme nettverket som ble forespeilet av en lokal funnalgoritme og har distribusjon. Referansepartisjonen har distribusjon. Felledelingen er . Likheten mellom disse to partisjonene fanges opp av normalisert gjensidig informasjon . ${\ displaystyle p (C)}$${\ displaystyle C}$${\ displaystyle p (C_ {2})}$${\ displaystyle p (C_ {1})}$${\ displaystyle p (C_ {1}, C_ {2})}$

${\ displaystyle I_ {n} = {\ frac {\ sum _ {C_ {1}, C_ {2}} p (C_ {1}, C_ {2}) \ log _ {2} {\ frac {p ( C_ {1}, C_ {2})} {p (C_ {1}) p (C_ {2})}} {{\ frac {1} {2}} H (\ {p (C_ {1} ) \}) + {\ frac {1} {2}} H (\ {p (C_ {2}) \})}}}$

Hvis referanseporteføljen og de oppdagede partisjonene er identiske, og hvis de er uavhengige av hverandre.${\ displaystyle I_ {n} = 1}$${\ displaystyle I_ {n} = 0}$

referanser