“随机图”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
第11行： 第11行：
 
从一组 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>。不同的随机图模型在图上产生不同的概率分布。最常见的研究是由埃德加 · 吉尔伯特提出的，表示''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>
  
−
一个相关性强的模型，Erdős-Rényi模型表示''G'' (''n'',''M'')，给每一个正好有''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''条边的图赋予等概率。当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 个顶点开始没有边的一个随机过程，每个步骤均匀地从缺失的边集中选择一个新的边。
  
−
如果我们从一个无限的顶点集合开始，然后再次让每个可能的边以概率0 < ''p'' < 1独立出现，那么我们得到一个对象 ''G'' 称为'''无限随机图 Infinite Graph'''。除了在 ''p'' = 0或1的平凡情况下，这样的 ''G'' 在大多数情况下肯定具有以下性质:
+
如果我们从一个无限的顶点集合开始，然后再次让每个可能的边以概率<math>0 < ''p'' < 1</math>独立出现，那么我们得到一个对象 ''G'' 称为'''无限随机图 Infinite Graph'''。除了在 ''p'' = 0或1的平凡情况下，这样的 ''G'' 在大多数情况下肯定具有以下性质:
  
 
在 <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> 中，给定任何 ''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> 相邻。
第37行： 第37行：
 
随机图理论研究随机图的典型性质，即从特定分布中抽取的图的高概率性质。例如，我们可以要求一个给定的值 <math>n</math> 和 <math>p</math>  <math>G(n，p)</math> 连接的概率。在研究这些问题时，研究人员往往集中在随机图的趋近行为上——各种概率收敛到的值变得非常大。'''渗流理论 Percolation Theory'''刻画了随机图，特别是无穷大图的'''连通性 Connectedness'''。
 
随机图理论研究随机图的典型性质，即从特定分布中抽取的图的高概率性质。例如，我们可以要求一个给定的值 <math>n</math> 和 <math>p</math>  <math>G(n，p)</math> 连接的概率。在研究这些问题时，研究人员往往集中在随机图的趋近行为上——各种概率收敛到的值变得非常大。'''渗流理论 Percolation Theory'''刻画了随机图，特别是无穷大图的'''连通性 Connectedness'''。
  
−
'''渗流 Percolation''' 与图形(也称为网络)的'''紧密性 Robustness'''有关。给定一个随机图形，其中的节点是 <math>n</math> 和一个平均度 <math>\langle k\rangle</math> 。接下来我们随机移除一部分概率为 <math>1-p</math> 的节点，只留下一部分概率为 <math>p</math> 的节点。存在一个'''临界渗透阈值 Critical Percolation Threshold'''<math>p_c=\tfrac{1}{\langle k\rangle}</math>，当低于这个临界渗透阈值，网络变得支离破碎，而高于临界渗透阈值 <math>p_c</math> 的网络则存在一个巨大的''连接元件 Connected Component'''(图论)<ref>{{cite book  |title=Networks: An Introduction |last= Newman |first=M. E. J. |year= 2010 |publisher=  Oxford}}</ref>。
+
'''渗流 Percolation''' 与图形(也称为网络)的'''紧密性 Robustness'''有关。给定一个随机图形，其中的节点是 <math>n</math> 和一个平均度 <math>\langle k\rangle</math> 。接下来我们随机移除一部分概率为 <math>1-p</math> 的节点，只留下一部分概率为 <math>p</math> 的节点。存在一个'''临界渗透阈值 Critical Percolation Threshold'''<math>p_c=\tfrac{1}{\langle k\rangle}</math>，当低于这个临界渗透阈值，网络变得支离破碎，而高于临界渗透阈值 <math>p_c</math> 的网络则存在一个巨大的''连接元件 Connected Component'''(图论)<ref>{{cite book  |title=Networks: An Introduction |last= Newman |first=M. E. J. |year= 2010 |publisher=  Oxford}}</ref><ref>{{cite book |title= Complex Networks: Structure, Robustness and Function |authors= Reuven Cohen and [[Shlomo Havlin]] |year= 2010 |url= http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php |publisher= Cambridge University Press}}</ref>。
−
 
 
−
<ref>{{cite book |title= Complex Networks: Structure, Robustness and Function |authors= Reuven Cohen and [[Shlomo Havlin]] |year= 2010 |url= http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php |publisher= Cambridge University Press}}</ref><ref name ="On Random Graphs" />
 
  
 
