<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue1" %>
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
AMS Subject Classification: 05C80
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.
Keywords: random graphs, power law, eigenvalues

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.