The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
The average distances in random graphs with given expected degrees
Open accessAbstract
Random graph theory is used to examine the “small-world phenomenon”; any two strangers are connected through a short chain of mutual acquaintances. We will show that for certain families of random graphs with given expected degrees the average distance is almost surely of order log n/log d̃,where d̃is the weighted average of the sum of squares of the expected degrees. Of particular interest are power law random graphs in which the number of vertices of degree k is proportional to 1/k βfor some fixed exponent β. For the case of β > 3, we prove that the average distance of the power law graphs is almost surely of order log n/log d̃.However, many Internet, social, and citation networks are power law graphs with exponents in the range 2 < β < 3 for which the power law random graphs have average distance almost surely of order log log n,but have diameter of order log n(provided having some mild constraints for the average distance and maximum degree). In particular, these graphs contain a dense subgraph, which we call the core, having nc/log log nvertices. Almost all vertices are within distance log log n of the core although there are vertices at distance log n from the core.
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
Erdős, P., & Rényi, A. (2022) · Publicationes Mathematicae Debrecen · doi:10.5486/pmd.1959.6.3-4.12 · Cited by 5,337
The 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
The small-world problem: (400002009-005)
Milgram, S. (1967) · PsycEXTRA Dataset · doi:10.1037/e400002009-005 · Cited by 4,790
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
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
Random graphs with arbitrary degree distributions and their applications
Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2001) · Physical Review E · doi:10.1103/physreve.64.026118 · Cited by 3,648
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., & Wiener, J. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00083-9 · Cited by 2,810
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
A critical point for random graphs with a given degree sequence
Molloy, M., & Reed, B. (1995) · Random Structures & Algorithms · doi:10.1002/rsa.3240060204 · Cited by 2,351
The frequency distribution of scientific productivity
Lotka, A. J. (1926) · Journal of the Washington Academy of Sciences · Cited by 2,246
Random graph models of social networks
Newman, M. E. J., Watts, D. J., & Strogatz, S. H. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.012582999 · Cited by 1,326
The Web as a Graph: Measurements, Models, and Methods
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. S. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48686-0_1 · Cited by 1,016
Connected Components in Random Graphs with Given Expected Degree Sequences
Chung, F., & Lu, L. (2002) · Annals of Combinatorics · doi:10.1007/pl00012580 · Cited by 938
Self-citationThe Size of the Giant Component of a Random Graph with a Given Degree Sequence
MOLLOY, M., & REED, B. (1998) · Combinatorics, Probability and Computing · doi:10.1017/s0963548398003526 · Cited by 831
Modeling the Internet's large-scale topology
Yook, S.-H., Jeong, H., & Barabási, A.-L. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.172501399 · Cited by 665
Ghio, P. (1908) · Marcel Rivière eBooks · Cited by 437
A Random Graph Model for Power Law Graphs
Aiello, W., Chung, F., & Lu, L. (2001) · Experimental Mathematics · doi:10.1080/10586458.2001.10504428 · Cited by 405
Self-citationThe Diameter of Sparse Random Graphs
Chung, F., & Lu, L. (2001) · Advances in Applied Mathematics · doi:10.1006/aama.2001.0720 · Cited by 269
Self-citationRandom Evolution in Massive Graphs
Aiello, W., Chung, F., & Lu, L. (2002) · Massive Computing · doi:10.1007/978-1-4615-0005-6_4 · Cited by 169
Self-citationRandom Graphs with Arbitrary Degree Distribution and Their ApplicationsPreprint
Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2000) · RePEc: Research Papers in Economics · Cited by 42
(1949) · Max Planck Digital Library
Cited by
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Network biology: understanding the cell's functional organization
Barabási, A.-L., & Oltvai, Z. N. (2004) · Nature Reviews Genetics · doi:10.1038/nrg1272 · Cited by 7,903
“Although the small-world effect is a property of random networks, scale-free networks are ultra smal”
BackgroundHan (2023) · doi:10.1109/tpami.2022.3152247 · Cited by 4,682
Characterization of complex networks: A survey of measurements
Costa, L. D. F., Rodrigues, F. A., Travieso, G., & Villas Boas, P. R. (2007) · Advances in Physics · doi:10.1080/00018730601170527 · Cited by 2,475
Graph evolution: Densification and shrinking diameters
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217301 · Cited by 2,461
Metadata
- Authors
- Chung, F., & Lu, L.
- Venue
- Proceedings of the National Academy of Sciences
- Published
- 2002-12-04
- Volume
- 99
- Issue
- 25
- Pages
- 15879-15882
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- OpenAlex
- W2027377866
- Cited by
- 885
- References
- 23
- FWCI
- 11.28
- 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.