Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure
Author
Summary, in English
A statistical approach to a posteriori blockmodeling for graphs
is proposed. The model assumes that the vertices of the graph are partitioned into two unknown blocks and that the probability of an edge between two vertices depends only on the blocks to which they belong.
Statistical procedures are derived for estimating the probabilities of edges
and for predicting the block structure from observations of the edge pattern only. ML estimators can be computed using the EM algorithm, but this
strategy is practical only for small graphs. A Bayesian estimator,
based on Gibbs sampling, is proposed. This estimator is practical also
for large graphs. When ML estimators are used, the block structure can be
predicted based on predictive likelihood. When Gibbs sampling is used,
the block structure can be predicted from posterior predictive probabilities.
A side result is that when the number of vertices tends to infinity while
the probabilities remain constant, the block structure can be recovered
correctly with probability tending to 1.
is proposed. The model assumes that the vertices of the graph are partitioned into two unknown blocks and that the probability of an edge between two vertices depends only on the blocks to which they belong.
Statistical procedures are derived for estimating the probabilities of edges
and for predicting the block structure from observations of the edge pattern only. ML estimators can be computed using the EM algorithm, but this
strategy is practical only for small graphs. A Bayesian estimator,
based on Gibbs sampling, is proposed. This estimator is practical also
for large graphs. When ML estimators are used, the block structure can be
predicted based on predictive likelihood. When Gibbs sampling is used,
the block structure can be predicted from posterior predictive probabilities.
A side result is that when the number of vertices tends to infinity while
the probabilities remain constant, the block structure can be recovered
correctly with probability tending to 1.
Department/s
Publishing year
1997
Language
English
Pages
75-100
Publication/Series
Journal of Classification
Volume
14
Document type
Journal article
Publisher
Springer
Topic
- Probability Theory and Statistics
Keywords
- Colored graph
- EM algorithm
- Latent class model
- Social networks
- Gibbs sampling
Status
Published
ISBN/ISSN/Other
- ISSN: 1432-1343