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

Di Jin; Zhizhi Yu; Pengfei Jiao; Shirui Pan; Dongxiao He; Jia Wu; Philip S. Yu; Weixiong Zhang

Source-linked AI summary

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

Di Jin, Zhizhi Yu, Pengfei Jiao, Shirui Pan, Dongxiao He, Jia Wu, Philip S. Yu, Weixiong Zhang

arXiv:2101.01669v3Jan 3, 2021cs.SIcs.AIcs.LGphysics.soc-ph

TL;DR

Community detection is widely used, but its theoretical and methodological foundations remain insufficiently understood as network data and tasks become more complex. This survey unifies and reviews probabilistic graphical-model and deep-learning approaches, covering applications, resources, and open challenges. It organizes the field through a learning-based taxonomy and highlights adaptive model selection and complex network structures as continuing challenges.

Problem
The paper addresses limited understanding of the theoretical and methodological foundations of community detection, particularly for learning-based methods.
Method
The survey reviews and compares community detection methods through a unified taxonomy covering probabilistic graphical models and deep learning.
Results
The survey organizes representative methods, discusses applications, and synthesizes their similarities, differences, challenges, and future directions.
Takeaways & Limitations
The taxonomy provides a perspective for understanding, designing, and using learning-based community detection methods.
Takeaways & Limitations
Existing methods generally lack adaptive model selection for heterogeneous or dynamic networks and task-specific requirements.

Abstract

from arXiv · show

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. Despite all the recent advancement, there is still a lack of insightful understanding of the theoretical and methodological underpinning of community detection, which will be critically important for future development of the area of network analysis. In this paper, we develop and present a unified architecture of network community-finding methods to characterize the state-of-the-art of the field of community detection. Specifically, we provide a comprehensive review of the existing community detection methods and introduce a new taxonomy that divides the existing methods into two categories, namely probabilistic graphical model and deep learning. We then discuss in detail the main idea behind each method in the two categories. Furthermore, to promote future development of community detection, we release several benchmark datasets from several problem domains and highlight their applications to various network analysis tasks. We conclude with discussions of the challenges of the field and suggestions of possible directions for future research.

1 INTRODUCTION

Community detection partitions networks into densely connected groups with sparse links between groups, supporting analysis of organizational principles and applications such as recommendation and anomaly detection. This survey addresses limited understanding of the field’s theoretical and methodological foundations by organizing learning-based approaches across probabilistic modeling and deep learning.

Community detection divides network nodes into groups that are densely connected internally and sparsely linked across groups.
Network community detection supports tasks including recommendation, anomaly detection, and terrorist organization identification.
Deep learning methods address high-dimensional network data by learning low-dimensional representations, including through auto-encoders and generative adversarial approaches.
The survey responds to limited understanding of community detection’s theoretical and methodological foundations, particularly for learning-based methods.
The paper presents a unified perspective spanning probabilistic modeling and deep learning, emphasizing learning as a central issue in community modeling.
The survey reviews methods, analyzes their similarities and differences, identifies challenges, provides benchmark datasets and applications, and proposes five future directions.

2 PRELIMINARIES AND CATEGORIZATION

The paper defines networks, communities, and community detection before classifying learning-based methods into probabilistic graphical models and deep learning. The taxonomy further distinguishes graphical-model and deep-learning families by their modeling or representation-learning strategies.

2.1 Definitions, Terms and Notations: A network G = (V, E, X) contains nodes, edges, node attributes, and an adjacency matrix describing its topology.
2.1 Definitions, Terms and Notations: A community is a subgraph whose internal connections are dense and whose connections to other communities are sparse.
2.1 Definitions, Terms and Notations: Community detection maps each network node to at least one community identity, producing a community assignment C = (c1, c2, . . . , cn).
2.2 Categorization: The taxonomy groups community detection methods into probabilistic graphical models and deep learning.
2.2 Categorization: Probabilistic graphical models describe dependencies among network entities through edges and include directed, undirected, and hybrid graphical models.
2.2 Categorization: Deep learning methods map network data into low-dimensional, community-oriented representations using auto-encoders, generative adversarial networks, GCNs, or integrated GCN–graphical-model designs.

3 COMMUNITY DETECTION WITH PROBABILISTIC GRAPHICAL MODEL

