Entrywise bounds for eigenvectors of random graphs
Summary: Let \(G\) be a graph randomly selected from \({\mathbf G}_{n,p}\), the space of Erdős-Rényi random graphs with parameters \(n\) an d\(p\), where \(p\geq \frac{\log^6n}{n}\). Also, let \(A\) be the adjacency matrix of \(G\), and \(v_1\) be the first eigenvector of \(A\). We provide two short proofs of the following statement: For all \(i\in[n]\), for some constant \(c>0\), \[ \bigg|v_1(i)- \frac{1}{\sqrt{n}}\bigg|\leq \frac{1}{\sqrt{n}} \frac{\log n}{\log(np)} \sqrt{ \frac{\log n}{np}} \] with probability \(1-o(1)\). This gives nearly optimal bounds on the entrywise stability of the first eigenvector of (Erdős-Rényi) random graphs. This question about entrywise bounds was motivated by a problem in unsupervised spectral clustering. We make some progress towards solving that problem.
- Vertices cannot be hidden from quantum spatial search for almost all random graphs
- Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
- Tail bounds for gaps between eigenvalues of sparse random matrices
- Concentration of the spectral norm of Erdős-Rényi random graphs
- On the cycle space of a random graph
- Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
- Eigenvector delocalization for non‐Hermitian random matrices and applications
- The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
- Concentration of hitting times in Erdős-Rényi graphs
- On \(r\)-to-\(p\) norms of random matrices with nonnegative entries: asymptotic normality and \(\ell_{\infty}\)-bounds for the maximizer
- Hitting times in the binomial random graph
- Eigenvectors of random matrices: A survey
This page was built for publication: Entrywise bounds for eigenvectors of random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380297)
