Spectral techniques applied to sparse random graphs
From MaRDI portal
Publication:5318249
DOI10.1002/rsa.20089zbMath1076.05073OpenAlexW4243880374WikidataQ105583242 ScholiaQ105583242MaRDI QIDQ5318249
Publication date: 22 September 2005
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20089
Random graphs (graph-theoretic aspects) (05C80) Semidefinite programming (90C22) Combinatorial probability (60C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Universality of the mean-field for the Potts model, Large Rainbow Cliques in Randomly Perturbed Dense Graphs, Vertices cannot be hidden from quantum spatial search for almost all random graphs, On the spectrum of dense random geometric graphs, Functional limit theorems for random regular graphs, Message passing algorithms for MLS-3LIN problem, Optimal and algorithmic norm regularization of random matrices, Norms of random matrices: local and global problems, Spectra of edge-independent random graphs, The spectra of random mixed graphs, Outliers in spectrum of sparse Wigner matrices, On an anti-Ramsey threshold for random graphs, Finding one community in a sparse graph, On the efficacy of higher-order spectral clustering under weighted stochastic block models, Mean-Field Approximations for Stochastic Population Processes with Heterogeneous Interactions, Detection thresholds in very sparse matrix completion, Algebraic and combinatorial expansion in random simplicial complexes, Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs, Fluctuations in mean-field Ising models, Faster least squares approximation, Unnamed Item, Detecting structured signals in Ising models, Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models, The skew spectral radius and skew Randić spectral radius of general random oriented graphs, On the second eigenvalue of random bipartite biregular graphs, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, A Simple SVD Algorithm for Finding Hidden Partitions, Spectral norm bounds for block Markov chain random matrices, Non-backtracking spectra of weighted inhomogeneous random graphs, Spectral algorithms for unique games, Recovering Structured Probability Matrices, On the spectra of general random mixed graphs, Sampling based succinct matrix approximation, Spectral radii of sparse random matrices, Spectral clustering in the dynamic stochastic block model, Sparse random graphs: Eigenvalues and eigenvectors, Graph Partitioning via Adaptive Spectral Techniques, On eigenvalues of random complexes, On semidefinite relaxations for the block model, Size biased couplings and the spectral gap for random regular graphs, Community Detection and Stochastic Block Models, Clustering in block Markov chains, Sparse regular random graphs: spectral density and eigenvectors, The Hopfield model on a sparse Erdös-Renyi graph, Why almost all \(k\)-colorable graphs are easy to color, On the Laplacian Eigenvalues of Gn,p, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT, Spectral Compressed Sensing via Projected Gradient Descent, Convex relaxation methods for community detection, Extremal eigenvalues of critical Erdős-Rényi graphs, Spectral edge in sparse random graphs: upper and lower tail large deviations, Capacity of an associative memory model on random graph architectures, Community detection in sparse networks via Grothendieck's inequality, Analysis of crowdsourced sampling strategies for HodgeRank with sparse random graphs, Sparse random tensors: concentration, regularization and applications, Expansion and Lack Thereof in Randomly Perturbed Graphs, Sherali-adams strikes back, A spectral method for community detection in moderately sparse degree-corrected stochastic block models, The theta number of simplicial complexes, Constructive regularization of the random matrix norm, An \({\ell_p}\) theory of PCA and spectral clustering, Unnamed Item, Consistency of spectral clustering in stochastic block models, Unnamed Item, Swarming on random graphs. II, Recognizing more random unsatisfiable 3-SAT instances efficiently, Distributed user profiling via spectral methods, Loose laplacian spectra of random hypergraphs, Role of normalization in spectral clustering for stochastic blockmodels
Uses Software
Cites Work
