Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges

Keywords

Adjacency matrix, Combinatorics, Mathematics, Adjacency list, Laplacian matrix

References

• Probability on Banach spacesBeck, Anatole — 1978
• Random Graphs: NotationBéla Bollobás — 2001
• The Spectral Gap of Random Graphs with Given Expected DegreesAmin Coja‐Oghlan, André Lanka — 2006
• The concentration of measure phenomenonMichel Ledoux — 2001
• Perturbation theory for linear operatorsTosio Kato — 1966
• Spectral Graph TheoryFan Chung — 1996
• Random Cayley Graphs are Expanders: a Simple Proof of the Alon-Roichman TheoremZeph Landau, Alexander Russell — 2004
• A proof of Alon's second eigenvalue conjecture and related problemsJoel Friedman — 2004
• Percolation on finite graphs and isoperimetric inequalitiesNoga Alon, Itai Benjamini, Alan Stacey — 2002
• Random Vectors in the Isotropic PositionMark Rudelson — 1996
• The Spectra of Random Graphs with Given Expected DegreesFan Chung, Linyuan Lü, Van Vu — 2004
• Random Graph Coverings I: General Theory and Graph ConnectivityAlon Amit, Nathan Linial — 2002
• The two possible values of the chromatic number of a random graphDimitris Achlioptas, Assaf Naor — 2004
• ‘‘Extrinsic’’ and ‘‘Intrinsic’’ Data in Quantum Measurements: Asymptotic Convex Decomposition of Positive Operator Valued MeasuresAndreas Winter — 2001
• The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz InequalityPascal Massart — 1990
• The Largest Eigenvalue of Sparse Random GraphsMichael Krivelevich, Benny Sudakov — 2001
• Relating quantum privacy and quantum coherence: an operational approach.Igor Devetak, Andreas Winter — 2003
• Sharp concentration of the chromatic number on random graphsGn, pEli Shamir, Joel Spencer — 1987
• Quasi-random graphsFan Chung, Ron Graham, R. Wilson — 1988
• Relative expanders or weakly relatively Ramanujan graphsJoel Friedman — 2003

Cited by

• Optimal Data Collection for Improved Rankings Expose Well-Connected GraphsBraxton Osting, Christoph Brüne, Stanley Osher — 2012
• User-Friendly Tools for Random Matrices: An IntroductionJoel A. Tropp — 2012
• Concentration and regularization of random graphsCan M. Le, Elizaveta Levina, Roman Vershynin — 2015
• Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition ModelKamalika Chaudhuri, Fan Chung, Alexander Tsiatas — 2012
• Out-of-sample Extension for Latent Position GraphsMinh Tang, Youngser Park, Carey E. Priebe — 2013
• On Some Extensions of Bernstein's Inequality for Self-adjoint OperatorsStanislav Minsker — 2011
• Dimension-free tail inequalities for sums of random matricesDaniel Hsu, Sham M. Kakade, Tong Zhang — 2011
• Deriving Matrix Concentration Inequalities from Kernel CouplingsDaniel Paulin, Lester Mackey, Joel A. Tropp — 2013
• Invertibility of random submatrices via tail decoupling and a Matrix Chernoff InequalityStéphane Chrétien, Sébastien Darses — 2011
• A Limit Theorem for Scaled Eigenvectors of Random Dot Product GraphsA. Manoj Athreya, Carey E. Priebe, Minh Tang — 2013
• On the Spectra of General Random GraphsFan Chung, Mary Radcliffe — 2011
• Kolmogorov’s law of the iterated logarithm for noncommutative martingalesQiang Zeng — 2012
• Role of normalization in spectral clustering for stochastic blockmodelsPurnamrita Sarkar, Peter J. Bickel — 2013
• Universally Consistent Latent Position Estimation and Vertex Classification for Random Dot Product GraphsDaniel L. Sussman, Minh Tang, Carey E. Priebe — 2012
• TAIL BOUNDS FOR ALL EIGENVALUES OF A SUM OF RANDOM MATRICESAlex Gittens, Joel A. Tropp — 2011
• Sparse random graphs: regularization and concentration of the LaplacianCan M. Le, Elizaveta Levina, Roman Vershynin — 2015
• Concentration of the Stationary Distribution on General Random Directed GraphsFranklin Kenter — 2013
• A central limit theorem for scaled eigenvectors of random dot product graphsAvanti Athreya, Vince Lyzinski, David J. Marchette — 2013
• The Masked Sample Covariance Estimator: An Analysis via the Matrix Laplace TransformRichard Y. Chen, Alex Gittens, Joel A. Tropp — 2012
• Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational IssuesNihar B. Shah, Sivaraman Balakrishnan, Adityanand Guntuboyina — 2015

Related papers

• Adjacency Maps and Efficient Graph AlgorithmsGabriel Valiente — 2022
• Research of the genetic-clustering algorithm considering the condition of planar adjacency relationshipShe Xiang-yang — 2005
• Compressed Adjacency Matrices: Untangling Gene Regulatory NetworksKasper Dinkla, Michel A. Westenberg, Jarke J. van Wijk — 2012
• A general method for finding principal resonance structures for conjugated systems by semi-random searching of an adjacency matrixE. C. Kirby — 1985
• DIRECTED GRAPHS AND THEIR ADJACENCY MATRICES: MISCONCEPTIONS AND MORE EFFICIENT METHODSRichard Frost — 1992
• Do chemical graphs have a natural order? some regularities of a “compacted maximal adjacency code”E. C. Kirby — 1989
• Consensus-Based Distributed Connectivity Control in Multi-Agent SystemsKarlo Griparić, Marsela Polić, Marko Križmančić — 2022