Structure and estimation of network models with overlapping communities

Abstract

Many types of data in different fields of science can be naturally represented as networks. Social relationships in groups of people, the structure of the internet, and traffic networks can all be understood as collections of nodes and connections between them. Real-world networks often show signs of community structure, i.e., some groups of nodes are more densely connected to each other than to the rest of the nodes. Since communities may emerge through many different mechanisms, it is natural to describe these networks with statistical models where the communities are allowed to overlap. Even in the absence of obvious communities, various other types of structure are commonly observed in data. For example, the degrees of adjacent nodes tend to be correlated, and node pairs have an increased probability of being adjacent if they have common neighbors. This dissertation is concerned with the structure of large and sparse statistical network models with overlapping communities. This structure is described using statistical quantities and distributions and their limits as the number of nodes tends to infinity. The focus is on the asymptotic behavior of subgraph frequencies, joint degree distributions of adjacent nodes, and various summary statistics. New results are proved on their convergence, and exact formulas are provided for their limits. These results lead to new estimators of the model parameters based on counting the frequencies of small subgraphs. The consistency of these estimators is proved under complete or partly incomplete data. The results show that the models have structural similarities with many real-world networks, such as non-trivial clustering, degree correlations, and power laws. This illustrates how some empirical observations on network data can be explained with an underlying overlapping community structure.

Monia eri tieteenaloilla esiintyviä aineistoja voidaan luontevasti esittää verkostoina. Esimerkiksi ihmisten välisiä sosiaalisia suhteita, Internetin rakennetta ja liikenneverkostoja voidaan esittää kokoelmina solmuja ja niiden välisiä kytköksiä. Tosimaailman verkostoissa havaitaan usein yhteisörakennetta, eli solmut muodostavat ryhmiä, jotka ovat sisäisesti tiiviisti kytkeytyneitä, mutta kytkökset ryhmän ulkopuolisiin solmuihin ovat vähäisiä. Koska yhteisörakenne voi syntyä useiden eri mekanismien kautta, on luontevaa että verkostoa kuvaava tilastollinen malli sallii yhteisöjen päällekkäisyyden. Vaikka aineistossa ei esiintyisi selkeitä yhteisöjä, usein voidaan havaita muunlaista rakenteellisuutta. Esimerkiksi kytkettyjen solmujen asteet korreloivat, ja solmuparit ovat todennäköisemmin kytkettyjä, jos niillä on yhteisiä naapureita. Tässä väitöskirjassa tutkitaan suurten ja harvojen päällekkäisiä yhteisöjä sisältävien tilastollisten verkostomallien rakennetta. Tätä rakennetta kuvataan tilastollisilla suureilla ja jakaumilla sekä näiden raja-arvoilla solmujen määrän kasvaessa kohti ääretöntä. Työssä analysoidaan pienten osaverkkojen lukumäärien, kytkettyjen solmujen asteiden yhteisjakaumien ja erilaisten tilastollisten tunnuslukujen asymptoottista käyttäytymistä. Näille todistetaan suppenemistuloksia ja niiden raja-arvoille annetaan täsmällisiä kaavoja. Tulosten perusteella johdetaan pienten osaverkkojen laskentaan perustuvia estimaattoreita mallien parametreille, ja niiden tarkentuvuus todistetaan täysin ja osittain havaituille aineistoille. Tulokset osoittavat, että malleilla on rakenteellisia yhtäläisyyksiä monien tosimaailman verkostojen kanssa, kuten epätriviaaleja klusterointiominaisuuksia, asteiden korrelaatioita ja potenssilakeja.Tämä havainnollistaa sitä, kuinka eräitä verkostoaineistoista tehtyjä havaintoja voidaan selittää piilevien ja päällekkäisten yhteisöjen rakenteen avulla.