Stokastisk blokkmodell - Stochastic block model

Den stokastiske blokkmodellen er en generativ modell for tilfeldige grafer . Denne modellen har en tendens til å produsere grafer som inneholder lokalsamfunn , undersett av noder preget av å være forbundet med hverandre med spesielle kanttettheter. For eksempel kan kanter være mer vanlige i lokalsamfunn enn mellom lokalsamfunn. Den matematiske formuleringen ble først introdusert i 1983 innen det sosiale nettverket av Holland et al. Den stokastiske blokkeringsmodellen er viktig innen statistikk , maskinlæring og nettverksvitenskap , der den fungerer som en nyttig målestokk for oppgaven med å gjenopprette samfunnsstruktur i grafdata.

Definisjon

Den stokastiske blokkmodellen tar følgende parametere:

Antall hjørner; ${\ displaystyle n}$
en partisjon av toppunktet som er satt inn i usammenhengende undergrupper , kalt fellesskap ; ${\ displaystyle \ {1, \ ldots, n \}}$ ${\ displaystyle C_ {1}, \ ldots, C_ {r}}$
en symmetrisk matrise med kant -sannsynligheter. ${\ displaystyle r \ ganger r}$ ${\ displaystyle P}$

Kantsettet samles deretter tilfeldig som følger: to hjørner og er forbundet med en kant med sannsynlighet . Et eksempel på problem er: gitt en graf med hjørner, hvor kantene er samplet som beskrevet, gjenopprett gruppene . ${\ displaystyle u \ i C_ {i}}$ ${\ displaystyle v \ i C_ {j}}$ ${\ displaystyle P_ {ij}}$ ${\ displaystyle n}$ ${\ displaystyle C_ {1}, \ ldots, C_ {r}}$

Spesielle tilfeller

Et eksempel på assortativ sak for den stokastiske blokkmodellen.

Hvis sannsynlighetsmatrisen er en konstant, i den forstand at for alle , så er resultatet Erdős - Rényi -modellen . Denne saken er degenerert - inndelingen i lokalsamfunn blir irrelevant - men den illustrerer et nært forhold til Erdős - Rényi -modellen. ${\ displaystyle P_ {ij} = p}$ ${\ displaystyle i, j}$ ${\ displaystyle G (n, p)}$

Den plantede partisjonsmodellen er det spesielle tilfellet at verdiene til sannsynlighetsmatrisen er en konstant på diagonalen og en annen konstant utenfor diagonalet. Dermed deler to hjørner i samme fellesskap en kant med sannsynlighet , mens to hjørner i forskjellige samfunn deler en kant med sannsynlighet . Noen ganger er det denne begrensede modellen som kalles den stokastiske blokkmodellen. Saken der kalles en assortativ modell, mens saken kalles disassortativ . ${\ displaystyle P}$ ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle p> q}$ ${\ displaystyle p <q}$

Tilbake til den generelle stokastiske blokkmodellen, kalles en modell sterkt assortativ hvis når : alle diagonale oppføringer dominerer alle off-diagonale oppføringer. En modell kalles svakt assortative om når : hver diagonal oppføring er bare nødvendig å dominere resten av sin egen rad og kolonne. Disassortative former for denne terminologien eksisterer ved å reversere alle ulikheter. Algoritmisk gjenoppretting er ofte lettere mot blokkmodeller med assortative eller disassortative tilstander i denne formen. ${\ displaystyle P_ {ii}> P_ {jk}}$ ${\ displaystyle j \ neq k}$ ${\ displaystyle P_ {ii}> P_ {ij}}$ ${\ displaystyle i \ neq j}$

Typiske statistiske oppgaver

Mye av litteraturen om algoritmisk fellesskapsdeteksjon tar for seg tre statistiske oppgaver: deteksjon, delvis gjenoppretting og eksakt gjenoppretting.

Gjenkjenning

Målet med deteksjonsalgoritmer er ganske enkelt å bestemme om grafen har latent samfunnsstruktur, gitt en samplet graf. Nærmere bestemt kan en graf, med noen kjent tidligere sannsynlighet, genereres fra en kjent stokastisk blokkmodell, og ellers fra en lignende Erdos-Renyi-modell . Den algoritmiske oppgaven er å korrekt identifisere hvilken av disse to underliggende modellene som genererte grafen.

Delvis utvinning

Ved delvis gjenoppretting er målet å omtrent bestemme den latente partisjonen i lokalsamfunn, i den forstand å finne en partisjon som er korrelert med den sanne partisjonen, betydelig bedre enn en tilfeldig gjetning.

Nøyaktig restitusjon