'''局部渗滤 Localized Percolation'''指的是去除一个节点的邻居、次近邻等。直到网络中概率为 <math>1-p</math> 的一部分节点被移除。结果表明，对于服从泊松分布的随机图，其度分布为 <math>p_c=\tfrac{1}{\langle k\rangle}</math> ，和随机删除是一样的。对于其他类型的度分布 <math>p_c</math>，局部攻击和随机攻击是不同的。<ref name="ShaoHuang2015">{{cite journal|last1=Shao|first1=Shuai|last2=Huang|first2=Xuqing|last3=Stanley|first3=H Eugene|last4=Havlin|first4=Shlomo|title=Percolation of localized attack on complex networks|journal=New Journal of Physics|volume=17|issue=2|year=2015|pages=023049|issn=1367-2630|doi=10.1088/1367-2630/17/2/023049|arxiv=1412.3124|bibcode=2015NJPh...17b3049S}}</ref>
 
'''局部渗滤 Localized Percolation'''指的是去除一个节点的邻居、次近邻等。直到网络中概率为 <math>1-p</math> 的一部分节点被移除。结果表明，对于服从泊松分布的随机图，其度分布为 <math>p_c=\tfrac{1}{\langle k\rangle}</math> ，和随机删除是一样的。对于其他类型的度分布 <math>p_c</math>，局部攻击和随机攻击是不同的。<ref name="ShaoHuang2015">{{cite journal|last1=Shao|first1=Shuai|last2=Huang|first2=Xuqing|last3=Stanley|first3=H Eugene|last4=Havlin|first4=Shlomo|title=Percolation of localized attack on complex networks|journal=New Journal of Physics|volume=17|issue=2|year=2015|pages=023049|issn=1367-2630|doi=10.1088/1367-2630/17/2/023049|arxiv=1412.3124|bibcode=2015NJPh...17b3049S}}</ref>
第52行： 第50行：
  
 
:<math>V_n^{(2)} = \left \{ij \ : \ 1 \leq j \leq n, i \neq j \right \} \subset V^{(2)}, \qquad  i=1, \cdots, n.</math>
 
:<math>V_n^{(2)} = \left \{ij \ : \ 1 \leq j \leq n, i \neq j \right \} \subset V^{(2)}, \qquad  i=1, \cdots, n.</math>
−
 
−
<math>V_n^{(2)} = \left \{ij \ : \ 1 \leq j \leq n, i \neq j \right \} \subset V^{(2)}, \qquad  i=1, \cdots, n.</math>
 
−
 
−
<math>V_n^{(2)}=\left\{ij\:\1\leq j\leq n,i \neq j \right\}\子集 V^{(2)},\qquad i=1,\cdots,n.</math>
 
  
 
如果随机图中的边 <math>M</math>，<math>G_M</math> 大到足以确保几乎每个 <math>G_M</math> 的最小阶数至少为1，那么几乎每个 <math>G</math> 是连通的，如果 <math>n</math> 是偶数，则几乎每个 <math>G_M</math> 都有一个'''完美匹配 Perfect Matching'''。特别是，在几乎每个随机图中，最后一个孤立点消失的那一刻，图会变连通。
 
如果随机图中的边 <math>M</math>，<math>G_M</math> 大到足以确保几乎每个 <math>G_M</math> 的最小阶数至少为1，那么几乎每个 <math>G</math> 是连通的，如果 <math>n</math> 是偶数，则几乎每个 <math>G_M</math> 都有一个'''完美匹配 Perfect Matching'''。特别是，在几乎每个随机图中，最后一个孤立点消失的那一刻，图会变连通。
第77行： 第71行：
 
==条件随机图==
 
==条件随机图==
  
−
考虑一个给定的随机图模型定义在概率空间上<math>(\Omega,\mathcal{F},P)</math> ，并且让 <math>\mathcal{P}(G):\Omega\tarrow R^{m}</math> 是一个值是实数的函数，它在 <math>\Omega</math> 中为每个图赋值一个 ''m'' 属性的向量。
+
考虑一个给定的随机图模型定义在概率空间上<math>(\Omega,\mathcal{F},P)</math> ，并且让 <math>\mathcal{P}(G) : \Omega \rightarrow R^{m}</math> 是一个值是实数的函数，它在 <math>\Omega</math> 中为每个图赋值一个 ''m'' 属性的向量。
  
 
对于 <math>R^{m}</math> 中的一个固定的 <math>\mathbf{p}</math> ，条件随机图是这样的模型，在这个模型中，机率量测 <math>p</math> 给所有图分配零概率，例如“ <math>\mathcal{P}(G)\neq\mathbf{p}</math> 。  
 