Probabilistic graphical model methods detect communities by modeling network generation or relationships, with major families including directed, undirected, and hybrid models. These approaches encompass SBM variants, matrix factorization, and MRF-based methods that incorporate topology, attributes, temporal information, or node-pair constraints.

3 COMMUNITY DETECTION WITH PROBABILISTIC GRAPHICAL MODEL: Probabilistic graphical models detect communities by modeling the network generation process through directed, undirected, or hybrid graphical models.The surveyed directed models include stochastic block models, topic models, and matrix factorization.
3.1 Directed Graphical Models: SBM assigns nodes to communities through a generative probability model and infers hidden memberships by maximizing likelihood or using Gibbs sampling and expectation-maximization.The basic SBM has time complexity O(n2k2), while variants address degree heterogeneity, dynamic networks, overlapping communities, and mixed memberships.
3.1.1 Stochastic Block Model-based Methods: MMSB extends SBM by allowing nodes to belong to multiple communities, with time complexity O(n2k), while cMMSB models dependencies among nodes using a Copula function.These models target overlapping communities and diverse node information in directed networks.
3.1.1 Stochastic Block Model-based Methods: Degree-corrected SBM introduces node-specific degree parameters so expected degrees can match observed degrees under broad degree distributions.Extensions include sparse-network models, convexified modularity maximization, and network cross-validation for estimating hidden communities.
3.1.3 Matrix Factorization-based Methods: NMF-based methods extend from non-overlapping community detection to overlapping, attributed, dynamic, and semi-supervised settings.BIGCLAM combines non-negative node-community affiliation factors with block stochastic gradient descent to identify densely overlapping, hierarchically nested, and non-overlapping communities in massive networks.
3.2 Undirected Graphical Models: MRF-based methods use network topology, semantic attributes, or GNNs, while modularity-based energy functions can be optimized with max-sum belief propagation.A fused MRF-LDA factor-graph approach addresses the difficulty of sharing and jointly training the two models’ parameters.

4 COMMUNITY DETECTION WITH DEEP LEARNING

Deep learning methods detect communities by learning low-dimensional network representations, using architectures such as auto-encoders, GANs, and GCNs. Their effectiveness is strongest for homophilous community structures, which can limit robustness.

Auto-encoder-based Methods: Auto-encoders learn hidden representations by minimizing reconstruction error between original inputs and reconstructed data.Variants include stacked, sparse, denoising, and variational auto-encoders.
Auto-encoder-based Methods: Sparse auto-encoders address large-scale networks by imposing sparsity constraints on hidden representations.GraphEncoder has time complexity O(nbd), where b is the maximum hidden-layer width and d is the graph’s average degree.
Generative Adversarial Network-based Methods: GAN-based methods use a generator and discriminator in an unsupervised minimax framework to learn graph representations and discover communities.CommunityGAN jointly finds overlapping communities and learns a graph representation, while SEAL uses adversarial seed expansion.
Overview: Deep learning maps high-dimensional network data into low-dimensional representations, often followed by clustering to extract communities.Some methods integrate clustering directly into the model instead.
Summary for deep learning: Existing deep learning methods generally suit homophilous communities, where within-community links are dense and between-community links are sparse.This structural assumption may limit model robustness.

5 APPLICATIONS OF COMMUNITY DETECTION

The paper surveys benchmark datasets and applications of community detection across social, citation, collaboration, neuroscience, image-understanding, recommendation, and link-prediction settings. It also releases dataset information publicly to facilitate open research.

Open Datasets: The benchmark collection includes synthetic networks with known community structures and real-world networks organized by application domain.Synthetic benchmarks include GN and LFR networks; real-world networks include social, citation, collaboration, and other networks.
Open Datasets: The authors make detailed dataset information publicly accessible to facilitate open research on community detection.The released collection contains both synthetic and real-world networks.
Open Datasets: Real-world benchmark networks range from tens to millions of nodes, with edge counts from hundreds to hundreds of millions.These networks cover social, citation, collaboration, and other categories.
Applications in Different Areas: Community detection is applied to social networks, neuroscience, and image understanding, including spammer detection, crisis response, brain subdivision, and image representation.Examples combine probabilistic, graphical-model, and deep-learning approaches with network or semantic information.
Applications to Other Network Analysis Tasks: Community structures are also used in recommendation and link prediction to model user interests, missing connections, and community-level similarity.The surveyed methods incorporate community information into recommendation and cold-start link-prediction frameworks.

