Spectral methods for network community detection and graph partitioning

Abstract

We consider three distinct and well studied problems concerning network structure: community detection by modularity maximization, community detection by statistical inference, and normalized-cut graph partitioning. Each of these problems can be tackled using spectral algorithms that make use of the eigenvectors of matrix representations of the network. We show that with certain choices of the free parameters appearing in these spectral algorithms the algorithms for all three problems are, in fact, identical, and hence that, at least within the spectral approximations used here, there is no difference between the modularity- and inference-based community detection methods, or between either and graph partitioning.

11 pages, 5 figures

References in corpus (10)

• Modularity and community structure in networks
• 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
• Community detection and graph partitioning
• Spectra of random graphs with arbitrary expected degrees
• Eigenvalue Spectra of Modular Networks
• (Un)detectable cluster structure in sparse networks
• Multiway Spectral Clustering: A Margin-Based Perspective

Cited by in corpus (66)

• Influence maximization in complex networks through optimal percolation
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• A Comprehensive Survey on Community Detection with Deep Learning
• Community Detection via Maximization of Modularity and Its Variants
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Multiway spectral community detection in networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Deep Community Detection
• Accelerating Community Detection by Using K-core Subgraphs
• Network community-based model reduction for vortical flows
• Using higher-order Markov models to reveal flow-based communities in networks
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Adaptive Modularity Maximization via Edge Weighting Scheme
• Cross-validation estimate of the number of clusters in a network
• A paradox in community detection
• Spectral Detection of Simplicial Communities via Hodge Laplacians
• Universality of the stochastic block model
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• A divisive spectral method for network community detection
• Simplex2Vec embeddings for community detection in simplicial complexes
• Consistency landscape of network communities
• Discovering the hidden community structure of public transportation networks
• Modularity and Projection of Bipartite Networks
• BrainNNExplainer: An Interpretable Graph Neural Network Framework for Brain Network based Disease Analysis
• Comparative analysis on the selection of number of clusters in community detection
• Geometric Multiscale Community Detection: Markov Stability and Vector Partitioning
• StaTIX - Statistical Type Inference on Linked Data
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• On the Permanence of Vertices in Network Communities
• Community Detection in Partially Observable Social Networks
• Detectability of the spectral method for sparse graph partitioning
• Finite size analysis of the detectability limit of the stochastic block model
• Efficient Mobility-on-Demand System with Ride-Sharing
• A Graph Signal Processing View on Functional Brain Imaging
• Inferring cultural regions from correlation networks of given baby names
• Decoding communities in networks
• Eigenvector dynamics under perturbation of modular networks
• Unsupervised Community Detection with Modularity-Based Attention Model
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Unsupervised Machine Learning of Open Source Russian Twitter Data Reveals Global Scope and Operational Characteristics
• Ising-Based Louvain Method: Clustering Large Graphs with Specialized Hardware
• Importance of initial conditions in the polarization of complex networks
• Fine-tuning Partition-aware Item Similarities for Efficient and Scalable Recommendation
• Learning Markov models via low-rank optimization
• A Versatile Framework for Attributed Network Clustering via K-Nearest Neighbor Augmentation
• Community Detection in networks by Dynamical Optimal Transport Formulation
• Temporal stability in human interaction networks
• Quantum walk on simplicial complexes for simplicial community detection
• Spectral State Compression of Markov Processes
• Linear Constrained Rayleigh Quotient Optimization: Theory and Algorithms
• Urban Analytics: Multiplexed and Dynamic Community Networks
• Multi Loci Phylogenetic Analysis with Gene Tree Clustering
• Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks
• Coalition Formation Algorithm of Prosumers in a Smart Grid Environment
• Almost exact recovery in noisy semi-supervised learning
• Evidential Label Propagation Algorithm for Graphs
• Krylov Subspace Approximation for Local Community Detection in Large Networks
• Network inference and community detection, based on covariance matrices, correlations and test statistics from arbitrary distributions
• A generalized inverse for graphs with absorption
• Using Laplacian Spectrum as Graph Feature Representation
• Automated Allocation of Detention Rooms Based on Inverse Graph Partitioning
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach
• Network Representation Learning: From Traditional Feature Learning to Deep Learning
• A class of randomized Subset Selection Methods for large complex networks
• Optimal Partition of a Tree with Social Distance
• Non-backtracking walks reveal compartments in sparse chromatin interaction networks