On the Evolution of Random Graphs.¶
Erdős, P., & Rényi, A. (1960). On the Evolution of Random Graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5, 17-61.
Cited by¶
5 citations across 5 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Criticality
- At criticality, the component-size distribution is a power law \(P(s) \propto s^{-5/2}\), the correlation length (typical finite-component size) diverges, and small edge additions produce disproportionately large changes — a transition Erdős and Rényi (1960) characterized in their original paper on random graph evolution.
This sourceSeminal characterization of the random-graph G(n,p) phase transition at mean degree one, where a giant connected component emerges, supporting the marker's percolation-criticality example.
- At criticality, the component-size distribution is a power law \(P(s) \propto s^{-5/2}\), the correlation length (typical finite-component size) diverges, and small edge additions produce disproportionately large changes — a transition Erdős and Rényi (1960) characterized in their original paper on random graph evolution.
- Percolation
- The Erdős-Rényi giant-component transition, carried over to internet topology, produces the robust-to-random-fragile-to-targeted result directly.
This sourceEstablishes the sudden emergence of a giant connected component in random graphs as edge density crosses a critical value.
Supported in partVerified against the work's full text
Supplies the abrupt giant-component transition in random graphs at about n/2 edges; nothing on internet topology, random failure versus targeted attack, or a direct link.
“When N(n) passes the threshold n/2, the structure of r,, N(~) changes abruptly.”
- The Erdős-Rényi giant-component transition, carried over to internet topology, produces the robust-to-random-fragile-to-targeted result directly.
Domain-specific¶
- Local World Evolving Network Models
- Local-world models relax global-information assumptions in preferential attachment by giving arriving nodes access only to a sampled neighborhood, community, or bounded subset.
This sourceMath. Inst. Hung. Acad. Sci, Vol.5, p.17-61.
- Local-world models relax global-information assumptions in preferential attachment by giving arriving nodes access only to a sampled neighborhood, community, or bounded subset.
Mechanisms¶
- Component-Merge Simulation
- Across those runs it locates the point at which a giant component emerges — the percolation-style threshold
This sourceErdős and Rényi establish a threshold regime for the emergence of a giant component in an evolving random graph. They do not describe this mechanism's simulation runs, uncertainty bands, or candidate scoring rule.
- Across those runs it locates the point at which a giant component emerges — the percolation-style threshold
- Network Correlation Monitor
- It is watching the graph's connectivity structure become effectively denser, in the spirit of a percolation threshold
This sourceRandom graphs undergo a connectivity transition in which increasing edge density produces a giant component spanning a macroscopic share of the graph.
- It is watching the graph's connectivity structure become effectively denser, in the spirit of a percolation threshold
Verification¶
Does it exist? Not checked yet. This entry carries no identifier to resolve. It was extracted from the citation as written in the article, normalized, and deduplicated against the rest of the registry.
Does it back the claim? Read against the text for 1 of 5 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 2 other ways.
- https://snap.stanford.edu/class/cs224w-readings/erdos60random.pdf ×1
- https://static.renyi.hu/renyi_cikkek/1960_renyi_on_the_evolution_of_random_graphs_17_61.pdf ×1
Registry ID ref:6702f702afb1 · see in the full table