Spectral redemption in clustering sparse networks

DOI10.1073/pnas.1312486110zbMath1359.62252arXiv1306.5550OpenAlexW2024514015WikidataQ37421201 ScholiaQ37421201MaRDI QIDQ2962184

Lenka Zdeborová, Pan Zhang, Allan Sly, Moore, Cristopher, Florent Krzakala, Elchanan Mossel, Joe Neeman

Publication date: 16 February 2017

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.5550

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Stochastic network models in operations research (90B15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Detection theory in information and communication theory (94A13) Information theory (general) (94A15)

Related Items

The Bethe Hessian and information theoretic approaches for online change-point detection in network data, An impossibility result for reconstruction in the degree-corrected stochastic block model, Hierarchical Community Detection by Recursive Partitioning, Ergodicity Coefficients for Higher-Order Stochastic Processes, Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM), 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, Fundamentals of spreading processes in single and multilayer complex networks, Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information, Optimal Bipartite Network Clustering, Disordered systems insights on computational hardness, Iterative Collaborative Filtering for Sparse Matrix Estimation, On equivalence of likelihood maximization of stochastic block model and constrained nonnegative matrix factorization, Exact computational solution of modularity density maximization by effective column generation, Epidemic spreading dynamics on complex networks with adaptive social-support, Unnamed Item, Clustering sparse binary data with hierarchical Bayesian Bernoulli mixture model, A spectral algorithm with additive clustering for the recovery of overlapping communities in networks, On the exponential generating function for non-backtracking walks, 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, Convexified modularity maximization for degree-corrected stochastic block models, An individual-based modeling framework for infectious disease spreading in clustered complex networks, Find Your Place: Simple Distributed Algorithms for Community Detection, A new weighted Ihara zeta function for a graph, Random walks and diffusion on networks, Finding one community in a sparse graph, Self-awareness-based resource allocation strategy for containment of epidemic spreading, Entrywise eigenvector analysis of random matrices with low expected rank, Phase transitions in semidefinite relaxations, Targeted influence maximization in complex networks, Unnamed Item, Non-backtracking spectra of weighted inhomogeneous random graphs, Step-by-step community detection in volume-regular graphs, Estimating a network from multiple noisy realizations, On the \(\alpha\)-nonbacktracking centrality for complex networks: existence and limit cases, Non-backtracking PageRank: from the classic model to Hashimoto matrices, Network Centrality: An Introduction, Recovering Structured Probability Matrices, Sparse general Wigner-type matrices: Local law and eigenvector delocalization, Notes on computational-to-statistical gaps: predictions using statistical physics, Spectral radii of sparse random matrices, Approximating Spectral Clustering via Sampling: A Review, A testing based extraction algorithm for identifying significant communities in networks, The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, Percolation on complex networks: theory and application, Evaluating accuracy of community detection using the relative normalized mutual information, Community detection based on first passage probabilities, 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, Controlling epidemic outbreak based on local dynamic infectiousness on complex networks, Disentangling bipartite and core-periphery structure in financial networks, Unnamed Item, Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs, Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs, Beyond non-backtracking: non-cycling network centrality measures, Heterogeneous node responses to multi-type epidemics on networks, Efficient modularity density heuristics for large graphs, Edge reconstruction of the Ihara zeta function, Community Detection and Stochastic Block Models, Statistical inference on random dot product graphs: a survey, The Spacey Random Walk: A Stochastic Process for Higher-Order Data, Estimating the number of communities by spectral methods, Some spectral properties of the non-backtracking matrix of a graph, Unnamed Item, Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log^*|V|) time, Precisely identifying the epidemic thresholds in real networks via asynchronous updating, Approximate normalized cuts without eigen-decomposition, A goodness-of-fit test for stochastic block models, Approximate Moore graphs are good expanders, Convex relaxation methods for community detection, Fast community detection by SCORE, Weighted community detection and data clustering using message passing, Network Cross-Validation for Determining the Number of Communities in Network Data, 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, Analysis of spectral clustering algorithms for community detection: the general bipartite setting, Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models, Nonbacktracking Eigenvalues under Node Removal: X-Centrality and Targeted Immunization, Non-backtracking PageRank, Mean-field theory of graph neural networks in graph partitioning, A Theory for Backtrack-Downweighted Walks, Consistency of spectral clustering in stochastic block models, The Why, How, and When of Representations for Complex Systems, Fragmenting complex network based on non-backtracking matrix, Unnamed Item, Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, Eigenvalues of the non-backtracking operator detached from the bulk, Spectral theory of sparse non-Hermitian random matrices, Voter model on networks partitioned into two cliques of arbitrary sizes, Robust and computationally feasible community detection in the presence of arbitrary outlier nodes, Graph Powering and Spectral Robustness, Community informed experimental design, A literature survey of matrix methods for data science, Subsampling spectral clustering for stochastic block models in large-scale networks, Detection thresholds in very sparse matrix completion, Community detection in the sparse hypergraph stochastic block model, Community modulated recursive trees and population dependent branching processes, Kemeny's constant for nonbacktracking random walks, There is no going back: properties of the non-backtracking Laplacian, Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs, Combinatorial statistics and the sciences, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, Two typical analytic models for reverse bond percolation on real networks, Asymptotic uncertainty quantification for communities in sparse planted bi-section models, Learning sparse graphons and the generalized Kesten-Stigum threshold, Spectral theory of the non-backtracking Laplacian for graphs, Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks, Discovering the hidden community structure of public transportation networks, EVENT GRAPHS: ADVANCES AND APPLICATIONS OF SECOND-ORDER TIME-UNFOLDED TEMPORAL NETWORK MODELS, The rank of sparse random matrices

Cites Work

• On the distribution of the roots of certain symmetric matrices
• The expected eigenvalue distribution of a large regular graph
• Information flow on trees
• A nonparametric view of network models and Newman–Girvan and other modularities
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Random matrices, nonbacktracking walks, and orthogonal polynomials
• A Spectral Approach to Analysing Belief Propagation for 3-Colouring
• Graph Partitioning via Adaptive Spectral Techniques
• Community structure in social and biological networks
• THE IHARA-SELBERG ZETA FUNCTION OF A TREE LATTICE
• The phase transition in inhomogeneous random graphs
• Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes