Entrywise Bounds for Eigenvectors of Random Graphs

Source abstract

Let $G$ be a graph randomly selected from ${\bf G}_{n, p}$, the space of Erdős-Rényi Random graphs with parameters $n$ and $p$, where $p \geq {\log^6 n\over 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$ $$\left|v_1(i) - {1\over\sqrt{n}}\right| \leq c {1\over\sqrt{n}} {\log n\over\log (np)} \sqrt{{\log n\over 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.