Community detection and graph partitioning

Abstract

Many methods have been proposed for community detection in networks. Some of the most promising are methods based on statistical inference, which rest on solid mathematical foundations and return excellent results in practice. In this paper we show that two of the most widely used inference methods can be mapped directly onto versions of the standard minimum-cut graph partitioning problem, which allows us to apply any of the many well-understood partitioning algorithms to the solution of community detection problems. We illustrate the approach by adapting the Laplacian spectral partitioning method to perform community inference, testing the resulting algorithm on a range of examples, including computer-generated and real-world networks. Both the quality of the results and the running time rival the best previous methods.

5 pages, 2 figures

References in corpus (6)

• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• (Un)detectable cluster structure in sparse networks

Cited by in corpus (19)

• Spectral methods for network community detection and graph partitioning
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Eigenvalue Spectra of Modular Networks
• Universality of the stochastic block model
• Nearly-Linear Time Spectral Graph Reduction for Scalable Graph Partitioning and Data Visualization
• Weighted Laplacian and Its Theoretical Applications
• A network approach for power grid robustness against cascading failures
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Temporal stability in human interaction networks
• SCOREH+: A High-Order Node Proximity Spectral Clustering on Ratios-of-Eigenvectors Algorithm for Community Detection
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Estimating parameters of a multipartite loglinear graph model via the EM algorithm
• Coalition Formation Algorithm of Prosumers in a Smart Grid Environment
• Understanding Vulnerability of Communities in Complex Networks
• Automated Allocation of Detention Rooms Based on Inverse Graph Partitioning
• Error-Correcting Decoders for Communities in Networks