A survey on theoretical advances of community detection in networks

被引：25
作者：
Zhao Y. [1 ]
机构：
[1] Department of Statistics, George Mason University, Fairfax, VA
来源：
Wiley Interdisciplinary Reviews: Computational Statistics | 2017年 / 9卷 / 05期
基金：
美国国家科学基金会;
关键词：
community detection; consistency; stochastic blockmodels;
D O I：
10.1002/wics.1403
中图分类号：
学科分类号：
摘要：
Real-world networks usually have community structure, that is, nodes are grouped into densely connected communities. Community detection is one of the most popular and best-studied research topics in network science and has attracted attention in many different fields, including computer science, statistics, social sciences, among others. Numerous approaches for community detection have been proposed in literature, from ad hoc algorithms to systematic model-based approaches. The large number of available methods leads to a fundamental question: whether a certain method can provide consistent estimates of community labels. The stochastic blockmodel (SBM) and its variants provide a convenient framework for the study of such problems. This article is a survey on the recent theoretical advances of community detection. The authors review a number of community detection methods and their theoretical properties, including graph cut methods, profile likelihoods, the pseudo-likelihood method, the variational method, belief propagation, spectral clustering, and semidefinite relaxations of the SBM. The authors also briefly discuss other research topics in community detection such as robust community detection, community detection with nodal covariates and model selection, as well as suggest a few possible directions for future research. WIREs Comput Stat 2017, 9:e1403. doi: 10.1002/wics.1403. For further resources related to this article, please visit the WIREs website. © 2017 Wiley Periodicals, Inc.
引用
收藏
相关论文
共 90 条
[21]  
Newman M.E.J., Modularity and community structure in networks, Proc Natl Acad Sci U S A, 103, (2006)
[22]  
Fortunato S., Community detection in graphs, Phys Rep, 486, (2010)
[23]  
Snijders T., Nowicki K., Estimation and prediction for stochastic block-structures for graphs with latent block structure, J Classification, 14, (1997)
[24]  
Nowicki K., Snijders T.A.B., Estimation and prediction for stochastic blockstructures, J Am Stat Assoc, 96, (2001)
[25]  
Karrer B., Newman M.E.J., Stochastic blockmodels and community structure in networks, Phys Rev E, 83, (2011)
[26]  
Zhao Y., Levina E., Zhu J., Consistency of community detection in networks under degree-corrected stochastic block models, Ann Stat, 40, (2012)
[27]  
Airoldi E.M., Blei D.M., Fienberg S.E., Xing E.P., Mixed membership stochastic blockmodels, J Mach Learn Res, 9, (2008)
[28]  
Handcock M.D., Raftery A.E., Tantrum J.M., Model-based clustering for social networks, J R Stat Soc A, 170, (2007)
[29]  
Bickel P.J., Chen A., A nonparametric view of network models and Newman-Girvan and other modularities, Proc Natl Acad Sci U S A, 106, (2009)
[30]  
Amini A., Chen A., Bickel P., Levina E., Fitting community models to large sparse networks, Ann Stat, 41, (2013)
123456789