Eigenvalues of Random Power law Graphs

Fan Chung, Linyuan Lu, and Van Vu

Department of Mathematics, University of California, San Diego, La Jolla, CA 92093, USA

{fan, vanvu}@ucsd.edu, llu@math.ucsd.edu

Annals of Combinatorics 7 (1) p.21-33 March, 2003

Abstract:

Many graphs arising
in various information networks exhibit the ``power law'' behavior --- the number
of vertices of degree k is proportional to
for some positive . We show that
if , the largest eigenvalue of
a random power law graph is almost surely
where m is the maximum degree. Moreover, the k largest eigenvalues of a random
power law graph with exponent
have power law distribution with exponent 2-1
if the maximum degree is sufficiently large, where k is a function depending
on , m and d, the average degree.
When 2 < < 2.5, the largest eigenvalue
is heavily concentrated at 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, the weighted average of the squares
of the expected degrees. We show that the k-th largest eigenvalue is almost
surely where
is the k-th largest expected degree provided
is large enough. These results have implications on the usage of spectral techniques
in many areas related to pattern detection and information retrieval.

References:

1. W. Aiello, F. Chung, and L. Lu, A random graph model for massive graphs, STOC 2001, pp. 171–180, Experiment. Math. 10 (2001) 53–66.

2. W. Aiello, F. Chung, and L. Lu, Random evolution in massive graphs, In: Handbook of Massive Data Sets, Vol. 2, J. Abello et al. Eds., Kluwer Academic Publishers, 2002, pp. 97–122. Extended abstract appeared in FOCS 2001, pp. 510–519.

3. R. Albert, H. Jeong, and A. Barabási, Diameter of the world wide web, Nature 401 (1999) 130–131.

4. A. Barabási and R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509–512.

5. F. Chung and L. Lu, Connected components in random graphs with given expected degree sequences, Ann. Combin. 6 (2002) 125–145.

6. P. Erdős and T. Gallai, Gráfok előirt fokú pontokkal (Graphs with points of prescribed degrees, in Hungarian), Mat. Lapok 11 (1961) 264–274.

7. P. Erdős and A. Rényi, On random graphs I, Publ. Math. Debrecen 6 (1959) 290–297.

8. M. Faloutsos, P. Faloutsos, and C. Faloutsos, On power-law relationships of the internet topology, ACM SIG-COMM'99, Comput. Commun. Rev. 29 (1999) 251–263.

9. I.J. Farkas, I. Derényi, A.-L. Barabási, and T. Vicsek, Spectra of “Real-World” graphs: beyond the semi-circle law, cond-mat/0102335.

10. C. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001.

11. K.-I. Goh, B. Kahng, and D. Kim, Spectra and eigenvectors of scale-free networks, condmat/ 0103337.

12. M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, Eds., Probabilistic Methods for Algorithmic Discrete Mathematics, Algorithms and Combinatorics, 16, Springer-Verlag, Berlin, 1998, pp. 195–248.

13. H. Jeong, B. Tomber, R. Albert, Z. Oltvai, and A. L. Barábasi, The large-scale organization of metabolic networks, Nature 407 (2000) 378–382.

14. J. Kleinberg, S. R. Kumar, P. Raphavan, S. Rajagopalan, and A. Tomkins, The web as a graph: measurements, models and methods, Proceedings of the International Conference on Combinatorics and Computing, 1999.

15. L. Lu, The diameter of random massive graphs, In: Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms, 2001, pp. 912–921.

16. M. Mihail and C. Papadimitriou, On the eigenvalue power law, preprint.

17. O. Perron, Theorie der algebraischen Gleichungen, II (zweite Auflage), de Gruyter, Berlin, 1933.