2021

A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning

Jin, Di, Yu, Zhizhi, Jiao, Pengfei et al.

Understand

Community detection, a fundamental task for network analysis, aims to partition a network into multiple sub-structures to help reveal their latent functions.

Community detection has been extensively studied in and broadly applied to many real-world network problems.
Classical approaches to community detection typically utilize probabilistic graphical models and adopt a variety of prior knowledge to infer community structures.
As the problems that network methods try to solve and the network data to be analyzed become increasingly more sophisticated, new approaches have also been proposed and developed, particularly those that utilize deep learning and convert networked data into low dimensional representation.

Built on

W. W. Zachary, “An information flow model for conflict and fission in small groups,” J. Anthropol. Res
1977
Earlier work this paper cites.
P. W. Holland, K. B. Laskey, and S. Leinhardt, “Stochastic blockmodels: First steps,” Soc. Networks
1983
Earlier work this paper cites.
T. A. Snijders and K. Nowicki, “Estimation and prediction for stochastic blockmodels for graphs with latent block structure,” J. Classif
1997
Earlier work this paper cites.
D. J. Watts and S. H. Strogatz, “Collective dynamics of ’small-world’ networks,” Nature
1998
Earlier work this paper cites.
R. M. Neal and G. E. Hinton, “A view of the em algorithm that justifies incremental, sparse, and other variants,” in Learning in Graphical Models
1998
Earlier work this paper cites.
A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science
1999
Earlier work this paper cites.
D. D. Lee and H. S. Seung, “Algorithms for non-negative matrix factorization,” in Proceedings of NeurIPS
2000
Earlier work this paper cites.
M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proc. Natl. Acad. Sci
2002
Earlier work this paper cites.
D. M. Blei, A. Y. Ng, and M. I. Jordan, “Latent dirichlet allocation,” J. Mach. Learn. Res
2003
Earlier work this paper cites.
M. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Phys. Rev. E
2004
Earlier work this paper cites.
L. A. Adamic and N. S. Glance, “The political blogosphere and the 2004 U.S. election: divided they blog,” in Proceedings of SIGKDD
2005
Earlier work this paper cites.
J. Leskovec, J. M. Kleinberg, and C. Faloutsos, “Graphs over time: densification laws, shrinking diameters and possible explanations,” in Proceedings of SIGKDD
2005
Earlier work this paper cites.
G. E. Hinton and R. R. Salakhutdinov, “Reducing the dimensionality of data with neural networks.,” Science
2006
Earlier work this paper cites.
H. Zhang, B. Qiu, C. L. Giles, H. C. Foley, and J. Yen, “An lda-based community structure discovery approach for large-scale social networks,” in Proceedings of ISI
2007
Earlier work this paper cites.
E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, “Mixed membership stochastic blockmodels,” J. Mach. Learn. Res
2008
Earlier work this paper cites.
R.-S. Wang, S. Zhang, Y. Wang, X.-S. Zhang, and L. Chen, “Clustering complex networks and biological networks by nonnegative matrix factorization with various similarity measures,” Neurocomputing
2008
Earlier work this paper cites.
P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad, “Collective classification in network data,” AI Magazine
2008
Earlier work this paper cites.
W. Fu, L. Song, and E. P. Xing, “Dynamic mixed membership blockmodel for evolving networks,” in Proceedings of ICML
2009
Earlier work this paper cites.
A. Lancichinetti and S. Fortunato, “Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities,” Phys. Rev. E
2009
Earlier work this paper cites.
W. Ren, G. Yan, X. Liao, and L. Xiao, “Simple probabilistic algorithm for detecting community structure,” Phys. Rev. E
2009
Earlier work this paper cites.
J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, “Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,” Internet Math
2009
Earlier work this paper cites.
C. C. Aggarwal and H. Wang, “Managing and mining graph data,” Advances in Database Systems
2010
Earlier work this paper cites.
E. P. Xing, W. Fu, and L. Song, “A state-space mixed membership blockmodel for dynamic network tomography,” Ann. Appl. Stat
2010
Earlier work this paper cites.
X. Ma, L. Gao, X. Yong, and L. Fu, “Semi-supervised clustering algorithm for community structure detection in complex networks,” Physical A: Statistical Mechanics and its Applications
2010
Earlier work this paper cites.
F. Wang, T. Li, X. Wang, S. Zhu, and C. Ding, “Community discovery using nonnegative matrix factorization,” Data Min. Knowl. Discov
2011
Earlier work this paper cites.
B. Karrer and M. E. J. Newman, “Stochastic blockmodels and community structure in networks,” Phys. Rev. E
2011
Earlier work this paper cites.
T. Yang, Y. Chi, S. Zhu, Y. Gong, and R. Jin, “Detecting communities and their evolutions in dynamic social networks - a bayesian approach,” Mach. Learn
2011
Earlier work this paper cites.
P. Latouche, E. Birmelé, C. Ambroise, et al
2011
Earlier work this paper cites.
S. Nowozin and C. H. Lampert, “Structured learning and prediction in computer vision,” Found. Trends Comput. Graph. Vis
2011
Earlier work this paper cites.
Z. Yang, J. Tang, J. Li, and W. Yang, “Social Community Analysis via a Factor Graph Model,” IEEE Intell. Syst
2011
Earlier work this paper cites.
Ginsparg and Paul, “Arxiv at 20,” Nature
2011
Earlier work this paper cites.
Y. Zhang and D. Yeung, “Overlapping community detection via bounded nonnegative matrix tri-factorization,” in Proceedings of SIGKDD
2012
Earlier work this paper cites.
P. Zhang, F. Krzakala, J. Reichardt, and L. Zdeborová, “Comparative study for inference of hidden classes in stochastic block models,” J. Stat. Mech.-Theory Exp
2012
Earlier work this paper cites.
Y. Zhao, E. Levina, and J. Zhu, “Consistency of community detection in networks under degree-corrected stochastic block models,” Ann. Stat
2012
Earlier work this paper cites.
Z. Yin, L. Cao, Q. Gu, and J. Han, “Latent community topic analysis: Integration of community discovery with topic modeling,” ACM Trans. Intell. Syst. Technol
2012
Earlier work this paper cites.
Y. Cha and J. Cho, “Social-network analysis using topic models,” in Proceedings of SIGIR
2012
Earlier work this paper cites.
Z. Xu, Y. Ke, Y. Wang, H. Cheng, and J. Cheng, “A model-based approach to attributed graph clustering,” in Proceedings of COMAD
2012
Earlier work this paper cites.
D. Kuang, H. Park, and C. H. Q. Ding, “Symmetric nonnegative matrix factorization for graph clustering,” in Proceedings of SIAM
2012
Earlier work this paper cites.
A. Passarella, R. I. M. Dunbar, M. Conti, and F. Pezzoni, “Ego network models for future internet social networking environments,” Comput. Commun
2012
Earlier work this paper cites.
J. J. McAuley and J. Leskovec, “Learning to discover social circles in ego networks,” in Proceedings of NeurIPS
2012
Earlier work this paper cites.
W. Lin, X. Kong, P. S. Yu, Q. Wu, Y. Jia, and C. Li, “Community detection in incomplete information networks,” in Proceedings of WWW
2012
Earlier work this paper cites.
J. Xie, S. Kelley, and B. K. Szymanski, “Overlapping community detection in networks: the state of the art and comparative study,” ACM Comput. Surv
2013
Earlier work this paper cites.
F. D. Malliaros and M. Vazirgiannis, “Clustering and community detection in directed networks: A survey,” Phys. Rep.-Rev. Sec. Phys. Lett
2013
Earlier work this paper cites.
J. Yang and J. Leskovec, “Overlapping community detection at scale: a nonnegative matrix factorization approach,” in Proceedings of WSDM
2013
Earlier work this paper cites.
J. Zeng, W. K. Cheung, and J. Liu, “Learning topic models by belief propagation,” IEEE Trans. Pattern Anal. Mach. Intell
2013
Earlier work this paper cites.
P. Zhang and C. Moore, “Scalable detection of statistically significant communities and hierarchies, using message passing for modularity,” Proc. Natl. Acad. Sci
2014
Earlier work this paper cites.
A. Anandkumar, R. Ge, D. J. Hsu, and S. M. Kakade, “A tensor approach to learning mixed membership community models,” J. Mach. Learn. Res
2014
Earlier work this paper cites.
C. C. Aggarwal and K. Subbian, “Evolutionary network analysis: A survey,” ACM Comput. Surv
2014
Earlier work this paper cites.
X. Tang and C. C. Yang, “Detecting social media hidden communities using dynamic stochastic blockmodel with temporal dirichlet process,” ACM Trans. Intell. Syst. Technol
2014
Earlier work this paper cites.
K. S. Xu and A. O. Hero, “Dynamic stochastic blockmodels for time-evolving social networks,” IEEE J. Sel. Top. Signal Process
2014
Earlier work this paper cites.
Y. Jia, Y. Gao, W. Yang, J. Huo, and Y. Shi, “A novel ego-centered academic community detection approach via factor graph model,” in Proceedings of IDEAL
2014
Earlier work this paper cites.
F. Tian, B. Gao, Q. Cui, E. Chen, and T. Liu, “Learning deep representations for graph clustering,” in Proceedings of AAAI
2014
Earlier work this paper cites.
D. P. Kingma and M. Welling, “Auto-encoding variational bayes,” in Proceedings of ICLR
2014
Earlier work this paper cites.
I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. C. Courville, and Y. Bengio, “Generative adversarial nets,” in Proceedings of NeurIPS
2014
Earlier work this paper cites.
S. Harenberg, G. Bello, L. Gjeltema, S. Ranshous, and N. Samatova, “Community detection in large-scale networks: A survey and empirical evaluation,” WIREs Computational Statistics
2014
Earlier work this paper cites.
S. Mukherjee, H. Lamba, and G. Weikum, “Experience-aware item recommendation in evolving review communities,” in Proceedings of ICDM
2015
Earlier work this paper cites.

