Consistent estimation of dynamic and multi-layer block models

Qiuyi Han, Kevin Xu, Edoardo Airoldi
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1511-1520, 2015.

Abstract

Significant progress has been made recently on theoretical analysis of estimators for the stochastic block model (SBM). In this paper, we consider the multi-graph SBM, which serves as a foundation for many application settings including dynamic and multi-layer networks. We explore the asymptotic properties of two estimators for the multi-graph SBM, namely spectral clustering and the maximum-likelihood estimate (MLE), as the number of layers of the multi-graph increases. We derive sufficient conditions for consistency of both estimators and propose a variational approximation to the MLE that is computationally feasible for large networks. We verify the sufficient conditions via simulation and demonstrate that they are practical. In addition, we apply the model to two real data sets: a dynamic social network and a multi-layer social network with several types of relations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-hanb15, title = {Consistent estimation of dynamic and multi-layer block models}, author = {Han, Qiuyi and Xu, Kevin and Airoldi, Edoardo}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1511--1520}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/hanb15.pdf}, url = {https://proceedings.mlr.press/v37/hanb15.html}, abstract = {Significant progress has been made recently on theoretical analysis of estimators for the stochastic block model (SBM). In this paper, we consider the multi-graph SBM, which serves as a foundation for many application settings including dynamic and multi-layer networks. We explore the asymptotic properties of two estimators for the multi-graph SBM, namely spectral clustering and the maximum-likelihood estimate (MLE), as the number of layers of the multi-graph increases. We derive sufficient conditions for consistency of both estimators and propose a variational approximation to the MLE that is computationally feasible for large networks. We verify the sufficient conditions via simulation and demonstrate that they are practical. In addition, we apply the model to two real data sets: a dynamic social network and a multi-layer social network with several types of relations.} }
Endnote
%0 Conference Paper %T Consistent estimation of dynamic and multi-layer block models %A Qiuyi Han %A Kevin Xu %A Edoardo Airoldi %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-hanb15 %I PMLR %P 1511--1520 %U https://proceedings.mlr.press/v37/hanb15.html %V 37 %X Significant progress has been made recently on theoretical analysis of estimators for the stochastic block model (SBM). In this paper, we consider the multi-graph SBM, which serves as a foundation for many application settings including dynamic and multi-layer networks. We explore the asymptotic properties of two estimators for the multi-graph SBM, namely spectral clustering and the maximum-likelihood estimate (MLE), as the number of layers of the multi-graph increases. We derive sufficient conditions for consistency of both estimators and propose a variational approximation to the MLE that is computationally feasible for large networks. We verify the sufficient conditions via simulation and demonstrate that they are practical. In addition, we apply the model to two real data sets: a dynamic social network and a multi-layer social network with several types of relations.
RIS
TY - CPAPER TI - Consistent estimation of dynamic and multi-layer block models AU - Qiuyi Han AU - Kevin Xu AU - Edoardo Airoldi BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-hanb15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1511 EP - 1520 L1 - http://proceedings.mlr.press/v37/hanb15.pdf UR - https://proceedings.mlr.press/v37/hanb15.html AB - Significant progress has been made recently on theoretical analysis of estimators for the stochastic block model (SBM). In this paper, we consider the multi-graph SBM, which serves as a foundation for many application settings including dynamic and multi-layer networks. We explore the asymptotic properties of two estimators for the multi-graph SBM, namely spectral clustering and the maximum-likelihood estimate (MLE), as the number of layers of the multi-graph increases. We derive sufficient conditions for consistency of both estimators and propose a variational approximation to the MLE that is computationally feasible for large networks. We verify the sufficient conditions via simulation and demonstrate that they are practical. In addition, we apply the model to two real data sets: a dynamic social network and a multi-layer social network with several types of relations. ER -
APA
Han, Q., Xu, K. & Airoldi, E.. (2015). Consistent estimation of dynamic and multi-layer block models. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1511-1520 Available from https://proceedings.mlr.press/v37/hanb15.html.

Related Material