Spectral Gap of Random Hyperbolic Graphs and Related Parameters

摘要: Random hyperbolic graphs have been suggested as a promising model of social networks. A few their fundamental parameters studied. However, none them concerns spectra. We consider the random graph formalized by [GPP12] and essentially determine spectral gap normalized Laplacian. Specifically, we establish that with high probability second smallest eigenvalue Laplacian giant component $n$-vertex is $\Omega(n^{-(2\alpha-1)}/D)$, where $\frac12<\alpha<1$ parameter $D$ network diameter (which known to be at most polylogarithmic in $n$). also show matching (up factor) upper bound $n^{-(2\alpha-1)}(\log n)^{1+o(1)}$. As byproduct conclude conductance on obtained via Cheeger's inequality tight. provide more detailed picture collection vertices which attained, particular showing for all subsets whose volume $O(n^{1-\varepsilon})$ $\Omega(n^{-(2\alpha-1)\varepsilon+o(1)})$. Finally, consequences our result minimum maximum bisection component.