I nøyaktig gjenoppretting er målet å gjenopprette den latente partisjonen i lokalsamfunn nøyaktig. Samfunnets størrelser og sannsynlighetsmatrise kan være kjent eller ukjent.

Statistiske nedre grenser og terskelatferd

Stokastiske blokkmodeller viser en skarp terskeleffekt som minner om perkolasjonsterskler . Anta at vi lar størrelsen på grafen vokse, og beholder fellesskapsstørrelsene i faste proporsjoner. Hvis sannsynlighetsmatrisen forblir fast, blir oppgaver som delvis og nøyaktig gjenoppretting mulig for alle ikke-degenererte parameterinnstillinger. Imidlertid, hvis vi skalerer ned sannsynlighetsmatrisen med en passende hastighet som økninger, observerer vi en skarp faseovergang: for visse innstillinger av parametrene vil det bli mulig å oppnå gjenoppretting med sannsynlighet til 1, mens på motsatt side av parameterterskel, har sannsynligheten for gjenoppretting en tendens til 0 uansett hvilken algoritme som brukes. ${\ displaystyle n}$ ${\ displaystyle n}$

For delvis gjenoppretting er passende skalering å ta for fast , noe som resulterer i grafer med konstant gjennomsnittlig grad. I tilfelle av to like store lokalsamfunn, i den assortative plantede partisjonsmodellen med sannsynlighetsmatrise ${\ displaystyle P_ {ij} = {\ tilde {P}} _ {ij}/n}$ ${\ displaystyle {\ tilde {P}}}$

{\ displaystyle P = \ left ({\ begin {array} {cc} {\ tilde {p}}/n & {\ tilde {q}}/n \\ {\ tilde {q}}/n & {\ tilde { p}}/n \ end {array}} \ right),}

delvis gjenoppretting er mulig med sannsynlighet når som helst , mens enhver estimator mislykkes delvis gjenoppretting med sannsynlighet når som helst .

{\ displaystyle 1-o (1)}

{\ displaystyle ({\ tilde {p}}-{\ tilde {q}})^{2}> 2 ({\ tilde {p}}+{\ tilde {q}})}

{\ displaystyle 1-o (1)}

{\ displaystyle ({\ tilde {p}}-{\ tilde {q}})^{2} <2 ({\ tilde {p}}+{\ tilde {q}})}

For nøyaktig gjenoppretting er det hensiktsmessig skalering å ta , noe som resulterer i grafer av logaritmisk gjennomsnittsgrad. Her eksisterer en lignende terskel: for den assortative plantede partisjonsmodellen med like store samfunn ligger terskelen på . Faktisk er den eksakte utvinningsterskelen kjent for den helt generelle stokastiske blokkmodellen. ${\ displaystyle P_ {ij} = {\ tilde {P}} _ {ij} \ logg n/n}$ ${\ displaystyle r}$ ${\ displaystyle {\ sqrt {\ tilde {p}}}-{\ sqrt {\ tilde {q}}} = {\ sqrt {r}}}$

Algoritmer

I prinsippet kan eksakt utvinning løses i sitt gjennomførbare område med maksimal sannsynlighet , men dette betyr å løse et begrenset eller regulert kuttproblem, for eksempel minimum biseksjon som vanligvis er NP-komplett . Derfor vil ingen kjente effektive algoritmer beregne maksimal sannsynlighetsestimatet i verste fall.

Imidlertid fungerer et bredt utvalg av algoritmer godt i gjennomsnittet, og det er bevist mange høy sannsynlighetsytelser for algoritmer i både delvise og eksakte gjenopprettingsinnstillinger. Vellykkede algoritmer inkluderer spektralgruppering av hjørnene, semidefinitt programmering , former for trosformidling og oppdagelse av fellesskap blant andre.

Varianter

Det finnes flere varianter av modellen. En mindre tweak tildeler hjørner til grupper tilfeldig, i henhold til en kategorisk fordeling , i stedet for i en fast partisjon. Mer signifikante varianter inkluderer den gradskorrigerte stokastiske blokkmodellen, den hierarkiske stokastiske blokkmodellen, den geometriske blokkmodellen, sensurert blokkmodell og blokkeringsmodellen for blandet medlemskap.

Emnemodeller

Stokastisk blokkmodell har blitt anerkjent som en temamodell på topartsnettverk. I et nettverk av dokumenter og ord kan den stokastiske blokkmodellen identifisere emner: en gruppe ord med en lignende betydning.

Se også

blokkmodellering
Girvan - Newman -algoritme - Algoritme for gjenkjenning av fellesskap
Lancichinetti – Fortunato – Radicchi benchmark - Algoritme for å generere benchmark -nettverk med lokalsamfunn

Languages

In other projects