Moment-based parameter estimation in binomial random intersection graph models

Joona Karjalainen; Lasse Leskelä

doi:10.1007/978-3-319-67810-8_1

Moment-based parameter estimation in binomial random intersection graph models

Joona Karjalainen, Lasse Leskelä

Department of Mathematics and Systems Analysis

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

2 Citations (Scopus)

Abstract

Binomial random intersection graphs can be used as parsimonious statistical models of large and sparse networks, with one parameter for the average degree and another for transitivity, the tendency of neighbours of a node to be connected. This paper discusses the estimation of these parameters from a single observed instance of the graph, using moment estimators based on observed degrees and frequencies of 2-stars and triangles. The observed data set is assumed to be a subgraph induced by a set of n₀ nodes sampled from the full set of n nodes. We prove the consistency of the proposed estimators by showing that the relative estimation error is small with high probability for n₀ ≫ n^2/3 ≫ 1. As a byproduct, our analysis confirms that the empirical transitivity coefficient of the graph is with high probability close to the theoretical clustering coefficient of the model.

Original language	English
Title of host publication	Algorithms and Models for the Web Graph
Subtitle of host publication	14th International Workshop, WAW 2017, Toronto, ON, Canada, June 15–16, 2017, Revised Selected Papers
Editors	Anthony Bonato, Fan Chung Graham, Paweł Prałat
Pages	1–15
ISBN (Electronic)	9783319678108
DOIs	https://doi.org/10.1007/978-3-319-67810-8_1
Publication status	Published - 6 Sep 2017
MoE publication type	A4 Article in a conference publication
Event	Workshop on Algorithms and Models for the Web Graph - Fields Institute for Research in Mathematical Sciences, Toronto, Canada Duration: 15 Jun 2017 → 16 Jun 2017 Conference number: 14 http://www.math.ryerson.ca/waw2017/index.html

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10519
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	Workshop on Algorithms and Models for the Web Graph
Abbreviated title	WAW
Country	Canada
City	Toronto
Period	15/06/2017 → 16/06/2017
Internet address	http://www.math.ryerson.ca/waw2017/index.html

Keywords

statistical network model
network motif
model fitting
sparse graph
moment estimator
two-mode network
overlapping communities

Access to Document

10.1007/978-3-319-67810-8_1

https://arxiv.org/abs/1704.04278

Fingerprint Dive into the research topics of 'Moment-based parameter estimation in binomial random intersection graph models'. Together they form a unique fingerprint.

Cite this

Karjalainen, J., & Leskelä, L. (2017). Moment-based parameter estimation in binomial random intersection graph models. In A. Bonato, F. C. Graham, & P. Prałat (Eds.), Algorithms and Models for the Web Graph: 14th International Workshop, WAW 2017, Toronto, ON, Canada, June 15–16, 2017, Revised Selected Papers (pp. 1–15). (Lecture Notes in Computer Science; Vol. 10519). https://doi.org/10.1007/978-3-319-67810-8_1

Karjalainen, Joona ; Leskelä, Lasse. / Moment-based parameter estimation in binomial random intersection graph models. Algorithms and Models for the Web Graph: 14th International Workshop, WAW 2017, Toronto, ON, Canada, June 15–16, 2017, Revised Selected Papers. editor / Anthony Bonato ; Fan Chung Graham ; Paweł Prałat. 2017. pp. 1–15 (Lecture Notes in Computer Science).

@inproceedings{bc3630f055074804822570cd1448523b,

title = "Moment-based parameter estimation in binomial random intersection graph models",

abstract = "Binomial random intersection graphs can be used as parsimonious statistical models of large and sparse networks, with one parameter for the average degree and another for transitivity, the tendency of neighbours of a node to be connected. This paper discusses the estimation of these parameters from a single observed instance of the graph, using moment estimators based on observed degrees and frequencies of 2-stars and triangles. The observed data set is assumed to be a subgraph induced by a set of n0 nodes sampled from the full set of n nodes. We prove the consistency of the proposed estimators by showing that the relative estimation error is small with high probability for n0 ≫ n2/3 ≫ 1. As a byproduct, our analysis confirms that the empirical transitivity coefficient of the graph is with high probability close to the theoretical clustering coefficient of the model.",

keywords = "statistical network model, network motif, model fitting, sparse graph, moment estimator, two-mode network, overlapping communities",

author = "Joona Karjalainen and Lasse Leskel{\"a}",

year = "2017",

month = sep,

day = "6",

doi = "10.1007/978-3-319-67810-8_1",

language = "English",

isbn = "9783319678092",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "1–15",

editor = "Anthony Bonato and Graham, {Fan Chung} and Pawe{\l} Pra{\l}at",

booktitle = "Algorithms and Models for the Web Graph",

note = "Workshop on Algorithms and Models for the Web Graph, WAW ; Conference date: 15-06-2017 Through 16-06-2017",

url = "http://www.math.ryerson.ca/waw2017/index.html",

}

