Likelihood Inference for Large Scale Stochastic Blockmodels with Covariates based on a Divide-and-Conquer Parallelizable Algorithm with Communication

Sandipan Roy, Yves Atchadé, George Michailidis

Research output: Contribution to journalArticle

Abstract

We consider a stochastic blockmodel equipped with node covariate information, that is, helpful in analyzing social network data. The key objective is to obtain maximum likelihood estimates of the model parameters. For this task, we devise a fast, scalable Monte Carlo EM type algorithm based on case-control approximation of the log-likelihood coupled with a subsampling approach. A key feature of the proposed algorithm is its parallelizability, by processing portions of the data on several cores, while leveraging communication of key statistics across the cores during each iteration of the algorithm. The performance of the algorithm is evaluated on synthetic datasets and compared with competing methods for blockmodel parameter estimation. We also illustrate the model on data from a Facebook derived social network enhanced with node covariate information. Supplemental materials for this article are available online.

LanguageEnglish
Number of pages12
JournalJournal of Computational and Graphical Statistics
Early online date27 Feb 2019
DOIs
StatusE-pub ahead of print - 27 Feb 2019

Fingerprint

Divide-and-conquer Algorithm
Likelihood Inference
Covariates
Social Networks
Subsampling
Case-control
Synthetic Data
Vertex of a graph
Maximum Likelihood Estimate
Parameter Estimation
Likelihood
Statistics
Iteration
Communication
Inference
Approximation
Model
Node
Social networks

Keywords

  • Case-control approximation
  • Monte Carlo EM
  • Parallel computation with communication
  • Social network
  • Subsampling

ASJC Scopus subject areas

  • Statistics and Probability
  • Discrete Mathematics and Combinatorics
  • Statistics, Probability and Uncertainty

Cite this

@article{d80ed95bc4454e40832f682e953e48d7,
title = "Likelihood Inference for Large Scale Stochastic Blockmodels with Covariates based on a Divide-and-Conquer Parallelizable Algorithm with Communication",
abstract = "We consider a stochastic blockmodel equipped with node covariate information, that is, helpful in analyzing social network data. The key objective is to obtain maximum likelihood estimates of the model parameters. For this task, we devise a fast, scalable Monte Carlo EM type algorithm based on case-control approximation of the log-likelihood coupled with a subsampling approach. A key feature of the proposed algorithm is its parallelizability, by processing portions of the data on several cores, while leveraging communication of key statistics across the cores during each iteration of the algorithm. The performance of the algorithm is evaluated on synthetic datasets and compared with competing methods for blockmodel parameter estimation. We also illustrate the model on data from a Facebook derived social network enhanced with node covariate information. Supplemental materials for this article are available online.",
keywords = "Case-control approximation, Monte Carlo EM, Parallel computation with communication, Social network, Subsampling",
author = "Sandipan Roy and Yves Atchad{\'e} and George Michailidis",
note = "28 pages, 4 figures",
year = "2019",
month = "2",
day = "27",
doi = "10.1080/10618600.2018.1554486",
language = "English",
journal = "Journal of Computational and Graphical Statistics",
issn = "1061-8600",
publisher = "American Statistical Association",

}

TY - JOUR

T1 - Likelihood Inference for Large Scale Stochastic Blockmodels with Covariates based on a Divide-and-Conquer Parallelizable Algorithm with Communication

AU - Roy, Sandipan

AU - Atchadé, Yves

AU - Michailidis, George

N1 - 28 pages, 4 figures

PY - 2019/2/27

Y1 - 2019/2/27

N2 - We consider a stochastic blockmodel equipped with node covariate information, that is, helpful in analyzing social network data. The key objective is to obtain maximum likelihood estimates of the model parameters. For this task, we devise a fast, scalable Monte Carlo EM type algorithm based on case-control approximation of the log-likelihood coupled with a subsampling approach. A key feature of the proposed algorithm is its parallelizability, by processing portions of the data on several cores, while leveraging communication of key statistics across the cores during each iteration of the algorithm. The performance of the algorithm is evaluated on synthetic datasets and compared with competing methods for blockmodel parameter estimation. We also illustrate the model on data from a Facebook derived social network enhanced with node covariate information. Supplemental materials for this article are available online.

AB - We consider a stochastic blockmodel equipped with node covariate information, that is, helpful in analyzing social network data. The key objective is to obtain maximum likelihood estimates of the model parameters. For this task, we devise a fast, scalable Monte Carlo EM type algorithm based on case-control approximation of the log-likelihood coupled with a subsampling approach. A key feature of the proposed algorithm is its parallelizability, by processing portions of the data on several cores, while leveraging communication of key statistics across the cores during each iteration of the algorithm. The performance of the algorithm is evaluated on synthetic datasets and compared with competing methods for blockmodel parameter estimation. We also illustrate the model on data from a Facebook derived social network enhanced with node covariate information. Supplemental materials for this article are available online.

KW - Case-control approximation

KW - Monte Carlo EM

KW - Parallel computation with communication

KW - Social network

KW - Subsampling

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

U2 - 10.1080/10618600.2018.1554486

DO - 10.1080/10618600.2018.1554486

M3 - Article

JO - Journal of Computational and Graphical Statistics

T2 - Journal of Computational and Graphical Statistics

JF - Journal of Computational and Graphical Statistics

SN - 1061-8600

ER -