Moment-based parameter estimation in binomial random intersection graph models

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

Tutkijat

Organisaatiot

Kuvaus

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.

Yksityiskohdat

AlkuperäiskieliEnglanti
OtsikkoAlgorithms and Models for the Web Graph
Alaotsikko14th International Workshop, WAW 2017, Toronto, ON, Canada, June 15–16, 2017, Revised Selected Papers
ToimittajatAnthony Bonato, Fan Chung Graham, Paweł Prałat
TilaJulkaistu - 6 syyskuuta 2017
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaWorkshop on Algorithms and Models for the Web Graph - Fields Institute for Research in Mathematical Sciences, Toronto, Kanada
Kesto: 15 kesäkuuta 201716 kesäkuuta 2017
Konferenssinumero: 14
http://www.math.ryerson.ca/waw2017/index.html

Julkaisusarja

NimiLecture Notes in Computer Science
KustantajaSpringer
Vuosikerta10519
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349

Workshop

WorkshopWorkshop on Algorithms and Models for the Web Graph
LyhennettäWAW
MaaKanada
KaupunkiToronto
Ajanjakso15/06/201716/06/2017
www-osoite

ID: 13005931