The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Random graphs with arbitrary degree distributions and their applications
Open accessAbstract
Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Handbook of Mathematical Functions
McQuarrie, D. A. (1966) · American Journal of Physics · doi:10.1119/1.1972842 · Cited by 40,433
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
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
Classes of small-world networks
Amaral, L. A. N., Scala, A., Barthélémy, M., & Stanley, H. E. (2000) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.200327197 · Cited by 3,051
Cited by
Statistical mechanics of complex networks
Albert, R., & Barabási, A.-L. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.47 · Cited by 20,471
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Self-citationCommunity structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502
Self-citationCatastrophic cascade of failures in interdependent networks
Buldyrev, S. V., Parshani, R., Paul, G., Stanley, H. E., & Havlin, S. (2010) · Nature · doi:10.1038/nature08932 · Cited by 4,513
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
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
Kivela, M., Arenas, A., Barthelemy, M., Gleeson, J. P., Moreno, Y., & Porter, M. A. (2014) · Journal of Complex Networks · doi:10.1093/comnet/cnu016 · Cited by 3,235
A simple model of global cascades on random networks
Watts, D. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.082090499 · Cited by 2,673
Self-citationBarthélemy, M. (2011) · Physics Reports · doi:10.1016/j.physrep.2010.11.002 · Cited by 2,469
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
Evolution of the social network of scientific collaborations
Barabási, A. L., Jeong, H., Néda, Z., Ravasz, E., Schubert, A., & Vicsek, T. (2002) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(02)00736-7 · Cited by 1,972
Cascade-based attacks on complex networks
Motter, A. E., & Lai, Y.-C. (2002) · Physical Review E · doi:10.1103/physreve.66.065102 · Cited by 1,929
Collaboration and Creativity: The Small World Problem
Uzzi, B., & Spiro, J. (2005) · American Journal of Sociology · doi:10.1086/432782 · Cited by 1,885
Uncovering disease-disease relationships through the incomplete interactome
Menche, J., Sharma, A., Kitsak, M., Ghiassian, S. D., Vidal, M., Loscalzo, J., & Barabási, A.-L. (2015) · Science · doi:10.1126/science.1257601 · Cited by 1,546
Self-similar community structure in a network of human interactions
Guimerà, R., Danon, L., Díaz-Guilera, A., Giralt, F., & Arenas, A. (2003) · Physical Review E · doi:10.1103/physreve.68.065103 · Cited by 1,515
Network ‘Small-World-Ness’: A Quantitative Method for Determining Canonical Network Equivalence
Humphries, M. D., & Gurney, K. (2008) · PLoS ONE · doi:10.1371/journal.pone.0002051 · Cited by 1,442
Contagion in financial networks
Gai, P., & Kapadia, S. (2010) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2009.0410 · Cited by 1,163
Effects of missing data in social networks
Kossinets, G. (2006) · Social Networks · doi:10.1016/j.socnet.2005.07.002 · Cited by 926
Structural Properties of the Caenorhabditis elegans Neuronal Network
Varshney, L. R., Chen, B. L., Paniagua, E., Hall, D. H., & Chklovskii, D. B. (2011) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1001066 · Cited by 867
Chains of affection: the structure of adolescent romantic and sexual networks
Bearman, P. S., Moody, J., & Stovel, K. (2004) · American Journal of Sociology · doi:10.1086/386272 · Cited by 817
Cascade Control and Defense in Complex Networks
Motter, A. E. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.098701 · Cited by 776
Graph analysis of the human connectome: Promise, progress, and pitfalls
Fornito, A., Zalesky, A., & Breakspear, M. (2013) · NeuroImage · doi:10.1016/j.neuroimage.2013.04.087 · Cited by 743
The Structure of a Social Science Collaboration Network: Disciplinary Cohesion from 1963 to 1999
Moody, J. (2004) · American Sociological Review · doi:10.1177/000312240406900204 · Cited by 738
Large-scale topological and dynamical properties of the Internet
Vázquez, A., Pastor-Satorras, R., & Vespignani, A. (2002) · Physical Review E · doi:10.1103/physreve.65.066130 · Cited by 712
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2002) · Physical Review E · doi:10.1103/physreve.65.066122 · Cited by 540
Mocanu, D. C., Mocanu, E., Stone, P., Nguyen, P. H., Gibescu, M., & Liotta, A. (2018) · Nature Communications · doi:10.1038/s41467-018-04316-3 · Cited by 524
Structure of Urban Movements: Polycentric Activity and Entangled Hierarchical Flows
Roth, C., Kang, S. M., Batty, M., & Barthélemy, M. (2011) · PLoS ONE · doi:10.1371/journal.pone.0015923 · Cited by 461
A tutorial in connectome analysis: Topological and spatial features of brain networks
Kaiser, M. (2011) · NeuroImage · doi:10.1016/j.neuroimage.2011.05.025 · Cited by 371
On the uniform generation of random graphs with prescribed degree sequences
Milo, R., Kashtan, N., Itzkovitz, S., Newman, M. E. J., & Alon, U. (2003) · arXiv · doi:10.48550/arxiv.cond-mat/0312028 · Cited by 281
Self-citationSeed size strongly affects cascades on random networks
Gleeson, J. P., & Cahalane, D. J. (2007) · Physical Review E · doi:10.1103/physreve.75.056103 · Cited by 273
Configuring Random Graph Models with Fixed Degree Sequences
Fosdick, B. K., Larremore, D. B., Nishimura, J., & Ugander, J. (2018) · SIAM Review · doi:10.1137/16m1087175 · Cited by 246
Comparing alliance network structure across industries: observations and explanations
Rosenkopf, L., & Schilling, M. A. (2007) · Strategic Entrepreneurship Journal · doi:10.1002/sej.33 · Cited by 222
Rigidity percolation uncovers a structural basis for embryonic tissue phase transitions
Petridou, N. I., Corominas-Murtra, B., Heisenberg, C.-P., & Hannezo, E. (2021) · Cell · doi:10.1016/j.cell.2021.02.017 · Cited by 222
Percolation of localized attack on complex networks
Shao, S., Huang, X., Stanley, H. E., & Havlin, S. (2015) · New Journal of Physics · doi:10.1088/1367-2630/17/2/023049 · Cited by 182
Regime shifts in the anthropocene: drivers, risks, and resilience
Rocha, J. C., Peterson, G. D., & Biggs, R. (2015) · PLOS ONE · doi:10.1371/journal.pone.0134639 · Cited by 181
On the origins of hierarchy in complex networks
Corominas-Murtra, B., Goñi, J., Solé, R. V., & Rodríguez-Caso, C. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1300832110 · Cited by 160
Response Delays and the Structure of Transcription Networks
Rosenfeld, N., & Alon, U. (2003) · Journal of Molecular Biology · doi:10.1016/s0022-2836(03)00506-0 · Cited by 148
EEG functional connectivity is partially predicted by underlying white matter connectivity
Chu, C. J., Tanaka, N., Diaz, J., Edlow, B. L., Wu, O., Hämäläinen, M., Stufflebeam, S., Cash, S. S., & Kramer, M. A. (2015) · NeuroImage · doi:10.1016/j.neuroimage.2014.12.033 · Cited by 135
What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO
Dunning, I., Gupta, S., & Silberholz, J. (2018) · INFORMS Journal on Computing · doi:10.1287/ijoc.2017.0798 · Cited by 128
The Effect of Recommendations on Network Structure
Su, J., Sharma, A., & Goel, S. (2016) · Proceedings of the 25th International Conference on World Wide Web · doi:10.1145/2872427.2883040 · Cited by 78
Viscoelastic Networks: Forming Cells and Tissues
Corominas-Murtra, B., & Petridou, N. I. (2021) · Frontiers in Physics · doi:10.3389/fphy.2021.666916 · Cited by 69
Li, Z. (., Fang, X., & Sheng, O. R. L. (2018) · ACM Transactions on Management Information Systems · doi:10.1145/3131782 · Cited by 65
Insights into bootstrap percolation: Its equivalence with k-core percolation and the giant component
Di Muro, M. A., Valdez, L. D., Stanley, H. E., Buldyrev, S. V., & Braunstein, L. A. (2019) · Physical Review E · doi:10.1103/physreve.99.022311 · Cited by 18
Hierarchy in directed random networks
Mones, E. (2013) · Physical Review E · doi:10.1103/physreve.87.022817 · Cited by 16
Metadata
- Authors
- Newman, M. E. J., Strogatz, S. H., & Watts, D. J.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2001-07-24
- Volume
- 64
- Issue
- 2
- Pages
- 026118-026118
- ISSN
- 1063-651X (ISSN-L)
- 1095-3787
- OpenAlex
- W2169015768
- Cited by
- 3,648
- References
- 4
- FWCI
- 57.34
- Type
- journal article
- Language
- en
- Open access
- bronze
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.
