更改

随机图 (查看源代码)

2020年11月21日 (六) 16:31的版本

添加81字节、 2020年11月21日 (六) 16:31

第9行：第9行：

==模型==

−

从一组 n 个孤立的顶点开始，在它们之间随机添加连续的边，这样就得到一个随机图。这个领域的研究的目的是确定在什么阶段图形的特殊性质可能出现<ref name = "Random Graphs2">[[Béla Bollobás]], ''Random Graphs'', 1985, Academic Press Inc., London Ltd.</ref>。不同的随机图模型在图上产生不同的概率分布。最常见的研究是由埃德加 · 吉尔伯特提出的，表示''G'' (''n'',~~''p''~~) ~~，其中每个可能的边独立出现的概率为0~~ < ''p'' < ~~1。获得任意一个~~ m 边随机图的概率是 <math>p^m (1-p)^(N-m)</math > ，记号是 <math>N=\tbinom{n}{2}</math > 。<ref name = "Random Graphs3">[[Béla Bollobás]], ''Probabilistic Combinatorics and Its Applications'', 1991, Providence, RI: American Mathematical Society.</ref>

+

从一组 n 个孤立的顶点开始，在它们之间随机添加连续的边，这样就得到一个随机图。这个领域的研究的目的是确定在什么阶段图形的特殊性质可能出现<ref name = "Random Graphs2">[[Béla Bollobás]], ''Random Graphs'', 1985, Academic Press Inc., London Ltd.</ref>。不同的随机图模型在图上产生不同的概率分布。最常见的研究是由埃德加 · 吉尔伯特提出的，表示<math>G(n,M)</math> ，其中每个可能的边独立出现的概率为<math>0 <p< 1</math>。获得任意一个 m 边随机图的概率是 <math>p^m (1-p)^(N-m)</math > ，记号是 <math>N=\tbinom{n}{2}</math > 。<ref name = "Random Graphs3">[[Béla Bollobás]], ''Probabilistic Combinatorics and Its Applications'', 1991, Providence, RI: American Mathematical Society.</ref>

−

一个相关性强的模型，Erdős-Rényi模型表示<math>G(n,M)</math> ，给每一个正好有''M''~~条边的图赋予等概率。当0≤ ''~~M'' ≤ ''N'' 时，''G'' (''n'',''M'')具有 <math>\tbinom{N}{M}</math> 元素，且每个元素都以概率<math>1/\tbinom{N}{M}</math> 出现。后一个模型可以看作是随机图过程<math>\tilde{G}_n</math>某个特定时间(''M'')的一个快照，这个时间(''M'')是从 n 个顶点开始没有边的一个随机过程，每个步骤均匀地从缺失的边集中选择一个新的边。

+

一个相关性强的模型，Erdős-Rényi模型表示<math>G(n,M)</math> ，给每一个正好有''M''条边的图赋予等概率。当<math>0≤ M ≤ N</math>时，<math>G(n,M)</math>具有 <math>\tbinom{N}{M}</math> 元素，且每个元素都以概率<math>1/\tbinom{N}{M}</math> 出现。后一个模型可以看作是随机图过程<math>\tilde{G}_n</math>某个特定时间(''M'')的一个快照，这个时间(''M'')是从 <math>n</math> 个顶点开始没有边的一个随机过程，每个步骤均匀地从缺失的边集中选择一个新的边。

−

如果我们从一个无限的顶点集合开始，然后再次让每个可能的边以概率<math>0 < ''p'' < 1</math>独立出现，那么我们得到一个对象 ''G'' 称为'''无限随机图 Infinite Graph'''。除了在 ''p'' = ~~0或1的平凡情况下，这样的 ''~~G'' 在大多数情况下肯定具有以下性质:

+

如果我们从一个无限的顶点集合开始，然后再次让每个可能的边以概率<math>0<p< 1</math>独立出现，那么我们得到一个对象 <math>G</math> 称为'''无限随机图 Infinite Graph'''。除了在 <math>p = 0</math>或1的平凡情况下，这样的 <math>G</math> 在大多数情况下肯定具有以下性质:

−

在 <math>v</math> 中，给定任何 ''n + ''m'' 个元素，<math>a_1,\ldots,a_n,b_1,\ldots,b_m\</math> 中有一个顶点 ''c''，它与每个 <math>a_1,\ldots,a_n</math> 相邻，并且不与任何 <math>b_1,\ldots,b_m</math> 相邻。

+

在 <math>v</math> 中，给定任何 <math>n + m</math> 个元素，<math>a_1,\ldots,a_n,b_1,\ldots,b_m\</math> 中有一个顶点<math>c</math>，它与每个 <math>a_1,\ldots,a_n</math> 相邻，并且不与任何 <math>b_1,\ldots,b_m</math> 相邻。

结果表明，如果顶点集是可数的，那么在'''同构 Isomorphism'''意义下，只有一个图具有这个性质，即 Rado 图。因此，任何可数无限随机图几乎可以肯定是 Rado 图，由于这个原因，有时被简称为随机图。然而，对于'''不可数图 Uncountable Graph'''类似的结果是不正确的，不可数图中有许多'''不同构图 Nonisomorphic Graph'''满足上述性质。

−

另一个模型，概括了吉尔伯特的随机图模型，是'''随机点积模型 Random Dot-product Model'''。一个'''随机点积图 Random Dot-product Graph''' 将每个顶点与一个实向量相关联。任意顶点 ''u'' 和 ''v'' 之间的边 ''uv'' 的概率是它们各自向量的点积 ~~''u'' · ''v''~~ 的某个函数。

+

另一个模型，概括了吉尔伯特的随机图模型，是'''随机点积模型 Random Dot-product Model'''。一个'''随机点积图 Random Dot-product Graph''' 将每个顶点与一个实向量相关联。任意顶点 <math>u</math> 和 <math>v</math>之间的边 <math>uv</math> 的概率是它们各自向量的点积 <math>u·v</math> 的某个函数。

'''网络转移矩阵 NetWork Probability Matrix'''通过边概率对随机图进行建模，这些边概率代表给定的边存在一个特定的时间段的概率。这个模型可以扩展到有向和无向，加权和无权，以及静态或动态的图形结构。

−

对于 ''M''something ''pN''，其中 ''N'' 是可能的最大边数，两个最广泛使用的模型，''G'' (''n'',~~， ''~~M'')和 ''G'' (''n~~''，''~~p'')在大多数情况下是可互换的<ref name ="Handbook ">[[Béla Bollobás|Bollobas, B.]] and Riordan, O.M. "Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003</ref>。

+

对于 ''M''something ''pN''，其中 ''N'' 是可能的最大边数，两个最广泛使用的模型，<math>G(n,M)</math>和 <math>G(n,p)</math>在大多数情况下是可互换的<ref name ="Handbook ">[[Béla Bollobás|Bollobas, B.]] and Riordan, O.M. "Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003</ref>。

'''随机正则图 Random Regular Graph'''是一种特殊情况，其性质可能与一般随机图不同。

打豆豆

421

个编辑