×

zbMATH — the first resource for mathematics

Eigenvalues of random power law graphs. (English) Zbl 1017.05093
Summary: Many graphs arising in various information networks exhibit the “power law” behavior – the number of vertices of degree \(k\) is proportional to \(k^{-\beta}\) for some positive \(\beta\). We show that if \(\beta>2.5\), the largest eigenvalue of a random power law graph is almost surely \((1+o(1))\sqrt{m}\) where \(m\) is the maximum degree. Moreover, the \(k\) largest eigenvalues of a random power law graph with exponent \(\beta\) have power law distribution with exponent \(2\beta-1\) if the maximum degree is sufficiently large, where \(k\) is a function depending on \(\beta\), \(m\) and \(d\), the average degree. When \(2<\beta< 2.5\), the largest eigenvalue is heavily concentrated at \(cm^{3-\beta}\) for some constant \(c\) depending on \(\beta\) and the average degree. This result follows from a more general theorem which shows that the largest eigenvalue of a random graph with a given expected degree sequence is determined by \(m\) and the weighted average of the squares of the expected degrees. We show that the \(k\)th largest eigenvalue is almost surely \((1+o(1))\sqrt{m_k}\) where \(m_k\) is the \(k\)th largest expected degree provided \(m_k\) is large enough. These results have implications on the usage of spectral techniques in many areas related to pattern detection and information retrieval.

MSC:
05C80 Random graphs (graph-theoretic aspects)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX Cite
Full Text: DOI