Consistent Bayesian community detection

Abstract

Revealing underlying relations between the nodes in the network is one of the most important tasks in network analysis. This can be achieved by partitioning the network into sets of nodes which are, in some sense, more similar to each other than to the other nodes. Using tools and techniques from a variety of disciplines, many community detection methods have been developed for many different scenarios. This thesis examines the statistical properties of community detection algorithms with a focus on Bayesian procedures. We review key definitions and theoretical results related to large sample behavior of the posterior distribution. In particular, we focus on how these results are applied in the context of Bayesian stochastic block models.

The thesis proposes a dynamic community detection algorithm based on Gibbs sampling, which takes multiple independent and identically distributed network snapshots as an input. To understand the limiting behavior of the sampler, we derive two posterior concentration inequalities that imply posterior (almost) exact recovery of the community structure and a posterior contraction rate that improves as the number of snapshots increases. Moreover, we derive bounds for sufficient separation between within- and between-community connectivity parameters to achieve exact and almost exact community recovery. These conditions are comparable to a well known threshold for community detection in the stochastic block model with two equal communities.

We perform numerical experiments to assess how increasing the number of snapshots affects the classification accuracy of the sampler. The results show that the improved contraction rate and the decreased threshold for community recovery translate to improved accuracy in small to moderate network sizes.

Toimijoiden välisten piilevien vuorovaikutussuhteiden selvittäminen on verkostoanalyysin keskeisimpiä ongelmia. Tämä voidaan saavuttaa jakamalla toimijat joukkoihin, joiden jäsenillä on tietyssä mielessä enemmän yhteistä keskenään kuin muiden toimijoiden kanssa. Hyödyntäen työkaluja ja tekniikoita useilta eri tieteenaloilta, on tätä varten kehitetty laaja joukko erilaisia yhteisötunnistusmenetelmiä eri käyttötapauksia silmällä pitäen. Tässä opinnäytetyössä tarkastellaan yhteisötunnistusalgoritmien tilastollisia ominaisuuksia keskittyen erityisesti bayesilaisiin menetelmiin. Opinnäytetyö tekee katsauksen keskeisiin määritelmiin ja tuloksiin, joilla pyritään kuvaamaan posteriorijakauman käyttäytymistä otoskoon kasvaessa. Työssä keskitytään erityisesti siihen, kuinka näitä tuloksia on sovellettu bayesilaisten stokastisten lohkomallien tarkasteluun.

Työ esittelee Gibbsin otanta-algoritmiin perustuvan dynaamisen yhteisötunnistusalgoritmin, joka käyttää syötteenään useita riippumattomia ja samoin jakautuneita verkkoja. Algoritmin asymptoottisia ominaisuuksia tarkastellaan johtamalla kaksi posteriorin suppenemista kuvaavaa epäyhtälöä. Näistä seuraa, että algoritmi palauttaa piilevän yhteisörakenteen (melkein) tarkasti verkosta tehtyjen havaintojen lukumäärän kasvaessa. Tällöin myös suppenemisnopeus kasvaa. Lisäksi näytetään, että yhteisörakenteen (melkein) tarkka tunnistus onnistuu, kun yhteisöjen sisäisen ja välisen vuorovaikutustodennäköisyyden eroavuus ylittää esitetyn alarajan. Johdetut ehdot muistuttavat kuuluisaa kahden samankokoisen yhteisön stokastisen lohkomallin kynnysarvoa.

Kun tarkastellaan pieniä ja keskisuuria verkkoja, numeeristen kokeiden tulokset viittaavat siihen, että havaintojen lukumäärän kasvaessa kasvava suppenemisnopeus ja pienenevä kynnysarvo johtavat luokittelutarkkuuden parantumiseen.