Community Detection in Large Social Networks

Abstract

I denne masteroppgaven implementeres og testes to algoritmer for å finne gruppe- struktur i nettverk, nemlig Louvain-metoden og Diffusion and Propagation-metoden. Et nettverks gruppestruktur består av en naturlig inndeling av nettverkets noder i ikke-overlappende sett, der hvert sett består av noder som er tettere koblet til hver- andre, enn til resten av nettverket. De ovennevnte algoritmene er to alternativer blant mange gode iterative teknikker som har sett dagens lys i løpet av de siste 15 årene.Vi presenterer tre endringer til metodene nevnt over. Først introduserer vi en tredje fase i Louvain-metoden, og endrer dens aggregerende natur ved å la metoden bryte opp grupper i tillegg til å slå dem sammen. Videre undersøker vi hva som skjer med den beregnede gruppestrukturen når matrisen som representerer det un- derliggende nettverket gjennomgår en av flere matrisetransformasjoner. Spesifikt er vi interesserte i se på transformasjoner der kantmatrisen til nettverket opphøyes i andre og tredje potens, samt matriseeksponentialet. Til slutt tester vi og sammen- ligner resultatene til metodene på genererte nettverk av ulike slag, samt to store sosiale nettverk med millioner av noder fra den virkelige verden.