# 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.)
##### Keywords:
random graphs; power law; eigenvalues
Full Text: