The Erdös-Rényi (ER) model is a traditional graph generation approach where the likelihood of an edge existing between any two distinct nodes is an independent, constant probability. This generation process is mathematically expressed as $$P(A[u,v]=1)=r, \forall u,v \in \mathcal{V}, u \neq v$$, where the parameter $$r \in [0,1]$$ represents the expected density of the graph.

San Jose State University

Google

The goal of graph generation is to build models that can generate realistic graph structures. In some ways, we can view this graph generation problem as the mirror image of the graph embedding problem. There are three common traditional graph generation approaches:
- Erdös-Rényi (ER) model
- Stochastic Block Model (SBM)
- Preferential Attachment (PA) model

Traditional Graph Generation

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

The primary insight in the common traditional models is that we specify a generation process or probability model, which allows us to capture some useful property of real-world graphs while still being tractable and easy to analyze. Historically, these traditional generation models have been used in two key applications:
- Generating synthetic data
- Creating null models

Traditional Applications

Molecule generation is the task of generating diverse and novel molecules that has certain desirable chemical properties.

Learn Before

Related