An efficient and principled method for detecting communities in networks
arXiv:1104.3590 · doi:10.1103/PhysRevE.84.036103
Abstract
A fundamental problem in the analysis of network data is the detection of network communities, groups of densely interconnected nodes, which may be overlapping or disjoint. Here we describe a method for finding overlapping communities based on a principled statistical approach using generative network models. We show how the method can be implemented using a fast, closed-form expectation-maximization algorithm that allows us to analyze networks of millions of nodes in reasonable running times. We test the method both on real-world networks and on synthetic benchmarks and find that it gives results competitive with previous methods. We also show that the same approach can be used to extract nonoverlapping community divisions via a relaxation method, and demonstrate that the algorithm is competitively fast and accurate for the nonoverlapping problem.
arXiv comment14 pages, 5 figures, 1 table
References in corpus (20)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Uncovering the overlapping community structure of complex networks in nature and society
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Random graphs with arbitrary degree distributions and their applications
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Comparing community structure identification
- Spatial Networks
- Community detection algorithms: a comparative analysis
- Hierarchical structure and the prediction of missing links in networks
- Stochastic blockmodels and community structure in networks
- The Dynamics of Viral Marketing
- Link communities reveal multiscale complexity in networks
- The performance of modularity maximization in practical contexts
- Line Graphs, Link Partitions and Overlapping Communities
- The spatial structure of networks
- Evaluating Local Community Methods in Networks
Cited by in corpus (98)
- Community detection in networks: A user guide
- Networks beyond pairwise interactions: structure and dynamics
- Overlapping Community Detection in Networks: the State of the Art and Comparative Study
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- The ground truth about metadata and community detection in networks
- A Classification for Community Discovery Methods in Complex Networks
- A network approach to topic models
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Parsimonious module inference in large networks
- Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
- Community detection, link prediction, and layer interdependence in multilayer networks
- A General Optimization Technique for High Quality Community Detection in Complex Networks
- Efficiently inferring community structure in bipartite networks
- Inferring the mesoscale structure of layered, edge-valued and time-varying networks
- Clustering scientific publications based on citation relations: A systematic comparison of different methods
- Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
- Entropy of stochastic blockmodel ensembles
- Bayesian stochastic blockmodeling
- Inference of hyperedges and overlapping communities in hypergraphs
- Nonparametric weighted stochastic block models
- Scalable Recommendation with Poisson Factorization
- Model selection and hypothesis testing for large-scale network models with overlapping groups
- Infinite Edge Partition Models for Overlapping Community Detection and Link Prediction
- Detection of Core-Periphery Structure in Networks Using Spectral Methods and Geodesic Paths
- Communities and bottlenecks: Trees and treelike networks have high modularity
- Streaming Graph Challenge: Stochastic Block Partition
- Exploring the structural regularities in networks
- Community detection with node attributes in multilayer networks
- A statistical inference approach to structural reconstruction of complex networks from binary time series
- Disentangling bipartite and core-periphery structure in financial networks
- Structural and Functional Discovery in Dynamic Networks with Non-negative Matrix Factorization
- Scalable Text and Link Analysis with Mixed-Topic Link Models
- Adapting the Stochastic Block Model to Edge-Weighted Networks
- Accurate and scalable social recommendation using mixed-membership stochastic block models
- Social contagions on time-varying community networks
- Spectra of random graphs with community structure and arbitrary degrees
- Detecting Overlapping Communities in Networks Using Spectral Methods
- Mixed Membership Estimation for Social Networks
- Bayesian Poisson Tucker Decomposition for Learning the Structure of International Relations
- A testing based extraction algorithm for identifying significant communities in networks
- Universality of the stochastic block model
- Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
- Hierarchical community structure in networks
- Randomizing hypergraphs preserving degree correlation and local clustering
- Community Detection in Networks using Graph Distance
- Synchronization over and community detection in multiplex signed networks with constraints
- Change-point detection in dynamic networks via graphon estimation
- Multilayer Networks for Text Analysis with Multiple Data Types
- Exact Blind Community Detection from Signals on Multiple Graphs
- Algorithmic detectability threshold of the stochastic block model
- Structure and inference in hypergraphs with node attributes
- Generative model for reciprocity and community detection in networks
- Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
- Discovering link communities in complex networks by exploiting link dynamics
- Layer reconstruction and missing link prediction of multilayer network with a Maximum A Posteriori estimation
- Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
- Anomaly detection and community detection in networks
- Estimating Mixed Memberships with Sharp Eigenvector Deviations
- Community detection and reciprocity in networks by jointly modeling pairs of edges
- Efficiently Detecting Overlapping Communities through Seeding and Semi-Supervised Learning
- Community detection for networks with unipartite and bipartite structure
- Null Models and Community Detection in Multi-Layer Networks
- Mapping the spectrum of 3D communities in human chromosome conformation capture data
- Communities as Well Separated Subgraphs With Cohesive Cores: Identification of Core-Periphery Structures in Link Communities
- A useful criterion on studying consistent estimation in community detection
- Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
- Unsupervised Community Detection with Modularity-Based Attention Model
- A Modular Multiscale Approach to Overlapping Community Detection
- Multiresolution Tensor Decomposition for Multiple Spatial Passing Networks
- Generative models for local network community detection
- The interplay between ranking and communities in networks
- Local multiresolution order in community detection
- Hypothesis testing for populations of networks
- Community Detection in networks by Dynamical Optimal Transport Formulation
- Modular decomposition of Markov chain: detecting hierarchical organization of pervasive communities
- Navigating differential structures in complex networks
- The latent cognitive structures of social networks
- Soft happy colourings and community structure of networks
- Nonnegative Bayesian nonparametric factor models with completely random measures for community detection
- Comprehensive spectral approach for community structure analysis on complex networks
- Directed degree corrected mixed membership model and estimating community memberships in directed networks
- Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models
- A Random Dot Product Model for Weighted Networks
- Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
- Overlapping community detection in networks via sparse spectral decomposition
- Fast and reliable inference algorithm for hierarchical stochastic block models
- A Generative Model for Exploring Structure Regularities in Attributed Networks
- Feature Learning and Network Structure from Noisy Node Activity Data
- Latent Channel Networks
- Network-based models for social recommender systems
- Bayesian Modeling of Random Walker for Community Detection in Networks
- Identification of hybrid node and link communities in complex networks
- Modeling Node Exposure for Community Detection in Networks
- Model Selection in Overlapping Stochastic Block Models
- Information-theoretic Limits for Community Detection in Network Models
- Overlapping Communities Detection via Measure Space Embedding
- Clustering on the Edge: Learning Structure in Graphs