随机图

随机图从一组 n 个孤立顶点开始，在它们之间随机地添加连续的边。该领域研究的目的是确定图的特定属性可能出现在哪个阶段。 不同的 随机图模型 在图上生产不同的概率分布。最常见的研究是由 埃德加·吉尔伯特，表示为 G（n,p)，其中每个可能的边缘都以概率0 < p < 1出现。获得任何一个特定的 具有m条边的随机图的概率是    用符号   表示。

一个密切相关的模型 erdős–rényi模型 表示为 G（n,M)，将相等的概率赋给所有严格具有M条边的图。当0 ≤M ≤N时, G（n,M)有    元素，每个元素都以概率   出现。 后一种模型可以被视为特定时间(M)的快照的 随机图过程   ，这是一个 随机过程， 该过程初始时有n 顶点而没有边，并且在每一步添加一条从缺失边集中均匀选择的新边。

相反，如果我们从一组无限的顶点开始，并再次让每条可能的边以概率0 < p < 1，然后我们得到一个对象 G 叫做 无限随机图。除了在极端的情况下 p 是0或1，这样一个 G 几乎可以肯定 具有以下属性:

Given any n + m elements   , there is a vertex c in V that is adjacent to each of    and is not adjacent to any of   .

如果顶点集是 可数的 还有， 直到 同形，只有一个具有此属性的图，即 拉多图。因此，任何可数无限随机图几乎肯定是拉多图，因此有时简称为 随机图。然而，类似的结果对于不可数图是不成立的，其中有许多(非同态)图满足上述性质。

另一个将吉尔伯特随机图模型泛化的模型是 随机点积模型。随机点积图与每个顶点关联 实向量。 任何顶点u 和v 组成的边uv的概率是其对应的向量u和v的点积u·v的某个函数。

这 网络概率矩阵 通过边的概率来建模随机图    给定的优势    存在一段指定的时间。该模型可扩展到有向和无向；加权和未加权；和静态或动态图形结构。

为 M ≃ pN，其中 N 边数的最大可能，两个最广泛使用的模型：G（n,M)和 G（n,p)，几乎可以互换。

随机正则图s构成了一个特例，其性质可能不同于一般的随机图。

一旦我们有了随机图的模型，图上的每个函数就变成了 随机变量。对这个模型的研究是为了确定一个属性是否发生，或者至少估计发生的概率。

随机图上下文中的术语“几乎每一个”指的是一系列空间和概率，因此 误差概率 趋向于零。^[2]

随机图理论研究随机图的典型性质，这些性质对于从特定分布绘制的图具有很高的概率。 例如，我们可能要求给定的值    和    可能性有多大    存在 连接的。 在研究这类问题时，研究人员通常集中在随机图的渐近行为上—各种概率收敛为的值    变得非常大。 逾渗理论 刻画随机图的连通性，特别是无限大图。

渗透与图形(也称为网络)的健壮性有关。 给定一个随机图表    节点和平均度数   。接下来，我们随机移除一个分数    只留下一小部分   。存在临界渗透阈值    低于该值时，网络变得支离破碎，而高于该值时    存在一个巨大的连接组件。^{[2][2][2][3] [4]}

局部渗滤是指移除一个节点的邻居、下一个最近的邻居等。直到一小部分    从网络中删除的节点数。结果表明，对于泊松分布的随机图    就像随机移除一样。对于其他类型的学位分布    因为局部攻击不同于随机攻击^[5] (阈值函数，进化    )

随机图广泛应用于 概率法，试图证明具有某些性质的图的存在性。随机图上属性的存在通常意味着，通过 泽梅迪正则引理几乎所有图上该性质的存在性。

在 随机正则图s，    是一套   -正则图，带有    这样    和    是自然数，   ，和    是平的。^[6]

图的度序列    在    仅取决于集合中的边数^[6]

如果边缘，    在随机图表中，    大到足以确保几乎每一个    最低学位至少为1，然后几乎每    已经连接，如果    几乎每一个    完美匹配。特别是，在几乎每个随机图中最后一个孤立顶点消失的时刻，该图变得连接起来。^[6]

几乎每一个图都在偶数个顶点上进行，边的最小度数提高到1，或者随机图的最小度数略大于1    概率接近1的边确保了除了最多一个顶点之外，图具有完全匹配。

对于一些常数   ，几乎每一个带有    顶点，至少    边缘是 哈密顿量。随着概率趋向于1，将最小度增加到2的特定边使图哈密尔顿。

随机图的性质在图变换下可以改变或保持不变。 玛莎吉 例如，等人证明了将随机图转换成它们的边对偶图(或线图)的变换产生了具有几乎相同程度分布的图的集合，但是具有程度相关性和显著更高的聚类系数。^[6]

给定一个随机图 G 和顺序 n ，顶点 V（G)= {1，..., n}，由 贪婪算法 在颜色数量上，顶点可以用颜色1、2，...(顶点1被着色为1，如果顶点2不与顶点1相邻，则顶点2被着色为1，否则它被着色为2，依此类推。)。^[7] 给定一定数量的随机图的正确着色的数量 q 颜色，称为它的 色多项式，是未知的。带参数随机图的色多项式零点的标度 n 和边的数量 m 或者连接概率 p 已经使用基于符号模式匹配的算法进行了经验研究。^[7]

一个随机树 是一个 树 或者 树木状 通过 随机过程形式化。在大范围的随机有序图中 n 和尺寸 M（n)顺序树组件数量的分布 k 是渐近的 泊松。随机树的类型包括 均匀生成树, 随机最小生成树, 随机二叉树, treap, 快速探索随机树, 布朗树，和 随机森林。

考虑定义在 概率空间    让    是分配给中每个图的实值函数    向量 m 属性。 固定的   , 条件随机图 是概率度量的模型    给所有图形分配零概率   。

特殊情况有 条件一致随机图，哪里    为所有具有指定属性的图分配相等的概率。它们可以被看作是 erdős–rényi模型 G（n,M)，当条件信息不一定是边的数量时 M，但是无论其他任意图形属性是什么   。在这种情况下，很少有分析结果可用，并且需要模拟来获得平均特性的经验分布。最近，一种通用而精确的随机图模拟方法被提出 。^[8]

其他最近研究的 条件随机图 是 条件指数随机图模型，哪里    所有图形都有ERGM函数形式   。Nasini等人引入了这类模型。^[9] 在…情况下 科学合作网络

在相互依赖的图中，一个网络(图)中的节点依赖于其他网络来运行。因此，一个或几个图中的故障会导致图形之间的级联故障，这可能会导致突然崩溃。^[10][11]

随机图模型的最早是 海伦·霍尔·詹宁斯 和 雅各布·莫雷诺 在1938年第一次使用，在研究比较网络数据中往复链接的比例和随机模型时，考虑了“机会社会图”(定向Erdős-Rényi模型)。^[12] 另一个用途，在“随机网络”的名称下，是由 索洛单夫和拉波波特在1951年提出，使用了一个有向图模型，该模型具有固定的外度和随机选择的到其他顶点的附件。^[13]

这 erdős–rényi模型 随机图的第一个定义是 Paul Erdős 和 Alfréd Rényi 在他们1959年的论文《随机图》中^[14] ，以及吉尔伯特在他的论文《随机图》中独立地指出。^[14]