Spectra of random graphs with given expected degrees. Export

@article{citeulike:123, abstract = {In the study of the spectra of power-law graphs, there are basically two competing approaches. One is to prove analogues of Wigner's semicircle law, whereas the other predicts that the eigenvalues follow a power-law distribution. Although the semicircle law and the power law have nothing in common, we will show that both approaches are essentially correct if one considers the appropriate matrices. We will prove that (under certain mild conditions) the eigenvalues of the (normalized) Laplacian of a random power-law graph follow the semicircle law, whereas the spectrum of the adjacency matrix of a power-law graph obeys the power law. Our results are based on the analysis of random graphs with given expected degrees and their relations to several key invariants. Of interest are a number of (new) values for the exponent beta, where phase transitions for eigenvalue distributions occur. The spectrum distributions have direct implications to numerous graph algorithms such as, for example, randomized algorithms that involve rapidly mixing Markov chains.}, address = {Department of Mathematics, University of California at San Diego, La Jolla 92093-0112, USA. fan@ucsd.edu}, author = {Chung, F. and Lu, L. and Vu, V.}, citeulike-article-id = {123}, citeulike-linkout-0 = {http://dx.doi.org/10.1073/pnas.0937490100}, citeulike-linkout-1 = {http://www.pnas.org/content/100/11/6313.abstract}, citeulike-linkout-2 = {http://www.pnas.org/content/100/11/6313.full.pdf}, citeulike-linkout-3 = {http://www.pnas.org/cgi/content/abstract/100/11/6313}, citeulike-linkout-4 = {http://view.ncbi.nlm.nih.gov/pubmed/12743375}, citeulike-linkout-5 = {http://www.hubmed.org/display.cgi?uids=12743375}, day = {27}, doi = {10.1073/pnas.0937490100}, issn = {0027-8424}, journal = {Proc Natl Acad Sci U S A}, keywords = {graph, spectral}, month = {May}, number = {11}, pages = {6313--6318}, posted-at = {2006-10-06 21:56:36}, priority = {3}, title = {Spectra of random graphs with given expected degrees.}, url = {http://dx.doi.org/10.1073/pnas.0937490100}, volume = {100}, year = {2003} }

TY - JOUR ID - citeulike:123 L3 - citeulike-article-id:123 N2 - In the study of the spectra of power-law graphs, there are basically two competing approaches. One is to prove analogues of Wigner's semicircle law, whereas the other predicts that the eigenvalues follow a power-law distribution. Although the semicircle law and the power law have nothing in common, we will show that both approaches are essentially correct if one considers the appropriate matrices. We will prove that (under certain mild conditions) the eigenvalues of the (normalized) Laplacian of a random power-law graph follow the semicircle law, whereas the spectrum of the adjacency matrix of a power-law graph obeys the power law. Our results are based on the analysis of random graphs with given expected degrees and their relations to several key invariants. Of interest are a number of (new) values for the exponent beta, where phase transitions for eigenvalue distributions occur. The spectrum distributions have direct implications to numerous graph algorithms such as, for example, randomized algorithms that involve rapidly mixing Markov chains. IS - 11 JF - Proc Natl Acad Sci U S A SN - 0027-8424 AD - Department of Mathematics, University of California at San Diego, La Jolla 92093-0112, USA. fan@ucsd.edu EP - 6318 TI - Spectra of random graphs with given expected degrees. VL - 100 SP - 6313 KW - graph KW - spectral AU - Chung, F AU - Lu, L AU - Vu, V PY - 2003/05/27/ UR - http://dx.doi.org/10.1073/pnas.0937490100 ER -