Similar

S. Jia, L. Gao, Y. Gao, J. Nastos, Y. Wang, X. Zhang, and H. Wang, “Defining and identifying cograph communities in complex networks,” New J. Phys
2015
Cited alongside, same era.
Y. Li, K. He, D. Bindel, and J. E. Hopcroft, “Uncovering the small community structure in large networks: A local spectral approach,” in Proceedings of WWW
2015
Cited alongside, same era.
D. He, D. Liu, D. Jin, and W. Zhang, “A stochastic model for detecting heterogeneous link communities in complex networks,” in Proceedings of AAAI
2015
Cited alongside, same era.
B. Yang, X. Zhao, and X. Liu, “Bayesian approach to modeling and detecting communities in signed network,” in Proceedings of AAAI
2015
Cited alongside, same era.
K. S. Xu, “Stochastic block transition models for dynamic networks,” in Proceedings of AISTATS
2015
Cited alongside, same era.
X. Shi, H. Lu, Y. He, and S. He, “Community detection in social network with pairwisely constrained symmetric non-negative matrix factorization,” in Proceedings of ASONAM
2015
Cited alongside, same era.
Y. Pei, N. Chakraborty, and K. P. Sycara, “Nonnegative matrix tri-factorization with graph regularization for community detection in social networks,” in Proceedings of IJCAI
2015
Cited alongside, same era.
L. Yang, X. Cao, D. Jin, X. Wang, and D. Meng, “A unified semi-supervised community detection framework using latent space graph regularization,” IEEE Trans. Cybern
2015
Cited alongside, same era.
L. Yang, X. Cao, D. He, C. Wang, X. Wang, and W. Zhang, “Modularity based community detection with deep learning,” in Proceedings of IJCAI
2016
Cited alongside, same era.
T. Hartmann, A. Kappes, and D. Wagner, “Clustering evolving networks,” vol. 9220, pp. 280–329, 2016
2016
Cited alongside, same era.
X. Fan, R. Y. D. Xu, and L. Cao, “Copula mixed-membership stochastic block model,” in Proceedings of IJCAI
2016
Cited alongside, same era.
J. D. Wilson, N. T. Stevens, and W. H. Woodall, “Modeling and detecting change in temporal networks via a dynamic degree corrected stochastic block model,” Qual. Reliab. Eng. Int
2016
Cited alongside, same era.

