The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Spectra of random graphs with given expected degrees
Open accessAbstract
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 β, 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
Self-citationThe Large-Scale Organization of Metabolic Networks
Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N., & Barabási, A.-L. (2000) · Nature · doi:10.1038/35036627 · Cited by 4,972
Diameter of the World-Wide Web
Albert, R., Jeong, H., & Barabási, A.-L. (1999) · Nature · doi:10.1038/43601 · Cited by 4,260
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/316188.316229 · Cited by 4,196
Biggs, N. (1974) · doi:10.1017/cbo9780511608704 · Cited by 2,940
On power-law relationships of the Internet topology
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999) · ACM SIGCOMM Computer Communication Review · doi:10.1145/316194.316229 · Cited by 2,613
Random-matrix theories in quantum physics: common concepts
Guhr, T., Müller–Groeling, A., & Weidenmüller, H. A. (1998) · Physics Reports · doi:10.1016/s0370-1573(97)00088-4 · Cited by 2,211
On the Distribution of the Roots of Certain Symmetric Matrices
Wigner, E. P. (1958) · The Annals of Mathematics · doi:10.2307/1970008 · Cited by 1,463
Cited by
Synchronization in complex networks
Arenas, A., Díaz-Guilera, A., Kurths, J., Moreno, Y., & Zhou, C. (2008) · Physics Reports · doi:10.1016/j.physrep.2008.09.002 · Cited by 3,713
Epidemic processes in complex networks
Pastor-Satorras, R., Castellano, C., Van Mieghem, P., & Vespignani, A. (2015) · Reviews of Modern Physics · doi:10.1103/revmodphys.87.925 · Cited by 3,697
The structure and dynamics of multilayer networks
Boccaletti, S., Bianconi, G., Criado, R., del Genio, C. I., Gómez-Gardeñes, J., Romance, M., Sendiña-Nadal, I., Wang, Z., & Zanin, M. (2014) · Physics Reports · doi:10.1016/j.physrep.2014.07.001 · Cited by 3,125
“For the RP corresponding to the SIS spreading process, instead, the largest eigenvalue must be calculated [236].”
MethodNewman, M. (2018) · doi:10.1093/oso/9780198805090.001.0001 · Cited by 2,297
Critical phenomena in complex networks
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1275 · Cited by 2,220
The Kuramoto model in complex networks
Rodrigues, F. A., Peron, T. K. D., Ji, P., & Kurths, J. (2016) · Physics Reports · doi:10.1016/j.physrep.2015.10.008 · Cited by 1,040
A Survey of Statistical Network Models
Goldenberg, A., Zheng, A. X., Fienberg, S. E., & Airoldi, E. M. (2010) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000005 · Cited by 819
Epidemic thresholds in real networks
Chakrabarti, D., Wang, Y., Wang, C., Leskovec, J., & Faloutsos, C. (2008) · ACM Transactions on Information and System Security · doi:10.1145/1284680.1284681 · Cited by 787
Thresholds for Epidemic Spreading in Networks
Castellano, C., & Pastor-Satorras, R. (2010) · Physical Review Letters · doi:10.1103/physrevlett.105.218701 · Cited by 721
Discrete-time Markov chain approach to contact-based disease spreading in complex networks
Gómez, S., Arenas, A., Borge-Holthoefer, J., Meloni, S., & Moreno, Y. (2010) · EPL (Europhysics Letters) · doi:10.1209/0295-5075/89/38009 · Cited by 571
Agreement over random networks
Hatano, Y., & Mesbahi, M. (2004) · 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601) · doi:10.1109/cdc.2004.1430343 · Cited by 550
Network synchronization, diffusion, and the paradox of heterogeneity
Motter, A. E., Zhou, C., & Kurths, J. (2005) · Physical Review E · doi:10.1103/physreve.71.016116 · Cited by 546
Random walks in peer-to-peer networks
Gkantsidis, C., Mihail, M., & Saberi, A. (2004) · IEEE INFOCOM 2004 · doi:10.1109/infcom.2004.1354487 · Cited by 525
Agreement over random networks
Hatano, Y., & Mesbahi, M. (2005) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2005.858670 · Cited by 503
Synchronization is Enhanced in Weighted Complex Networks
Chavez, M., Hwang, D.-U., Amann, A., Hentschel, H. G. E., & Boccaletti, S. (2005) · Physical Review Letters · doi:10.1103/physrevlett.94.218701 · Cited by 460
Concentration Inequalities and Martingale Inequalities: A Survey
Chung, F., & Lu, L. (2006) · Internet Mathematics · doi:10.1080/15427951.2006.10129115 · Cited by 427
Self-citationToward link predictability of complex networks
Lü, L., Pan, L., Zhou, T., Zhang, Y.-C., & Stanley, H. E. (2015) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1424644112 · Cited by 412
Anomaly detection in dynamic networks: a survey
Ranshous, S., Shen, S., Koutra, D., Harenberg, S., Faloutsos, C., & Samatova, N. F. (2015) · WIREs Computational Statistics · doi:10.1002/wics.1347 · Cited by 379
Unification of theoretical approaches for epidemic spreading on complex networks
Wang, W., Tang, M., Eugene Stanley, H., & Braunstein, L. A. (2017) · Reports on Progress in Physics · doi:10.1088/1361-6633/aa5398 · Cited by 366
Abrupt transition in the structural formation of interconnected networks
Radicchi, F., & Arenas, A. (2013) · Nature Physics · doi:10.1038/nphys2761 · Cited by 348
Localization and Spreading of Diseases in Complex Networks
Goltsev, A. V., Dorogovtsev, S. N., Oliveira, J. G., & Mendes, J. F. F. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.128702 · Cited by 347
Laplacian Dynamics and Multiscale Modular Structure in Networks
Lambiotte, R., Delvenne, J., & Barahona, M. (2008) · doi:10.48550/arxiv.0812.1770 · Cited by 345
Universality in the Synchronization of Weighted Random Networks
Zhou, C., Motter, A. E., & Kurths, J. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.034101 · Cited by 340
Enhancing complex-network synchronization
Motter, A. E., Zhou, C. S., & Kurths, J. (2005) · Europhysics Letters (EPL) · doi:10.1209/epl/i2004-10365-4 · Cited by 317
Onset of synchronization in large networks of coupled oscillators
Restrepo, J. G., Ott, E., & Hunt, B. R. (2005) · Physical Review E · doi:10.1103/physreve.71.036151 · Cited by 312
Localization and centrality in networks
Martin, T., Zhang, X., & Newman, M. E. J. (2014) · Physical Review E · doi:10.1103/physreve.90.052808 · Cited by 309
Nature of the Epidemic Threshold for the Susceptible-Infected-Susceptible Dynamics in Networks
Boguñá, M., Castellano, C., & Pastor-Satorras, R. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.068701 · Cited by 291
Coevolution spreading in complex networks
Wang, W., Liu, Q.-H., Liang, J., Hu, Y., & Zhou, T. (2019) · Physics Reports · doi:10.1016/j.physrep.2019.07.001 · Cited by 286
Ferreira, S. C., Castellano, C., & Pastor-Satorras, R. (2012) · Physical Review E · doi:10.1103/physreve.86.041125 · Cited by 284
Spectrum of controlling and observing complex networks
Yan, G., Tsekenis, G., Barzel, B., Slotine, J.-J., Liu, Y.-Y., & Barabási, A.-L. (2015) · Nature Physics · doi:10.1038/nphys3422 · Cited by 279
Pairwise Alignment of Protein Interaction Networks
Koyutürk, M., Kim, Y., Topkara, U., Subramaniam, S., Szpankowski, W., & Grama, A. (2006) · Journal of Computational Biology · doi:10.1089/cmb.2006.13.182 · Cited by 268
Characterizing the Dynamical Importance of Network Nodes and Links
Restrepo, J. G., Ott, E., & Hunt, B. R. (2006) · Physical Review Letters · doi:10.1103/physrevlett.97.094102 · Cited by 260
Spectral Measure of Structural Robustness in Complex Networks
Wu, J., Barahona, M., Tan, Y.-J., & Deng, H.-Z. (2011) · IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans · doi:10.1109/tsmca.2011.2116117 · Cited by 254
Metadata
- Authors
- Chung, F., Lu, L., & Vu, V.
- Venue
- Proceedings of the National Academy of Sciences
- Published
- 2003-05-12
- Volume
- 100
- Issue
- 11
- Pages
- 6313-6318
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- OpenAlex
- W1973836644
- Cited by
- 492
- References
- 23
- FWCI
- 11.05
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.