Estimation of dense stochastic block models visited by random walks

DOI10.1214/21-EJS1899MaRDI QIDQ2074313zbMATH OpenFDO

Authors Viet Chi Tran, Thi Phuong Thuy Vo

Publication date 9 February 2022

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.08010, https://projecteuclid.org/journals/electronic-journal-of-statistics/volume-15/issue-2/Estimation-of-dense-stochastic-block-models-visited-by-random-walks/10.1214/21-EJS1899.full

zbMATH Keywords

chain-referral surveyEM estimationgraphonincomplete likelihoodrandom graphrandom walk explorationrespondent driven samplingsampling biasstochastic approximation expectation-maximization

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Sampling theory, sample surveys (62D05) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Abstract: We are interested in recovering information on a stochastic block model from the subgraph discovered by an exploring random walk. Stochastic block models correspond to populations structured into a finite number of types, where two individuals are connected by an edge independently from the other pairs and with a probability depending on their types. We consider here the dense case where the random network can be approximated by a graphon. This problem is motivated from the study of chain-referral surveys where each interviewee provides information on her/his contacts in the social network. First, we write the likelihood of the subgraph discovered by the random walk: biases are appearing since hubs and majority types are more likely to be sampled. Even for the case where the types are observed, the maximum likelihood estimator is not explicit any more. When the types of the vertices is unobserved, we use an SAEM algorithm to maximize the likelihood. Second, we propose a different estimation strategy using new results by Athreya and Roellin. It consists in de-biasing the maximum likelihood estimator proposed in Daudin et al. and that ignores the biases.

Recommendations

• Chain-referral sampling on stochastic block models
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• Stochastic blockmodels with a growing number of classes
• On model selection for dense stochastic block models
• Empirical Bayes estimation for the stochastic blockmodel

Cites work

• A critical threshold for design effects in network sampling
• An introduction to variational methods for graphical models
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Asymptotic Statistics
• Central limit theorems for network driven sampling
• Community detection and stochastic block models: recent developments
• Consistency and asymptotic normality of stochastic block models estimators from sampled data
• Consistency of maximum-likelihood and variational estimators in the stochastic block model
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Coupling a stochastic approximation version of EM with an MCMC procedure
• Dense graph limits under respondent-driven sampling
• Hidden population size estimation from respondent-driven sampling: a network approach
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• Improved inference for respondent-driven sampling data with application to HIV prevalence estimation
• Large networks and graph limits
• Novel sampling design for respondent-driven sampling
• Parameter identifiability in a class of random graph mixture models
• Snowball Sampling
• Stochastic versions of the em algorithm: an experimental study in the mixture case
• The phase transition in the configuration model
• Variational Inference for Stochastic Block Models From Sampled Data

Cited in

(1)

• Chain-referral sampling on stochastic block models

This page was built for publication: Estimation of dense stochastic block models visited by random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2074313)