Erdos-Renyi随机图的生成方法与特性有哪些特点？

本文共计2028个文字，预计阅读时间需要9分钟。

Erdos-Renyi随机图以两位著名的匈牙利数学家P.Erdős和A. Rényi的名字命名的，是生成随机无向图最简单和常用的方法，包括以下两种紧密相关的变体：G(n,p): 拥有n个节点，且边(u, v)以独立同分布的概率p产生的无向图；G(n, m): 拥有n个节点，且其中m条边按照均匀分布采样生成的无向图。G(n, p)生成时按某个次序考虑所有可能边中的每一条，然后以概率p独立地往图上添加每条边。 1 随机图生成简介 1.1 \(G_{np}\)和\(G_{nm}\)

以下是我学习《CS224W：Machine Learning With Graphs》^[1]中随机图生成部分的笔记，部分补充内容参考了随机算法教材^[2]和wiki^[3]。随机图生成算法应用非常广泛，在NetworkX网络数据库中也内置的相关算法。我觉得做图机器学习的童鞋很有必要了解下。

Erdos-Renyi随机图^[4]以两位著名的匈牙利数学家P.Erdős和A. Rényi的名字命名的，是生成随机无向图最简单和常用的方法，包括以下两种紧密相关的变体：

• \(G_{np}\): 拥有\(n\)个节点，且边\((u, v)\)以独立同分布的概率\(p\)产生的无向图

• \(G_{nm}\): 拥有\(n\)个节点，且其中\(m\)条边按照均匀分布采样生成的无向图。