Communities in a large social network: visualization and analysis

Abstract

Communities have been a hot topic in complex network research the last years. Several algorithms for detecting communities have been developed, and in this thesis we use the sequential clique percolation algorithm to detect communities in a large social network. Our network consists of 5.3 million mobile phone users, with mutual communication data aggregated over 18 weeks.

In this thesis we do a visual study of the communities, and we clearly see the nested community structure when we do clique percolation for dierent clique sizes. When we threshold the edge weights we see that the strongest edges are in the densest subcommunities and that the weakest edges keep the communities connected.

We also present numerical analysis of some selected structure and topology properties of the communities. Lastly we confirm, by numerical analysis of the available demographic data on the mobile phone users, that the communities are more conform with respect to zip code, age and sex compared to a reference network where the demographic attributes have been shuffled.

Samfunn har vært et hett emne innen forskning på komplekse nettverk de siste årene. Det har blitt utviklet flere algoritmer for å finne samfunn, og i denne oppgaven bruker vi sekvensiell klikkperkolasjon til å finne samfunn i et stort sosialt nettverk. Nettverket vårt består av 5.3 millioner mobiltelefonbrukere, med gjensidig kommunikasjonsdata aggregert over 18 uker.

I denne oppgaven gjør vi en visuell studie av samfunnene, og vi ser tydelig den vevde sammfunnsstrukturen når vi utfører klikkperkolasjon for ulike klikkstørrelser. Når vi setter terskler for lenkevektene ser vi at de sterkeste lenkene er i de tetteste undersamfunnene og at de svakeste lenkene holder samfunnene i kontakt med hverandre.

Vi presenterer også en numerisk analyse av noen utvalgte struktur- og topologiegenskaper hos samfunnene. Til slutt bekrefter vi, via numerisk analyse av den tilgjengelige demografiske informasjonen om mobiltelefonbrukerne, at samfunnene er mer konforme med tanke på postkode, alder og kjønn sammenlignet med et referansenettverk hvor de demografiske attributtene har blitt stokket om.