对于 <math>R^{m}</math> 中的一个固定的 <math>\mathbf{p}</math> ，条件随机图是这样的模型，在这个模型中，机率量测 <math>p</math> 给所有图分配零概率，例如“ <math>\mathcal{P}(G)\neq\mathbf{p}</math> 。  
第95行： 第89行：
 
==另请参见==
 
==另请参见==
  
−
* [[Bose–Einstein condensation: a network theory approach]]
+
*'''玻色-爱因斯坦凝聚Bose–Einstein Condensation''': a network theory approach
−
'''玻色-爱因斯坦凝聚Bose–Einstein Condensation''': a network theory approach
+
*'''[[空腔法]] Cavity Method'''
−
* [[Cavity method]]
+
*'''[[复杂网络]] Complex Network'''
−
'''空腔法 Cavity Method'''
+
*'''Dual-phase Evolution'''
−
* [[Complex networks]]
+
*'''Erdős–Rényi 模型'''
−
'''复杂网络 Complex Network'''
+
*'''[[指数随机图模型]] Exponential Random Graph Model'''
−
* [[Dual-phase evolution]]
+
*'''[[图论]] Graph Theory'''
−
'''Dual-phase Evolution'''
+
*'''相互依存图 Interdependent Networks'''
−
* [[Erdős–Rényi model]]
+
*'''[[网络科学]] Network Science'''
−
'''Erdős–Rényi model'''
+
*'''[[渗流]] Percolation'''
−
* [[Exponential random graph model]]
+
*'''[[渗流理论]] Percolation Theory'''
−
'''指数随机图模型 Exponential Random Graph Model'''
+
*'''[[正则图]] Regular Graph'''
−
* [[Graph theory]]
+
*'''[[无标度网络]] [[Scale Free Network]]'''
−
'''图论 Graph Theory'''
+
*'''[[半线性相应]] Semilinear Response'''
−
* [[Interdependent networks]]
+
*'''[[随机块体模型]] Stochastic Block Model'''
−
'''相互依存图 Interdependent Networks'''
+
*'''Lanchinetti Fortunato Radicchi基准'''
−
* [[Network science]]
 
−
'''网络科学 Network Science'''
 
−
* [[Percolation]]
 
−
'''渗流 Percolation'''
 
−
* [[Percolation theory]]
 
−
'''渗流理论 Percolation Theory'''
 
−
* [[Regular graph]]
 
−
'''正则图 Regular Graph'''
 
−
* [[Scale free network]]
 
−
'''无标度网络 Scale Free Network'''
 
−
* [[Semilinear response]]
 
−
'''半线性相应 Semilinear Response'''
 
−
* [[Stochastic block model]]
 
−
'''随机块体模型 Stochastic Block Model'''
 
−
*[[Lancichinetti–Fortunato–Radicchi benchmark]]
 
−
'''Lanchinetti Fortunato Radicchi基准 Lancichinetti–Fortunato–Radicchi Benchmark</font>'''
 
  
 
==References 参考文献==
 
==References 参考文献==
−
 
 
{{reflist}}
 
{{reflist}}
−
 
−
 
  
 
{{Stochastic processes}}
 
{{Stochastic processes}}
  
−
 
−
 
−
{{DEFAULTSORT:图论}}
 
  
 
[[Category:图论]]
 
[[Category:图论]]

2020年11月21日 (六) 15:48的版本


在数学领域中，随机图 Random Graph是指图上的概率分布的一般术语。随机图可以简单地用概率分布表示，也可以用生成它们的随机过程表示[1][2]。随机图的理论处于图论和概率论的交汇点上。从数学的角度来看，随机图可以用来回答有关典型图的性质的问题。在所有需要对复杂网络进行建模的领域都能看到它的实际应用——由于它反映了在不同领域遇到的不同类型的复杂网络，许多随机图模型就此被人们所熟知。在数学上，随机图几乎完全指的是 Erdős-Rényi 随机图模型 Erdős–Rényi Random Graph Model。在其他情况下，任何图形模型都可以称为随机图。

