查看“︁随机图”︁的源代码

在[[數學]]中，'''随机图'''是指由[[随机过程]]产生的[[图_(数学)|图]]<ref>[[Béla Bollobás]], ''Random Graphs'', 2nd Edition, 2001, Cambridge University Press</ref>。随机图的理论处于[[图论]]和[[概率论]]的交叉地带，主要研究各种经典随机图的性质。随机图的实际应用主要在[[复杂网络]]中所有建模领域中。第一批关于随机图的结果是[[保罗·埃尔德什]]和[[阿尔弗雷德·雷尼]]在1959年至1966年的一系列论文中提出的[[ER随机图]]。<ref>第一篇论文发表于1959年，标题为“''On Random Graphs I''”（《论随机图 I》），Publ. Math. Debrecen 6, p290.</ref>。在其他语义中，任何图模型都可以被称为随机图。

==定义与模型==
随机图的“随机”二字体现在边的分布上。一个随机图实际上是将给定的顶点之间随机地连上边。假设将一些纽扣散落在地上，并且不断随机地将两个纽扣之间系上一条线，这样就得到一个随机图的例子<ref name="wxf">{{cite book | title =《复杂网络理论及其应用》 | author =汪小帆,李翔,陈关荣 | publisher = 清华大学出版社  | year = 2006| isbn =9787302125051 | language = zh}}</ref>。边的产生可以依赖于不同的随机方式，这样就产生了不同的随机图模型。最常被讨论的模型是Edgar Gilbert提出的 ''G''(''n'',''p'')模型：''p''为'''边概率'''，即''G''中任意两个顶点之间相连的概率。在这种模型下，一个特定的图出现的概率为<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>.

与''G''(''n'',''p'')模型紧密相关的模型是[[保罗·埃尔德什|埃尔德什]]和[[阿尔弗雷德・雷尼|雷尼]]共同研究的'''ER模型'''，表示为''G''(''n'',''M'')：拥有''M''个边的图出现概率是相同的。当0 ≤ ''M'' ≤ ''N'', ''G''(''n'',''M'') 总共有<math>\tbinom{N}{M}</math>种可能的确定图，每种图出现的概率是<math>1/\tbinom{N}{M}</math><ref name = "Random Graphs2">[[Béla Bollobás]], ''Random Graphs'', 1985, Academic Press Inc., London Ltd.</ref>。若将随机图的生成过程描述为一个[[随机过程]]：开始时有''n''个顶点且互相没有边连接，每次迭代都从缺失的边集合中均匀的选择一条新边；那么ER模型可以被看作是随机图生成过程中迭代''M''次时的一个快照。

另一种随机图模型叫做'''内积模型'''，是Gilbert''G''(''n'',''p'')模型的推广形式。[[内积]]模型的机制是对每一个顶点指定一个[[实数|实]]系数的[[向量]]，而两个顶点之间是否连接的概率则是它们的向量的内积的函数。

定义更广泛的随机图模型的方法是定义所谓的网络概率矩阵。这个矩阵的系数就是'''边概率'''，因此详细刻画了随机图的模型。网络概率矩阵模型可以推广到有向图和带有权重的图。

[[随机正则图]]是随机图中特殊的一类，它的性质可能会与一般的随机图不同。

==性质==
随着边概率的不同，随机图可能会呈现不同的属性。对于最典型的ER模型，埃尔德什与雷尼研究了当顶点数目 ''n'' 趋向于正无穷大时，ER随机图的性质与概率 ''p'' 之间的关系。他们发现，当 ''p'' 的值越过某些门槛时，ER随机图的性质会发生突然的改变<ref name="wxf"/>。ER随机图的许多性质都是突然涌现的，比如说，当 ''p'' 的值小于某个特殊值之前，随机图具有某个性质的可能性等于0，但当 ''p'' 的值大于这个特殊值以后，随机图具有这个性质的可能性会突然变成1。

举例来说，当概率 ''p'' 大于某个临界值 ''p''<sub>c</sub>(''n'') 后，生成的随机图几乎必然是连通的（概率等于1）。也就是说，对于散落在地上的 ''n'' 个纽扣，如果你以这样的概率 ''p'' 将两个纽扣之间系上线，那么你拿起一颗纽扣时就几乎能带起所有的纽扣了<ref name="wxf"/>。

==随机树==
{{main|隨機樹}}

随机树是随机图的一类。如同随机图一样，随机树是一个经由随机过程建立的[[树 (图论)|树]]或[[有向树]]。随机数的类型包括[[随机最小生成树]]、[[随机二叉树]]、[[随机二叉查找树]]和[[随机森林]]等。

当顶点数''n''较大时，顶点数目为''k''的随机树的分布接近于[[泊松分布]]。

随机树的一种生成方法是利用随机置换。首先生成一个 <math>\scriptstyle \frac{n}{2}(n-1)</math> 阶随机[[置换]]函数，将 <math>\scriptstyle \frac{n}{2}(n-1)</math> 个可能连起来的边标上 1 至 <math>\scriptstyle \frac{n}{2}(n-1)</math> 的序号。然后按照从小到大的序号排列为原本没有边的图一一添加边。添加第 <math>\scriptstyle k</math> 条边时，如果发现添加后会导致图中出现一个[[连通图|圈]]，那么就放弃添加这条边，而开始添加第 <math>\scriptstyle k+1</math> 条边。最后得到的就是一个随机树<ref>{{cite web | title =The Random Tree Process | url =http://dimax.rutgers.edu/~alexak/tree_process.html | author =Alexandr Kazda | publisher =Center for Discrete Mathematics and Theoretical Computer Science | accessdate =2011-04-24 | archive-date =2016-03-04 | archive-url =https://web.archive.org/web/20160304230239/http://dimax.rutgers.edu/~alexak/tree_process.html }}</ref>。

==参见==
* [[玻色-爱因斯坦凝聚]]
* [[腔体法]]
* [[复杂网络]]
* [[小世界网络]]
* [[无尺度网络]]
*[[ER随机图]]

==参考来源==
{{reflist}}

{{Stochastic processes}}

[[Category:图论]]
[[Category:随机图]]
[[Category:随机过程]]

[[nl:Complexe netwerken#Random netwerken]]