On the evolution of random graphs

By P. Erdos, A. Rényi. 1984

Subfields: Probabilistic & Bayesian Methods, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Probabilistic & Bayesian Methods

In Algorithms & Complexity

Citations in the corpus

Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model (2021, methodology): “More recently, (Han et al., 2020) signiﬁcantly sharpened Simon’s and Yao’s analysis and provided a sufﬁcient condition for sparse Erd¨os-Renyi type of graph topologies (Erd˝os & R´enyi, 1960).”
Neural Execution Engines: Learning to Execute Subroutines (2020, methodology): “For both scenarios, we use 20000 training sequences/graphs of size 8 and 2000 validation sequences/graphs and test on 100 graphs of the following types with various sizes: • Erdős-Rényi random graphs [9]: each pair of nodes has probability p to form an edge, we use p uniformly sampled from [0, 1].”
Bayesian Structure Learning with Generative Flow Networks (2022, methodology): “Therefore, we sampled N = 100 datapoints from a randomly generated (under an Erd˝os-Rényi model; Erd˝os and Rényi, 1960) We evaluated the quality of the approximation based on the probability of various structural features.”
Learning Combinatorial Optimization Algorithms over Graphs (2017, methodology): “For the MVC and MAXCUT problems, we generate Erd˝os-Renyi (ER) [11] and Barabasi-Albert (BA) [1] graphs which have been used to model many real-world networks.”
GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders (2018, neutral): “Related work pre-dating deep learning includes random graphs (Erdos & R´enyi, 1960; Barab´asi & Albert, 1999), stochastic blockmodels (Snijders & Nowicki, 1997), or state transition matrix learning (Gong & Xiang, 2003).”
Towards Sparse Hierarchical Graph Classifiers (2018, background): “25) during training on Erdős-Rényi graphs [9] of varying node sizes (and |E| = 2|V |).”
Permutation Invariant Graph Generation via Score-Based Generative Modeling (2020, methodology): “For both tasks, all the graphs are randomly sampled from the Erdős and Rényi model (E-R) (Erdos and Rényi, 1960) with n = 12 and p = 0 .”
Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods (2021, methodology): “We generate graphs in which node labels are independent of edges by randomly choosing node labels and generating graph edges by the Erdős-Rényi random graph model [22].”
Anomalous critical and supercritical phenomena in explosive percolation (2015, methodology): “1(b), together with a realization of a ErdősRényi (ER) [3, 4] and a Bohman-Frieze (BF) [12] process on a system of size N = 106.”
An introduction to large deviations for random graphs (2016, methodology): “This is known as the Erdős–Rényi G(n, p) model, originally defined in [25].”
The Large-Scale Structure of Semantic Networks: Statistical Analyses and a Model of Semantic Growth (2005, background): “2 also illustrates two general properties of random graphs—graphs that are generated by placing an edge between any two nodes with some constant probability p independent of the existence of any other edge (a model introduced by Erdös and Réyni, 1960).”
A model of Internet topology using k-shell decomposition (2006, background): “Bollobas [8] introduced the k-core as a necessary but not sufficient condition for a subgraph to be k-colorable, and proved under very restrictive conditions that nonvanishing k-cores of a random graph in which all nodes have a Poisson distribution of the number of their neighbors (this is called an”
Principal Neighbourhood Aggregation for Graph Nets (2020, unknown): “In the multi-task benchmark, we consider three node labels and three graph labels.”
The component sizes of a critical random graph with given degree sequence (2010, background): “Then, for large integers n, SGn is an approximation of the Erdős–Renyi random graph G(n,1/n).”
Probabilistic broadcast for flooding in wireless mobile ad hoc networks (2003, background): “Erd˝ os and Rényi [8] have shown that the probability of a random graph being connected tends to 1 if the number of edges E is greater than p c ¦ E § © ¨ N logN 2 .”