Parameter estimators of sparse random intersection graphs with thinned communities

Joona Karjalainen, Johan S.H. van Leeuwaarden, Lasse Leskelä

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

Abstract

This paper studies a statistical network model generated by a large number of randomly sized overlapping communities, where any pair of nodes sharing a community is linked with probability q via the community. In the special case with q= 1 the model reduces to a random intersection graph which is known to generate high levels of transitivity also in the sparse context. The parameter q adds a degree of freedom and leads to a parsimonious and analytically tractable network model with tunable density, transitivity, and degree fluctuations. We prove that the parameters of this model can be consistently estimated in the large and sparse limiting regime using moment estimators based on partially observed densities of links, 2-stars, and triangles.

Original languageEnglish
Title of host publicationAlgorithms and Models for the Web Graphs
Subtitle of host publication15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings
EditorsA. Bonato, P. Pralat, A, Raigorodskii
Place of PublicationDordrecht
PublisherSpringer
Pages44-58
Number of pages15
ISBN (Electronic)978-3-319-92871-5
ISBN (Print)978-3-319-92870-8
DOIs
Publication statusPublished - 1 Jan 2018
Event15th Workshop on Algorithms and Models for the Web Graph, WAW 2018 - Moscow, Russian Federation
Duration: 17 May 201818 May 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10836 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th Workshop on Algorithms and Models for the Web Graph, WAW 2018
CountryRussian Federation
CityMoscow
Period17/05/1818/05/18

Fingerprint

Intersection Graphs
Random Graphs
Transitivity
Estimator
Network Model
Moment Estimator
Statistical Model
Overlapping
Triangle
Star
Sharing
Limiting
Degree of freedom
Fluctuations
Stars
Vertex of a graph
Model
Community

Cite this

Karjalainen, J., van Leeuwaarden, J. S. H., & Leskelä, L. (2018). Parameter estimators of sparse random intersection graphs with thinned communities. In A. Bonato, P. Pralat, & A. Raigorodskii (Eds.), Algorithms and Models for the Web Graphs: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings (pp. 44-58). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10836 LNCS). Dordrecht: Springer. https://doi.org/10.1007/978-3-319-92871-5_4
Karjalainen, Joona ; van Leeuwaarden, Johan S.H. ; Leskelä, Lasse. / Parameter estimators of sparse random intersection graphs with thinned communities. Algorithms and Models for the Web Graphs: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings. editor / A. Bonato ; P. Pralat ; A, Raigorodskii. Dordrecht : Springer, 2018. pp. 44-58 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{42751aa8571b4603a452685b7edd7af0,
title = "Parameter estimators of sparse random intersection graphs with thinned communities",
abstract = "This paper studies a statistical network model generated by a large number of randomly sized overlapping communities, where any pair of nodes sharing a community is linked with probability q via the community. In the special case with q= 1 the model reduces to a random intersection graph which is known to generate high levels of transitivity also in the sparse context. The parameter q adds a degree of freedom and leads to a parsimonious and analytically tractable network model with tunable density, transitivity, and degree fluctuations. We prove that the parameters of this model can be consistently estimated in the large and sparse limiting regime using moment estimators based on partially observed densities of links, 2-stars, and triangles.",
author = "Joona Karjalainen and {van Leeuwaarden}, {Johan S.H.} and Lasse Leskel{\"a}",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/978-3-319-92871-5_4",
language = "English",
isbn = "978-3-319-92870-8",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "44--58",
editor = "A. Bonato and P. Pralat and A, Raigorodskii",
booktitle = "Algorithms and Models for the Web Graphs",
address = "Germany",

}

Karjalainen, J, van Leeuwaarden, JSH & Leskelä, L 2018, Parameter estimators of sparse random intersection graphs with thinned communities. in A Bonato, P Pralat & A Raigorodskii (eds), Algorithms and Models for the Web Graphs: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10836 LNCS, Springer, Dordrecht, pp. 44-58, 15th Workshop on Algorithms and Models for the Web Graph, WAW 2018, Moscow, Russian Federation, 17/05/18. https://doi.org/10.1007/978-3-319-92871-5_4

Parameter estimators of sparse random intersection graphs with thinned communities. / Karjalainen, Joona; van Leeuwaarden, Johan S.H.; Leskelä, Lasse.

Algorithms and Models for the Web Graphs: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings. ed. / A. Bonato; P. Pralat; A, Raigorodskii. Dordrecht : Springer, 2018. p. 44-58 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10836 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Parameter estimators of sparse random intersection graphs with thinned communities

AU - Karjalainen, Joona

AU - van Leeuwaarden, Johan S.H.

AU - Leskelä, Lasse

PY - 2018/1/1

Y1 - 2018/1/1

N2 - This paper studies a statistical network model generated by a large number of randomly sized overlapping communities, where any pair of nodes sharing a community is linked with probability q via the community. In the special case with q= 1 the model reduces to a random intersection graph which is known to generate high levels of transitivity also in the sparse context. The parameter q adds a degree of freedom and leads to a parsimonious and analytically tractable network model with tunable density, transitivity, and degree fluctuations. We prove that the parameters of this model can be consistently estimated in the large and sparse limiting regime using moment estimators based on partially observed densities of links, 2-stars, and triangles.

AB - This paper studies a statistical network model generated by a large number of randomly sized overlapping communities, where any pair of nodes sharing a community is linked with probability q via the community. In the special case with q= 1 the model reduces to a random intersection graph which is known to generate high levels of transitivity also in the sparse context. The parameter q adds a degree of freedom and leads to a parsimonious and analytically tractable network model with tunable density, transitivity, and degree fluctuations. We prove that the parameters of this model can be consistently estimated in the large and sparse limiting regime using moment estimators based on partially observed densities of links, 2-stars, and triangles.

UR - http://www.scopus.com/inward/record.url?scp=85048231452&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-92871-5_4

DO - 10.1007/978-3-319-92871-5_4

M3 - Conference contribution

AN - SCOPUS:85048231452

SN - 978-3-319-92870-8

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 44

EP - 58

BT - Algorithms and Models for the Web Graphs

A2 - Bonato, A.

A2 - Pralat, P.

A2 - Raigorodskii, A,

PB - Springer

CY - Dordrecht

ER -

Karjalainen J, van Leeuwaarden JSH, Leskelä L. Parameter estimators of sparse random intersection graphs with thinned communities. In Bonato A, Pralat P, Raigorodskii A, editors, Algorithms and Models for the Web Graphs: 15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings. Dordrecht: Springer. 2018. p. 44-58. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-92871-5_4