更改

从一组 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> 相邻。

随机图理论研究随机图的典型性质，即从特定分布中抽取的图的高概率性质。例如，我们可以要求一个给定的值 <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>

:<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>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'''。特别是，在几乎每个随机图中，最后一个孤立点消失的那一刻，图会变连通。

==条件随机图==

==条件随机图==

考虑一个给定的随机图模型定义在概率空间上<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> 。  

==另请参见==

==另请参见==

* [[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}}

[[Category:图论]]

[[Category:图论]]