Advanced

Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure

Snijders, Tom A. B. and Nowicki, Krzysztof LU (1997) In Journal of Classification 14. p.75-100
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Colored graph, EM algorithm, Latent class model, Social networks, Gibbs sampling
in
Journal of Classification
volume
14
pages
75 - 100
publisher
Springer New York
external identifiers
  • scopus:0031495186
ISSN
1432-1343
DOI
10.1007/s003579900004
language
English
LU publication?
yes
id
ea745206-a48e-4a61-a3d9-fdb43967a910 (old id 1767796)
date added to LUP
2011-01-27 14:50:33
date last changed
2017-08-06 04:47:11
@article{ea745206-a48e-4a61-a3d9-fdb43967a910,
  abstract     = {A statistical approach to a posteriori blockmodeling for graphs<br/><br>
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.<br/><br>
Statistical procedures are derived for estimating the probabilities of edges<br/><br>
and for predicting the block structure from observations of the edge pattern only. ML estimators can be computed using the EM algorithm, but this<br/><br>
strategy is practical only for small graphs. A Bayesian estimator,<br/><br>
based on Gibbs sampling, is proposed. This estimator is practical also<br/><br>
for large graphs. When ML estimators are used, the block structure can be<br/><br>
predicted based on predictive likelihood. When Gibbs sampling is used,<br/><br>
the block structure can be predicted from posterior predictive probabilities.<br/><br>
<br/><br>
A side result is that when the number of vertices tends to infinity while<br/><br>
the probabilities remain constant, the block structure can be recovered<br/><br>
correctly with probability tending to 1.},
  author       = {Snijders, Tom A. B. and Nowicki, Krzysztof},
  issn         = {1432-1343},
  keyword      = {Colored graph,EM algorithm,Latent class model,Social networks,Gibbs sampling},
  language     = {eng},
  pages        = {75--100},
  publisher    = {Springer New York},
  series       = {Journal of Classification},
  title        = {Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure},
  url          = {http://dx.doi.org/10.1007/s003579900004},
  volume       = {14},
  year         = {1997},
}