6 FUTURE DIRECTIONS

Future research must address scalability, interpretability, adaptive model selection, complex network structures, and integration between statistical modeling and deep learning. These challenges motivate methods that preserve accuracy, stability, efficiency, and semantic understanding across diverse networks and tasks.

6.1 Large Networks: Large networks create prohibitive memory and computation demands, while reduction or approximation can lose network information and modeling accuracy.Existing methods may also require many training instances or model parameters.
6.2 Interpretability: Current community summaries often rely on a few top-ranked words, which may not adequately convey sentence-level node semantics or relationships among words.Future methods should use network information to improve semantic interpretation.
6.3 Adaptive Community Model Selection: Few methods automatically adapt algorithm choice to network characteristics or task requirements while maintaining model accuracy and stability.The goal is a unified architecture that can select methods for settings such as heterogeneous or dynamic networks and accuracy- or time-sensitive tasks.
6.4 Networks with Complex Structures: Heterogeneous, dynamic, hierarchical, and incomplete networks expose limitations in methods that assume homogeneous data or require repeated retraining as networks evolve.Dynamic-network retraining can be time-consuming and may not satisfy real-time processing demands.
6.5 Integrating Statistical Modeling and Deep Learning: Integrating statistical modeling with deep learning remains promising but unresolved, especially regarding time complexity, interpretability, and diverse community patterns.The paper highlights heterophily and randomness as patterns requiring robust integrated methods.

7 CONCLUSION

The conclusion presents the paper as a comprehensive synthesis of community detection research organized through a unified learning-based perspective. It also emphasizes applications and unresolved challenges as priorities for continued study.

7 CONCLUSION: The paper reviews community detection approaches and organizes existing methods into probabilistic graphical model and deep learning categories.This taxonomy is intended to provide a unified perspective on the field.
7 CONCLUSION: It compares and summarizes methods in both categories while discussing applications of community detection across various fields.The paper frames community detection as highly application oriented.
7 CONCLUSION: The conclusion highlights challenging open problems and suggests that synthesizing the state of the art can improve understanding of community detection in network science.The authors acknowledge that the review cannot include all community detection literature.

APPENDIX A

Appendix A points readers to the paper’s notation resources, including a table summarizing key notation and symbols used in the main text.

APPENDIX A: The main text’s key terms and notations are listed in Table 1.The passage directs readers to a notation reference.
APPENDIX A: Table 6 is titled “Summary of notations.”The table provides a notation-summary resource.

APPENDIX B

Appendix B gives the overall community-detection processes for several stochastic block model variants. It covers the basic Bernoulli SBM, MMSB, and DSBM through separate algorithms.

APPENDIX B: The appendix presents overall community-detection processes for the basic SBM with a Bernoulli distribution, MMSB, and DSBM.Each model is associated with a separate algorithm.
APPENDIX B: Algorithm 1 describes the process based on the basic SBM with a Bernoulli distribution.The passage identifies this as one of three model-specific procedures.

APPENDIX C

Appendix C presents algorithmic procedures for several community-detection methods, covering basic and dynamic stochastic block models, topic-model approaches, and Bayesian attributed graph clustering.

Basic SBM-based method: The basic SBM-based method assumes nodes are independently divided into k communities and estimates likelihood parameters ω and π using EM.The procedure takes n and k as input and outputs node community assignments C.
MMSB-based method: The MMSB-based method is presented as a separate algorithmic approach with node-wise processing steps.The supplied procedure identifies an MMSB-based method and begins by iterating over nodes.
DSBM-based method: The DSBM-based method generates a social network using SBM, then iterates over times t > 1 and node pairs at each time.Its inputs include n, π, A, and T, and its output is the community assignment C(T).
SSN-LDA method: SSN-LDA generates one social interaction profile by iterating over each node and its neighbors, then choosing a social interaction.The appendix identifies this procedure as the SSN-LDA method.
Attributed and temporal procedures: The appendix also provides a generation procedure for Bayesian attributed graph clustering, alongside a basic SBM procedure using time attributes and parameters ε, µ, and ν.The attributed-graph procedure is labeled BAGC, while the basic SBM procedure outputs node community assignments C.