Karjalainen, J & Leskelä, L 2017, Moment-based parameter estimation in binomial random intersection graph models. in A Bonato, FC Graham & P Prałat (eds), Algorithms and Models for the Web Graph: 14th International Workshop, WAW 2017, Toronto, ON, Canada, June 15–16, 2017, Revised Selected Papers. Lecture Notes in Computer Science, vol. 10519, pp. 1–15, Workshop on Algorithms and Models for the Web Graph, Toronto, Canada, 15/06/2017. https://doi.org/10.1007/978-3-319-67810-8_1

Moment-based parameter estimation in binomial random intersection graph models. / Karjalainen, Joona ; Leskelä, Lasse.

Algorithms and Models for the Web Graph: 14th International Workshop, WAW 2017, Toronto, ON, Canada, June 15–16, 2017, Revised Selected Papers. ed. / Anthony Bonato; Fan Chung Graham; Paweł Prałat. 2017. p. 1–15 (Lecture Notes in Computer Science; Vol. 10519).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Moment-based parameter estimation in binomial random intersection graph models

AU - Karjalainen, Joona

AU - Leskelä, Lasse

N1 - Conference code: 14

PY - 2017/9/6

Y1 - 2017/9/6

N2 - Binomial random intersection graphs can be used as parsimonious statistical models of large and sparse networks, with one parameter for the average degree and another for transitivity, the tendency of neighbours of a node to be connected. This paper discusses the estimation of these parameters from a single observed instance of the graph, using moment estimators based on observed degrees and frequencies of 2-stars and triangles. The observed data set is assumed to be a subgraph induced by a set of n0 nodes sampled from the full set of n nodes. We prove the consistency of the proposed estimators by showing that the relative estimation error is small with high probability for n0 ≫ n2/3 ≫ 1. As a byproduct, our analysis confirms that the empirical transitivity coefficient of the graph is with high probability close to the theoretical clustering coefficient of the model.

AB - Binomial random intersection graphs can be used as parsimonious statistical models of large and sparse networks, with one parameter for the average degree and another for transitivity, the tendency of neighbours of a node to be connected. This paper discusses the estimation of these parameters from a single observed instance of the graph, using moment estimators based on observed degrees and frequencies of 2-stars and triangles. The observed data set is assumed to be a subgraph induced by a set of n0 nodes sampled from the full set of n nodes. We prove the consistency of the proposed estimators by showing that the relative estimation error is small with high probability for n0 ≫ n2/3 ≫ 1. As a byproduct, our analysis confirms that the empirical transitivity coefficient of the graph is with high probability close to the theoretical clustering coefficient of the model.

KW - statistical network model

KW - network motif

KW - model fitting

KW - sparse graph

KW - moment estimator

KW - two-mode network

KW - overlapping communities

U2 - 10.1007/978-3-319-67810-8_1

DO - 10.1007/978-3-319-67810-8_1

M3 - Conference contribution

SN - 9783319678092

T3 - Lecture Notes in Computer Science

SP - 1

EP - 15

BT - Algorithms and Models for the Web Graph

A2 - Bonato, Anthony

A2 - Graham, Fan Chung

A2 - Prałat, Paweł

T2 - Workshop on Algorithms and Models for the Web Graph

Y2 - 15 June 2017 through 16 June 2017

ER -

Karjalainen J , Leskelä L. Moment-based parameter estimation in binomial random intersection graph models. In Bonato A, Graham FC, Prałat P, editors, Algorithms and Models for the Web Graph: 14th International Workshop, WAW 2017, Toronto, ON, Canada, June 15–16, 2017, Revised Selected Papers. 2017. p. 1–15. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-67810-8_1