Eigenvalues of Random Power law Graphs

Many graphs arising in various information networks exhibit the "power law" behavior -the number of vertices of degree k is proportional to k^-# for some positive #. We show that if # > 2.5, the largest eigenvalue of a random power law graph is almost surely(1+ o(1))?m (1+ o(1))\sqrt{m} where m is the maximum degree. Moreover, the klargest eigenvalues of a random power law graph with exponent # have power law distribution with exponent 2# if the maximum degree is sufficiently large, where k is a function depending on #, mand d, the average degree. When 2<#< 2.5, the largest eigenvalue is heavily concentrated at cm^3-# for some constant c depending on # 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, the maximum degree, and (d)\tilde] \tilde{d} , the weighted average of the squares of the expected degrees. We show that the k-th largest eigenvalue is almost surely (1+ o(1))?{m_k} (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.