421
个编辑
更改
跳到导航
跳到搜索
第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'''满足上述性质。
结果表明，如果顶点集是可数的，那么在'''同构 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'''通过边概率对随机图进行建模，这些边概率代表给定的边存在一个特定的时间段的概率。这个模型可以扩展到有向和无向，加权和无权，以及静态或动态的图形结构。
'''网络转移矩阵 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'''是一种特殊情况，其性质可能与一般随机图不同。
'''随机正则图 Random Regular Graph'''是一种特殊情况，其性质可能与一般随机图不同。