Random graphs
By Alan M. Frieze. 2006
12,398 citations recorded by the source corpus.
We will review some of the major results in random graphs and some of the more challenging open problems. We will cover algorithmic and structural questions. We will touch on newer models, including those related to the WWW.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Statistical and Nonlinear Physics, Algorithms & Complexity, Network Science & Complex Systems
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Bernhard Schölkopf
- Kun Zhang
- Sourav Chatterjee
- Charles Bordenave
- Jure Leskovec
- Santo Fortunato
- Clark Glymour
- Biwei Huang
In Discrete Mathematics and Combinatorics
- Jun Yin
- Horng-Tzer Yau
- Sourav Chatterjee
- Antti Knowles
- Van H. Vu
- Charles Bordenave
- Terence Tao
- L. Erdős
In Statistical and Nonlinear Physics
- Jure Leskovec
- Santo Fortunato
- Mark Newman
- Olaf Sporns
- M. A. Porter
- Alex Arenas
- D. Bassett
- Matjaz Perc
In Algorithms & Complexity
- M. A. Porter
- Jure Leskovec
- Marc Barthelemy
- Santo Fortunato
- D. Bassett
- E. Bullmore
- Renaud Lambiotte
- Darko Hric
In Network Science & Complex Systems
- Bernhard Schölkopf
- Santo Fortunato
- Marc Barthelemy
- D. Bassett
- M. A. Porter
- E. Bullmore
- Jure Leskovec
- Darko Hric
Citations in the corpus
- Causal Discovery from Heterogeneous/Nonstationary Data (2019, methodology): “We randomly generated acyclic causal structures according to the Erdos-Renyi model (Erd˝os and R´enyi, 1959) with parameter 0.3.”
- Graphite: Iterative Generative Modeling of Graphs (2018, methodology): “The earliest probabilistic models of graphs proposed to generate graphs by creating an edge between any pair of nodes with a constant probability [8].”
- GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models (2018, methodology): “Following Li et al. 2018 we compare against the Erd˝os-R´enyi model (E-R) (Erd˝os & R´enyi, 1959) and the Barab´asi-Albert (B-A) model (Albert & Barab´asi, 2002).”
- Exact Matrix Completion via Convex Optimization (2008, neutral): “When the entries are sampled uniformly at random, it is well known that one needs on the order of n log n samples to obtain a fully connected graph with large probability (see, e.g., [8]).”
- Community detection in graphs (2009, neutral): “A random graph à la Erdös-Rényi (Section A.3), for instance, is not expected to have community structure, as any two vertices have the same probability to be adjacent, so there should be no preferential linking involving special groups of vertices.”
- Graph-Based Continual Learning (2020, background): “More precisely, the distribution of the resulting Erd˝os-Rényi random graphs (Erdös and Rényi, 1959) can be defined as for all i , k ∈ C and j ∈ T where κ τ : R d 1 × R d 1 → [0, ∞ ) is a kernel function that encodes similarities between image embeddings such as the RBF kernel Here, with a slight…”
- Harnessing smoothness to accelerate distributed optimization (2016, methodology): “We choose n = 100 agents and the graph is generated using the Erdos-Renyi model [30] with connectivity probability 0.”
- A Weighted and Directed Interareal Connectivity Matrix for Macaque Cerebral Cortex (2012, neutral): “Here, we explore the classical notion of graph density (Janson et al. 2000; Newman 2010) of the FIN using multiple approaches that give converging results.”
- Linear Algebra and its Applications (2010, neutral): “The so-called exponential integration methods form another class being built on linearization and direct use of accurate, unconditionally stable approximations to the exponential operator.”
- The Kuramoto model in complex networks (2015, background): “If 〈k〉 > 1, there is an emergence of a giant component [446].”
- The architecture of the climate network (2004, neutral): “This choice guarantees that a random graph with the same speci+cations (number of nodes, and average links per node) will be connected [11].”