随机图模型简介：二项随机图与均匀随机图

"这份资源是Tomasz Łuczak在2015年Cargèse秋季随机图研讨会上的演讲材料，主要介绍了两种主要的随机图模型：二项式随机图G(n,p)和均匀随机图G(n,M)。" 在随机图理论中，这两种模型是理解和分析复杂网络结构的基础。它们模拟了随机性在图形生成过程中的作用，从而为各种数学问题提供了一个有趣的框架。 首先，二项式随机图G(n,p)是基于概率p构建的。在这个模型中，有n个顶点，每一对不同的顶点之间形成边的概率都是p，且这些边的生成是独立的。这意味着，对于所有的(n choose 2)即n*(n-1)/2对顶点，每一对成为边的概率是独立的p，不存在任何关联。因此，G(n,p)的期望边数是np(n-1)，而实际的边数可能因随机性而有所不同。 其次，均匀随机图G(n,M)是从所有含有n个顶点和M条边的图的集合中随机选择的一个。换句话说，每个具有M条边的图被等概率地选取。如果我们要计算一个特定图G成为G(n,M)的概率，如果G恰好有M条边，那么这个概率是1除以所有可能的具有M条边的图的数量，即1/(C(n,2,M))，其中C(n,2,M)是组合数，表示在n个顶点中选择2个形成M条边的不同方式。 在实际应用中，通常关注的是当n非常大时的随机图行为。例如，对于二项式随机图G(n,p)，我们可能关心的是在p随着n变化时，图的性质，如连通性、团的大小或平均路径长度等如何变化。当p随着n的增长保持在某个常数值附近时，G(n,p)会经历所谓的"临界现象"，比如从无大团到出现大团的转变，或者从几乎不连通到几乎完全连通的转变。 而均匀随机图G(n,M)在M相对于n的大小变化时，也会展现出不同的特性。例如，当M接近n*(n-1)/2（即所有可能边的一半）时，图趋于完全图；而当M远小于这个值时，图更可能是稀疏的，包含多个小的连通分量。 随机图模型帮助我们理解在大量节点和边的复杂网络中可能出现的结构和模式，这在社交网络、互联网、生物网络等领域都有重要应用。通过对这些模型的研究，我们可以推断出网络的全局性质，如聚类系数、度分布、直径等，并进一步探索其动态行为，如传染过程或信息传播。