Spectral redemption in clustering sparse networks
From MaRDI portal
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Stochastic network models in operations research (90B15) Detection theory in information and communication theory (94A13) Information theory (general) (94A15)
Abstract: Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities even when other algorithms such as belief propagation can do so. Here we introduce a new class of spectral algorithms based on a non-backtracking walk on the directed edges of the graph. The spectrum of this operator is much better-behaved than that of the adjacency matrix or other commonly used matrices, maintaining a strong separation between the bulk eigenvalues and the eigenvalues relevant to community structure even in the sparse case. We show that our algorithm is optimal for graphs generated by the stochastic block model, detecting communities all the way down to the theoretical limit. We also show the spectrum of the non-backtracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering.
Recommendations
- Consistency of spectral clustering in stochastic block models
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- Spectral clustering for community detection
- Detecting overlapping communities in networks using spectral methods
- Spectral clustering and the high-dimensional stochastic blockmodel
Cites work
- A nonparametric view of network models and Newman–Girvan and other modularities
- A spectral approach to analysing belief propagation for 3-colouring
- Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
- Community structure in social and biological networks
- Graph partitioning via adaptive spectral techniques
- Information flow on trees
- NON-BACKTRACKING RANDOM WALKS MIX FASTER
- On the distribution of the roots of certain symmetric matrices
- Random matrices, nonbacktracking walks, and orthogonal polynomials
- The expected eigenvalue distribution of a large regular graph
- THE IHARA-SELBERG ZETA FUNCTION OF A TREE LATTICE
- The phase transition in inhomogeneous random graphs
Cited in
(only showing first 100 items - show all)- A spectral clustering-based framework for detecting community structures in complex networks
- Fast community detection by SCORE
- Network cross-validation for determining the number of communities in network data
- An impossibility result for reconstruction in the degree-corrected stochastic block model
- Fundamentals of spreading processes in single and multilayer complex networks
- Exact computational solution of modularity density maximization by effective column generation
- Clustering sparse binary data with hierarchical Bayesian Bernoulli mixture model
- On the exponential generating function for non-backtracking walks
- Random walks and diffusion on networks
- Estimating a network from multiple noisy realizations
- On the -nonbacktracking centrality for complex networks: existence and limit cases
- Notes on computational-to-statistical gaps: predictions using statistical physics
- Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
- Efficient modularity density heuristics for large graphs
- Edge reconstruction of the Ihara zeta function
- Some spectral properties of the non-backtracking matrix of a graph
- Convex relaxation methods for community detection
- Phase transition in spectral clustering based on resistance matrix
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- The Bethe Hessian and information theoretic approaches for online change-point detection in network data
- Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
- On the Fourier transform of a quantitative trait: implications for compressive sensing
- On equivalence of likelihood maximization of stochastic block model and constrained nonnegative matrix factorization
- Epidemic spreading dynamics on complex networks with adaptive social-support
- Local law and Tracy-Widom limit for sparse stochastic block models
- Rate optimal Chernoff bound and application to community detection in the stochastic block models
- An individual-based modeling framework for infectious disease spreading in clustered complex networks
- Self-awareness-based resource allocation strategy for containment of epidemic spreading
- Entrywise eigenvector analysis of random matrices with low expected rank
- Step-by-step community detection in volume-regular graphs
- Non-backtracking PageRank: from the classic model to Hashimoto matrices
- Spectral radii of sparse random matrices
- Percolation on complex networks: theory and application
- Community detection based on first passage probabilities
- Precisely identifying the epidemic thresholds in real networks via asynchronous updating
- Approximate normalized cuts without eigen-decomposition
- Approximate Moore graphs are good expanders
- Non-backtracking PageRank
- Consistency of spectral clustering in stochastic block models
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Convexified modularity maximization for degree-corrected stochastic block models
- A new weighted Ihara zeta function for a graph
- Targeted influence maximization in complex networks
- Non-backtracking spectra of weighted inhomogeneous random graphs
- Phase transitions in semidefinite relaxations
- Spectral clustering for community detection
- Approximating spectral clustering via sampling: a review
- Evaluating accuracy of community detection using the relative normalized mutual information
- Centrality metrics and localization in core-periphery networks
- Localized eigenvectors of the non-backtracking matrix
- A divisive spectral method for network community detection
- Correlation enhanced modularity-based belief propagation method for community detection in networks
- Ornstein-Uhlenbeck diffusion of Hermitian and non-Hermitian matrices -- unexpected links
- Spectral bounds for the Ising ferromagnet on an arbitrary given graph
- Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
- Disentangling group and link persistence in dynamic stochastic block models
- Core influence mechanism on vertex-cover problem through leaf-removal-core breaking
- Markov spectral clustering algorithm with DCBM for community detection
- Spectral clustering algorithms for the detection of clusters in block-cyclic and block-acyclic graphs
- Community detection and stochastic block models: recent developments
- Improved spectral community detection in large heterogeneous networks
- Statistical inference on random dot product graphs: a survey
- Sparse general Wigner-type matrices: local law and eigenvector delocalization
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Non-backtracking spectrum of degree-corrected stochastic block models
- Controlling epidemic outbreak based on local dynamic infectiousness on complex networks
- Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
- A testing based extraction algorithm for identifying significant communities in networks
- Weighted community detection and data clustering using message passing
- Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
- Generalized nonbacktracking bounds on the influence
- Optimal bipartite network clustering
- Recovering structured probability matrices
- Nonbacktracking eigenvalues under node removal: X-centrality and targeted immunization
- The Lovász theta function for random regular graphs and community detection in the hard regime
- A Theory for Backtrack-Downweighted Walks
- scientific article; zbMATH DE number 7378741 (Why is no real title available?)
- The why, how, and when of representations for complex systems
- Eigenvalues of the non-backtracking operator detached from the bulk
- Graph powering and spectral robustness
- Ergodicity Coefficients for Higher-Order Stochastic Processes
- Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
- scientific article; zbMATH DE number 7626732 (Why is no real title available?)
- Disordered systems insights on computational hardness
- Iterative Collaborative Filtering for Sparse Matrix Estimation
- Disentangling bipartite and core-periphery structure in financial networks
- Find Your Place: Simple Distributed Algorithms for Community Detection
- Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
- Nonparametric modeling of higher-order interactions via hypergraphons
- Beyond non-backtracking: non-cycling network centrality measures
- Heterogeneous node responses to multi-type epidemics on networks
- Non-backtracking alternating walks
- The Lovász theta function for random regular graphs and community detection in the hard regime
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- Network centrality: an introduction
- The Spacey Random Walk: A Stochastic Process for Higher-Order Data
- Mean-field theory of graph neural networks in graph partitioning
- Fragmenting complex network based on non-backtracking matrix
- Spectral theory of sparse non-Hermitian random matrices
- Voter model on networks partitioned into two cliques of arbitrary sizes
This page was built for publication: Spectral redemption in clustering sparse networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2962184)
