Structure and estimation of network models with overlapping communities

Thumbnail Image
Files
isbn9789526406275.pdf (343.49 KB)
Journal Title
Journal ISSN
Volume Title
School of Science | Doctoral thesis (article-based) | Defence date: 2021-12-17
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2021
Department
Matematiikan ja systeemianalyysin laitos
Department of Mathematics and Systems Analysis
Major/Subject
Mcode
Degree programme
Language
en
Pages
55 + app. 125
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 175/2021
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.
Description
Supervising professor
Leskelä, Lasse, Assoc. Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
Keywords
networks, random graphs, parameter estimation, asymptotic theory, overlapping communities, verkostot, satunnaisverkot, parametrien estimointi, asymptoottinen teoria, päällekkäiset yhteisöt
Other note
Parts
  • [Publication 1]: J. Karjalainen and L. Leskelä. Moment-based parameter estimation in binomial random intersection graph models. In Algorithms and Models for the Web Graph (WAW 2017), Lecture Notes in Computer Science, volume 10519, Toronto, Canada, pp. 1–15, June 2017.
    DOI: 10.1007/978-3-319-67810-8_1 View at publisher
  • [Publication 2]: J. Karjalainen, J.S.H. van Leeuwaarden, and L. Leskelä. Parameter estimators of sparse random intersection graphs with thinned communities. In Algorithms and Models for the Web Graph (WAW 2018), Lecture Notes in Computer Science, volume 10836, Moscow, Russia, pp. 44–58, May 2018.
    DOI: 10.1007/978-3-319-92871-5_4 View at publisher
  • [Publication 3]: T. Gröhn, J. Karjalainen, and L. Leskelä. Clique and cycle frequencies in a sparse random graph model with overlapping communities. Submitted to a journal, arXiv:1911.12827, 23 pages, April 2021
  • [Publication 4]: Bloznelis, J. Karjalainen, and L. Leskelä. Assortativity and bidegree distributions on Bernoulli random graph superpositions. Accepted for publication in Probability in the Engineering and Informational Sciences, 31 pages, August 2021.
    DOI: 10.1017/S0269964821000310 View at publisher
  • [Publication 5]: J. Karjalainen. A note on parameter estimation of thinned random intersection graphs. In 22nd European Young Statisticians Meeting, Athens, Greece, pp. 51–55, September 2021
  • [Publication 6]: M. Bloznelis, J. Karjalainen, and L. Leskelä. Normal and stable approximation to subgraph counts in superpositions of Bernoulli random graphs. Submitted to a journal, arXiv:2107.02683, 15 pages, July 2021
Citation
Permanent link to this item
https://urn.fi/URN:ISBN:978-952-64-0627-5
Collections
[diss] Perustieteiden korkeakoulu / SCI