模型

从一组 n 个孤立的顶点开始，在它们之间随机添加连续的边，这样就得到一个随机图。这个领域的研究的目的是确定在什么阶段图形的特殊性质可能出现[3]。不同的随机图模型在图上产生不同的概率分布。最常见的研究是由埃德加 · 吉尔伯特提出的，表示G (n,p) ，其中每个可能的边独立出现的概率为0 < p < 1。获得任意一个 m 边随机图的概率是 [math]\displaystyle{ p^m (1-p)^(N-m) }[/math] ，记号是 [math]\displaystyle{ N=\tbinom{n}{2} }[/math] 。[4]

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

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

在 [math]\displaystyle{ v }[/math] 中，给定任何 n + m 个元素，[math]\displaystyle{ a_1,\ldots,a_n,b_1,\ldots,b_m\ }[/math] 中有一个顶点 c，它与每个 [math]\displaystyle{ a_1,\ldots,a_n }[/math] 相邻，并且不与任何 [math]\displaystyle{ 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 的某个函数。

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

对于 Msomething pN，其中 N 是可能的最大边数，两个最广泛使用的模型，G (n,， M)和 G (n，p)在大多数情况下是可互换的[5]。

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

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

术语

在随机图的上下文中，“几乎每一个”这个术语指的是一系列空间和概率，使得出错概率趋于零。

性质

随机图理论研究随机图的典型性质，即从特定分布中抽取的图的高概率性质。例如，我们可以要求一个给定的值 [math]\displaystyle{ n }[/math] 和 [math]\displaystyle{ p }[/math] [math]\displaystyle{ G(n，p) }[/math] 连接的概率。在研究这些问题时，研究人员往往集中在随机图的趋近行为上——各种概率收敛到的值变得非常大。渗流理论 Percolation Theory刻画了随机图，特别是无穷大图的连通性 Connectedness。

'渗流 Percolation 与图形(也称为网络)的紧密性 Robustness有关。给定一个随机图形，其中的节点是 [math]\displaystyle{ n }[/math] 和一个平均度 [math]\displaystyle{ \langle k\rangle }[/math] 。接下来我们随机移除一部分概率为 [math]\displaystyle{ 1-p }[/math] 的节点，只留下一部分概率为 [math]\displaystyle{ p }[/math] 的节点。存在一个临界渗透阈值 Critical Percolation Threshold[math]\displaystyle{ p_c=\tfrac{1}{\langle k\rangle} }[/math]，当低于这个临界渗透阈值，网络变得支离破碎，而高于临界渗透阈值 [math]\displaystyle{ p_c }[/math] 的网络则存在一个巨大的连接元件 Connected Component(图论)[6][7]。

局部渗滤 Localized Percolation指的是去除一个节点的邻居、次近邻等。直到网络中概率为 [math]\displaystyle{ 1-p }[/math] 的一部分节点被移除。结果表明，对于服从泊松分布的随机图，其度分布为 [math]\displaystyle{ p_c=\tfrac{1}{\langle k\rangle} }[/math] ，和随机删除是一样的。对于其他类型的度分布 [math]\displaystyle{ p_c }[/math]，局部攻击和随机攻击是不同的。[8]

(阈值函数 Threshold Functions, [math]\displaystyle{ \tilde G }[/math] 的演化)

随机图在概率方法中得到了广泛的应用，它试图证明具有一定性质的图的存在性。通过 正则引理 Szemerédi Regularity Lemma，随机图上一个性质的存在常常意味着几乎所有图上该性质的存在。

在随机正则图中，[math]\displaystyle{ G(n，r-reg) }[/math] 是 [math]\displaystyle{ r=r(n) }[/math]的[math]\displaystyle{ r- }[/math]正则图的集合，其中 [math]\displaystyle{ n }[/math] 和 [math]\displaystyle{ m }[/math] 是自然数，[math]\displaystyle{ 3 \le r\lt n }[/math] ，[math]\displaystyle{ rn = 2m }[/math] 是偶数。

在 [math]\displaystyle{ G^n }[/math] 中，图 [math]\displaystyle{ G }[/math] 的度序列仅取决于集合中的边数。

[math]\displaystyle{ V_n^{(2)} = \left \{ij \ : \ 1 \leq j \leq n, i \neq j \right \} \subset V^{(2)}, \qquad i=1, \cdots, n. }[/math]

如果随机图中的边 [math]\displaystyle{ M }[/math]，[math]\displaystyle{ G_M }[/math] 大到足以确保几乎每个 [math]\displaystyle{ G_M }[/math] 的最小阶数至少为1，那么几乎每个 [math]\displaystyle{ G }[/math] 是连通的，如果 [math]\displaystyle{ n }[/math] 是偶数，则几乎每个 [math]\displaystyle{ G_M }[/math] 都有一个完美匹配 Perfect Matching。特别是，在几乎每个随机图中，最后一个孤立点消失的那一刻，图会变连通。

几乎每个偶数顶点上的最小度提高到1的图或稍大于 [math]\displaystyle{ \tfrac{n}{4}\log(n) }[/math] 边且概率接近1的随机图都能确保图有完全匹配 Complete Matching，但最多只有一个顶点。

对于某些常数 [math]\displaystyle{ c }[/math] ，几乎所有带有 [math]\displaystyle{ n }[/math] 顶点和至少 [math]\displaystyle{ cn\log(n) }[/math] 边的标记图都是 哈密尔顿环 Hamiltonian Cycle的。在概率趋于1的情况下，将最小度增加到2的特殊边会使图成为哈密尔顿图。

在图变换下，随机图的性质可以改变或保持不变。例如，Mashaghi A.等人证明了将随机图转换为其 边-对偶图 Edge-Dual Graphs(或 线图 Liner Graph)的变换会产生一个度分布几乎相同，但具有 度相关性 Degree Correlations 和显著更高的 聚类系数 Clustering Coefficent的图的集合。[9]

着色

给定一个 n 阶随机图 G，其顶点 V(G) = {1，... ，n } ，通过关于颜色数的贪婪算法 Greedy Algorithm，可以用颜色1,2。。。 (如果顶点1与顶点2不相邻，则顶点1与顶点2为染相同的颜色，否则染不同的颜色，以此类推。).

给定一个 q 颜色的随机图的真染色数，称为它的染色多项式 Chormatic Polynomial（到目前为止还没有确定的正式名称）。利用符号模式匹配算法 Algorithm Based On Symbolic Pattern Matching ，对参数为 n 、边数为 m 或连接概率为 p 的随机图的染色多项式零点的标度进行了实验研究。[10]

随机树图

随机树是由随机过程组成的树状图。在 n 阶和 M(n)大小的随机图的大范围内，k 阶树分量个数的分布是渐近泊松的。随机树的类型包括均匀生成树 Uniform Spanning Tree、随机最小生成树 Random Minimal Tree、随机二叉树 Random Binary Tree、树、快速检索随机树 Rapidly Exploring Random Tree、布朗树 Brownian Tree和随机森林 Random Forest。

条件随机图

考虑一个给定的随机图模型定义在概率空间上[math]\displaystyle{ (\Omega,\mathcal{F},P) }[/math] ，并且让 [math]\displaystyle{ \mathcal{P}(G) : \Omega \rightarrow R^{m} }[/math] 是一个值是实数的函数，它在 [math]\displaystyle{ \Omega }[/math] 中为每个图赋值一个 m 属性的向量。

对于 [math]\displaystyle{ R^{m} }[/math] 中的一个固定的 [math]\displaystyle{ \mathbf{p} }[/math] ，条件随机图是这样的模型，在这个模型中，机率量测 [math]\displaystyle{ p }[/math] 给所有图分配零概率，例如“ [math]\displaystyle{ \mathcal{P}(G)\neq\mathbf{p} }[/math] 。

特殊情况是条件均匀随机图 Conditionally Uniform Graph，其中 [math]\displaystyle{ p }[/math] 给所有具有指定性质的图赋予相等的概率。它们可以被看作是 Erdős–Rényi 模型 G(n，m)的一个推广，当条件信息不一定是边的个数 M，而是其他任意图性质 [math]\displaystyle{ \mathcal{P}(G) }[/math] 时。在这种情况下，很少有分析结果可用，就需要通过模拟来获得平均性质的经验分布。

相互依存图

在相互依存图中，一个网络（graph）中的节点依赖于其他网络来工作。因此，一个或多个图中的故障会导致图之间的级联故障 Cascading Failures，从而引起网络突然崩溃。[11][12]

历史

最早使用随机图模型的是海伦·霍尔·詹宁斯和雅各布·莫雷诺，他们在1938年提出了一个“偶然社会记录模型”(一个有向的 Erdős-Rényi 模型)[13] ，用来比较他们的网络数据中的回传链接的比例和随机模型。另一个被称为“随机网络 Random Net”的随机图模型应用是1951年 Solomonoff 和 Rapoport 使用的有向图模型，这些有向图具有固定的出度，并且随机选择附加到其他顶点。[14]

随机图的Erdős–Rényi 模型是由Paul Erdős和Alfréd Rényi于1959年发表的论文《随机图论》中首次提出的，Gilbert 在他的论文《随机图论》中独立定义了这一模型。[1]</ref> and independently by Gilbert in his paper "Random graphs".[15]

另请参见

References 参考文献

  1. ↑ Bollobás, Béla (2001). Random Graphs (2nd ed.). Cambridge University Press. 
  2. ↑ Frieze, Alan; Karonski, Michal (2015). Introduction to Random Graphs. Cambridge University Press. 
  3. ↑ Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd.
  4. ↑ Béla Bollobás, Probabilistic Combinatorics and Its Applications, 1991, Providence, RI: American Mathematical Society.
  5. ↑ 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
  6. ↑ Newman, M. E. J. (2010). Networks: An Introduction. Oxford. 
  7. ↑ Reuven Cohen and Shlomo Havlin (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press. http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php. 
  8. ↑ Shao, Shuai; Huang, Xuqing; Stanley, H Eugene; Havlin, Shlomo (2015). "Percolation of localized attack on complex networks". New Journal of Physics. 17 (2): 023049. arXiv:1412.3124. Bibcode:2015NJPh...17b3049S. doi:10.1088/1367-2630/17/2/023049. ISSN 1367-2630.
  9. ↑ Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (2003). "Generating correlated networks from uncorrelated ones". Phys. Rev. E. 67 (46107): 046107. arXiv:cond-mat/0212469. Bibcode:2003PhRvE..67d6107R. doi:10.1103/PhysRevE.67.046107. PMID 12786436.
  10. ↑ Van Bussel, Frank; Ehrlich, Christoph; Fliegner, Denny; Stolzenberg, Sebastian; Timme, Marc (2010). "Chromatic Polynomials of Random Graphs". J. Phys. A: Math. Theor. 43 (17): 175002. arXiv:1709.06209. Bibcode:2010JPhA...43q5002V. doi:10.1088/1751-8113/43/17/175002.
  11. ↑ Buldyrev, Sergey V.; Parshani, Roni; Paul, Gerald; Stanley, H. Eugene; Havlin, Shlomo (2010). "Catastrophic cascade of failures in interdependent networks". Nature. 464 (7291): 1025–1028. arXiv:1012.0206. Bibcode:2010Natur.464.1025B. doi:10.1038/nature08932. ISSN 0028-0836. PMID 20393559.
  12. ↑ Gao, Jianxi; Buldyrev, Sergey V.; Stanley, H. Eugene; Havlin, Shlomo (2011). "Networks formed from interdependent networks". Nature Physics. 8 (1): 40–48. Bibcode:2012NatPh...8...40G. CiteSeerX 10.1.1.379.8214. doi:10.1038/nphys2180. ISSN 1745-2473.
  13. ↑ Moreno, Jacob L; Jennings, Helen Hall (Jan 1938). "Statistics of Social Configurations". Sociometry. 1 (3/4): 342–374. doi:10.2307/2785588. JSTOR 2785588.
  14. ↑ Solomonoff, Ray; Rapopst, Anatol (June 1951). "Connectivity of random nets". Bulletin of Mathematical Biophysics. 13 (2): 107–117. doi:10.1007/BF02478357.
  15. ↑ Gilbert, E. N. (1959), "Random graphs", Annals of Mathematical Statistics, 30 (4): 1141–1144, doi:10.1214/aoms/1177706098.

模板:Stochastic processes

Category:图论

取自“https://wiki.swarma.org/index.php?title=随机图&oldid=18846”