2014

How Many Communities Are There?

Saldana, Diego Franco, Yu, Yi, Feng, Yang

Understand

Stochastic blockmodels and variants thereof are among the most widely used approaches to community detection for social networks and relational data.

A stochastic blockmodel partitions the nodes of a network into disjoint sets, called communities.
The approach is inherently related to clustering with mixture models; and raises a similar model selection problem for the number of communities.
The Bayesian information criterion (BIC) is a popular solution, however, for stochastic blockmodels, the conditional independence assumption given the communities of the endpoints among different edges is usually violated in practice.

Built on

Spectral clustering and the high-dimensional stochastic blockmodel
Rohe, K., Chatterjee, S., and Yu, B. (2011) · 1915
Earlier work this paper cites.
Objective criteria for the evaluation of clustering methods
Rand, W. M. (1971) · 1971
Earlier work this paper cites.
Lower bounds for the partitioning of graphs
Donath, W. E. and Hoffman, A. J. (1973) · 1973
Earlier work this paper cites.
A bayesian analysis of some nonparametric problems
Ferguson, T. S. (1973) · 1973
Earlier work this paper cites.
Stochastic blockmodels: First steps
Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983) · 1983
Earlier work this paper cites.
Composite likelihood methods
Lindsay, B. G. (1988) · 1988
Earlier work this paper cites.
Towards efficient hierarchical designs by ratio cut partitioning
Wei, Y.-C. and Cheng, C.-K. (1989) · 1989
Earlier work this paper cites.
Random Fields on a Network: Modeling, Statistics, and Applications
Guyon, X. (1995) · 1995
Earlier work this paper cites.
Planar graphs and finite element meshes
Spielmat, D. A. and Teng, S.-H. (1996) · 1996
Earlier work this paper cites.
On the quality of spectral separators
Guattery, S. and Miller, G. L. (1998) · 1998
Earlier work this paper cites.
A composite likelihood approach to binary spatial data
Heagerty, P. J. and Lele, S. R. (1998) · 1998
Earlier work this paper cites.
On the generation of correlated artifical binary data
Leisch, F., Weingessel, A., and Hornik, K. (1998) · 1998
Earlier work this paper cites.
Estimating a dirichlet distribution
Minka, T. P. (2000) · 2000
Earlier work this paper cites.
Normalized cuts and image segmentation
Shi, J. and Malik, J. (2000) · 2000
Earlier work this paper cites.
Bayesian analysis of mixture models with an unknown number of components - an alternative to reversible jump methods
Stephens, M. (2000) · 2000
Earlier work this paper cites.

Similar

A note on pseudolikelihood constructed from marginal densities
Cox, D. R. and Reid, N. (2004) · 2004
Cited alongside, same era.
Particle filters for mixture models with an unknown number of components
Fearnhead, P. (2004) · 2004
Cited alongside, same era.
Detecting community structure in networks
Newman, M. E. J. (2004) · 2004
Cited alongside, same era.
Finding and evaluating community structure in networks
Newman, M. E. J. and Girvan, M. (2004) · 2004
Cited alongside, same era.
A note on composite likelihood inference and model selection
Varin, C. and Vidoni, P. (2005) · 2005
Cited alongside, same era.
Model-based clustering for social networks
Handcock, M. S., Raftery, A. E., and Tantrum, J. M. (2007) · 2007
Cited alongside, same era.
Bayesian finite mixtures with an unknown number of components: The allocation sampler
Nobile, A. and Fearnside, A. (2007) · 2007
Cited alongside, same era.
A tutorial on spectral clustering
von Luxburg, U. (2007) · 2007
Cited alongside, same era.
A mixture model for random graphs
Daudin, J.-J., Picard, F., and Robin, S. (2008) · 2008
Cited alongside, same era.
On composite marginal likelihoods
Varin, C. (2008) · 2008
Cited alongside, same era.
Composite likelihood bayesian information criteria for model selection in high-dimensional data
Gao, X. and Song, P. X.-K. (2010) · 2010
Cited alongside, same era.
A survey of statistical network models
Goldenberg, A., Zheng, A. X., Fienberg, S. E., and Airoldi, E. M. (2010) · 2010
Cited alongside, same era.

Then

An overview of composite likelihood methods
Varin, C., Reid, N., and Firth, D. (2011) · 2011
Later among the works it cites.
A mixed effects model for longitudinal relational and network data, with applications to international trade and conflict
Westveld, A. H. and Hoff, P. D. (2011) · 2011
Later among the works it cites.
Stochastic blockmodels with a growing number of classes
Choi, D. S., Wolfe, P. J., and Airoldi, E. M. (2012) · 2012
Later among the works it cites.
Computational statistical methods for social network models
Hunter, D. R., Krivitsky, P. N., and Schweinberger, M. (2012) · 2012
Later among the works it cites.
Variational Bayesian inference and complexity control for stochastic block models
Latouche, P., Birmelé, E., and Ambroise, C. (2012) · 2012
Later among the works it cites.
Null models for network data
Original
Perry, P. O. and Wolfe, P. J. (2012) · 2012
Later among the works it cites.
Consistency of community detection in networks under degree-corrected stochastic block models
Zhao, Y., Levina, E., and Zhu, J. (2012) · 2012
Later among the works it cites.
Improved bayesian inference for the stochastic blockmodel with application to large networks
McDaid, A. F., Murphy, T. B., Friel, N., and Hurley, N. J. (2013) · 2013
Later among the works it cites.
Mixed membership stochastic blockmodels
Airoldi, E. M., Blei, D. M., Fienberg, S. E., and Xing, E. P. (2008) · 2014
Closest in time.
Network cross-validation for determining the number of communities in network data
Original
Chen, K. and Lei, J. (2014) · 2014
Closest in time.
Inconsistency of pitman-yor process mixtures for the number of components
Miller, J. W. and Harrison, M. T. (2014) · 2014
Closest in time.
The highest dimensional stochastic blockmodel with a regularized estimator
Rohe, K., Qin, T., and Fan, H. (2014) · 2014
Closest in time.
Fast community detection by SCORE
Jin, J. (2015) · 2015
Closest in time.
Local dependence in random graph models: characterization, properties and statistical inference
Schweinberger, M. and Handcock, M. S. (2015) · 2015
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…