Then

Y. Jia, Q. Zhang, W. Zhang, and X. Wang, “Communitygan: Community detection with generative adversarial nets,” in Proceedings of WWW
2019
Later among the works it cites.
G. Sperlì, “A deep learning based community detection approach,” in Proceedings of SAC
2019
Later among the works it cites.
C. Lee and D. J. Wilkinson, “A review of stochastic block models and extensions for graph clustering,” Appl. Netw. Sci
2019
Later among the works it cites.
S. Pal and M. Coates, “Scalable MCMC in degree corrected stochastic block mode,” in Proceedings of ICASSP
2019
Later among the works it cites.
X. Wu, P. Jiao, Y. Wang, T. Li, W. Wang, and B. Wang, “Dynamic stochastic block model with scale-free characteristic for temporal complex networks,” in Proceedings of DASFAA
2019
Later among the works it cites.
N. Mehta, L. Carin, and P. Rai, “Stochastic blockmodels meet graph neural networks,” in Proceedings of ICML
2019
Later among the works it cites.
X. Wu, P. Jiao, Y. Wang, T. Li, W. Wang, and B. Wang, “Dynamic stochastic block model with scale-free characteristic for temporal complex networks,” in Proceedings of DASFAA
2019
Later among the works it cites.
D. Jin, J. Huang, P. Jiao, L. Yang, D. He, F. Fogelman-Soulié, and Y. Huang, “A novel generative topic embedding model by introducing network communities,” in Proceedings of WWW
2019
Later among the works it cites.
D. Jin, X. You, W. Li, D. He, P. Cui, F. Fogelman-Soulié, and T. Chakraborty, “Incorporating network embedding into Markov random field for better community detection,” in Proceedings of AAAI
2019
Later among the works it cites.
D. He, W. Song, D. Jin, Z. Feng, and Y. Huang, “An end-to-end community detection model: Integrating LDA into Markov random field via factor graph,” in Proceedings of IJCAI
2019
Later among the works it cites.
D. Jin, Z. Liu, W. Li, D. He, and W. Zhang, “Graph convolutional networks meet Markov random fields: Semi-supervised community detection in attribute networks,” in Proceedings of AAAI
2019
Later among the works it cites.
M. Qu, Y. Bengio, and J. Tang, “GMNN: graph Markov neural networks,” in Proceedings of ICML
2019
Later among the works it cites.
Y. Xie, X. Wang, D. Jiang, and R. Xu, “High-performance community detection in social networks using a deep transitive autoencoder,” Inf. Sci
2019
Later among the works it cites.
V. Bhatia and R. Rani, “A distributed overlapping community detection model for large graphs using autoencoder,” Future Gener. Comput. Syst
2019
Later among the works it cites.
C. Wang, S. Pan, R. Hu, G. Long, J. Jiang, and C. Zhang, “Attributed graph clustering: a deep attentional embedding approach,” in Proceedings of IJCAI
2019
Later among the works it cites.
J. J. Choong, X. Liu, and T. Murata, “Optimizing variational graph autoencoder for community detection,” in Proceedings of BigData
2019
Later among the works it cites.
D. Jin, B. Li, P. Jiao, D. He, and W. Zhang, “Network-specific variational auto-encoder for embedding in attribute networks,” in Proceedings of IJCAI
2019
Later among the works it cites.
F. Sun, M. Qu, J. Hoffmann, C. Huang, and J. Tang, “vgraph: A generative model for joint community detection and node representation learning,” in Proceedings of NeurIPS
2019
Later among the works it cites.
M. K. Rahman and A. Azad, “Evaluating the community structures from network images using neural networks,” in Proceedings of Complex Networks and Their Applications
2019
Later among the works it cites.
Z. Tao, H. Liu, J. Li, Z. Wang, and Y. Fu, “Adversarial graph embedding for ensemble clustering,” in Proceedings of IJCAI
2019
Later among the works it cites.
Y. Sun, S. Wang, T. Hsieh, X. Tang, and V. G. Honavar, “MEGAN: A generative adversarial network for multi-view network embedding,” in Proceedings of IJCAI
2019
Later among the works it cites.
H. Gao, J. Pei, and H. Huang, “Progan: Network embedding via proximity generative adversarial network,” in Proceedings of SIGKDD
2019
Later among the works it cites.
D. Jin, B. Li, P. Jiao, D. He, and H. Shan, “Community detection via joint graph convolutional network embedding in attribute network,” in Proceedings of ICANN
2019
Later among the works it cites.
Y. Zheng, S. Chen, X. Zhang, and D. Wang, “Heterogeneous graph convolutional networks for temporal community detection,” arXiv
2019
Later among the works it cites.
H. Gao, J. Pei, and H. Huang, “Conditional random field enhanced graph convolutional neural networks,” in Proceedings of SIGKDD
2019
Later among the works it cites.
O. Shchur and S. Günnemann, “Overlapping community detection with graph neural networks,” arXiv
2019
Later among the works it cites.
L. Chu, Z. Wang, J. Pei, Y. Zhang, Y. Yang, and E. Chen, “Finding theme communities from database networks,” Proc. VLDB Endow
2019
Later among the works it cites.
J. Liu, G. Ma, F. Jiang, C. Lu, P. S. Yu, and A. B. Ragin, “Community-preserving graph convolutions for structural and functional joint embedding of brain networks,” in Proceedings of BigData
2019
Later among the works it cites.
Z. Li, J. Tang, and T. Mei, “Deep collaborative embedding for social image understanding,” IEEE Trans. Pattern Anal. Mach. Intell
2019
Later among the works it cites.
S. Zhang, L. Yao, L. V. Tran, A. Zhang, and Y. Tay, “Quaternion collaborative filtering for recommendation,” in Proceedings of IJCAI
2019
Later among the works it cites.
H. Wan, Y. Zhang, J. Zhang, and J. Tang, “Aminer: Search and mining of academic social networks,” Data Intell
2019
Later among the works it cites.
Y. Wang, D. Jin, K. Musial, and J. Dang, “Community detection in social networks considering topic correlations,” in proceedings of AAAI
2019
Later among the works it cites.
J. Shao, Z. Zhang, Z. Yu, J. Wang, Y. Zhao, and Q. Yang, “Community detection and link prediction via cluster-driven low-rank matrix completion,” in Proceedings of IJCAI
2019
Later among the works it cites.
V. Satuluri, Y. Wu, X. Zheng, Y. Qian, B. Wichers, Q. Dai, G. M. Tang, J. Jiang, and J. Lin, “Simclusters: Community-based representations for heterogeneous recommendations at twitter,” in Proceedings of SIGKDD
2020
Later among the works it cites.
M. R. Keyvanpour, M. B. Shirzad, and M. Ghaderi, “AD-C: a new node anomaly detection based on community detection in social networks,” Int. J. Electron. Bus
2020
Later among the works it cites.
Y. Zhang, Y. Xiong, Y. Ye, T. Liu, W. Wang, Y. Zhu, and P. S. Yu, “SEAL: learning heuristics for community detection with generative adversarial networks,” in Proceedings of SIGKDD
2020
Later among the works it cites.
F. Liu, S. Xue, J. Wu, C. Zhou, W. Hu, C. Paris, S. Nepal, J. Yang, and P. S. Yu, “Deep learning for community detection: Progress, challenges and opportunities,” in Proceedings of IJCAI
2020
Later among the works it cites.
M. G. Bhattacharjee M, Banerjee M, “Change point estimation in a dynamic stochastic block model,” J. Mach. Learn. Res
2020
Later among the works it cites.
D. Jin, B. Li, P. Jiao, D. He, H. Shan, and W. Zhang, “Modeling with node popularities for autonomous overlapping community detection,” ACM Trans. Intell. Syst. Technol
2020
Later among the works it cites.
D. Jin, K. Wang, G. Zhang, P. Jiao, D. He, F. Fogelman-Soulie, and X. Huang, “Detecting communities with multiplex semantics by distinguishing background, general and specialized topics,” IEEE Trans. Knowl. Data Eng
2020
Later among the works it cites.
D. Jin, B. Zhang, Y. Song, D. He, Z. Feng, S. Chen, W. Li, and K. Musial, “Modmrf: A modularity-based Markov random field method for community detection,” Neurocomputing
2020
Later among the works it cites.
H. Sun, F. He, J. Huang, Y. Sun, Y. Li, C. Wang, L. He, Z. Sun, and X. Jia, “Network embedding for community detection in attributed networks,” ACM Trans. Knowl. Discov. Data
2020
Later among the works it cites.
R. Xu, Y. Che, X. Wang, J. Hu, and Y. Xie, “Stacked autoencoder-based community detection method via an ensemble clustering framework,” Inf. Sci
2020
Later among the works it cites.
A. Sarkar, N. Mehta, and P. Rai, “Graph representation learning via ladder gamma variational autoencoders,” in Proceedings of AAAI
2020
Later among the works it cites.
H. Hong, X. Li, and M. Wang, “GANE: A generative adversarial network embedding,” IEEE Trans. Neural Networks Learn. Syst
2020
Later among the works it cites.
D. He, L. Zhai, Z. Li, D. Jin, L. Yang, Y. Huang, and P. S. Yu, “Adversarial mutual information learning for network embedding,” in Proceedings of IJCAI
2020
Later among the works it cites.
L. Yang, Y. Wang, J. Gu, C. Wang, X. Cao, and Y. Guo, “JANE: jointly adversarial network embedding,” in Proceedings of IJCAI
2020
Later among the works it cites.
Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” IEEE Trans. Neural Networks Learn. Syst
2020
Later among the works it cites.
D. He, Y. Song, D. Jin, Z. Feng, B. Zhang, Z. Yu, and W. Zhang, “Community-centric graph convolutional network for unsupervised community detection,” in Proceedings of IJCAI
2020
Later among the works it cites.
H. V. Lierde, T. W. S. Chow, and G. Chen, “Scalable spectral clustering for overlapping community detection in large-scale networks,” IEEE Trans. Knowl. Data Eng
2020
Later among the works it cites.
Y. Wu, D. Lian, Y. Xu, L. Wu, and E. Chen, “Graph convolutional networks with Markov random field reasoning for social spammer detection,” in Proceedings of AAAI
2020
Later among the works it cites.
D. Jin, R. Li, and J. Xu, “Multiscale community detection in functional brain networks constructed using dynamic time warping,” IEEE Trans. Neural Syst. Rehabil. Eng
2020
Later among the works it cites.
X. He, K. Deng, X. Wang, Y. Li, Y. Zhang, and M. Wang, “Lightgcn: Simplifying and powering graph convolution network for recommendation,” in Proceedings of SIGIR
2020
Later among the works it cites.
D. Jin, C. Huo, C. Liang, and L. Yang, “Heterogeneous graph neural network via attribute completion,” in Proceddings of WWW
2021
Closest in time.
D. Jin, X. Wang, D. He, J. Dang, and W. Zhang, “Robust detection of link communities with summary description in social networks,” IEEE Trans. Knowl. Data Eng
2021
Closest in time.
Z. He, J. Liu, Y. Zeng, L. Wei, and Y. Huang, “Content to node: Self-translation network embedding,” IEEE Trans. Knowl. Data Eng
2021
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…