更改

ER随机图模型 (查看源代码)

2020年4月27日 (一) 17:35的版本

添加69字节、 2020年4月27日 (一) 17:35

第64行：第64行：

==与渗流的关系==

在[http://wiki.swarma.net/index.php/%E6%B8%97%E6%B5%81%E6%A8%A1%E5%9E%8B 渗流理论]中，人们研究有限或无限的图，并随机删除连边（或连接）。因此，ER模型的过程实际就是[https://en.wikipedia.org/wiki/Complete_graph 完全图]上未加权连接的渗流。（所谓渗流，就是在加权的情况下以不同的权重移除节点和（或）连边）。渗流理论有很深的[https://en.wikipedia.org/wiki/Physics 物理学]根源，大部分研究都是在欧几里得空间中的[https://en.wikipedia.org/wiki/Lattice_(group) 格子]上进行的。np=1时，由巨连通分量向小连通分量的转变与这些图类似，但对格子来说，确定临界点很难。物理学家通常将对完全图的研究称为[https://en.wikipedia.org/wiki/Mean_field_theory 平均场理论]，因此ER模型的过程就是渗流的平均场情况。

−

人们在随机图的渗流上也做了许多重要研究。从物理学家的角度看，这仍是一个平均场模型，所以它常被看成一个通信网络，研究结果常用图的鲁棒性来表示。设一个随机图有n>>~~1个节点，平均度为~~<k>~~。从网络中随机删除1~~-~~p’个节点，仅保留一部分p’。存在渗流临界值~~<math>p'_c=\tfrac{1}{\langle k\rangle}</math>，使得低于该值时，网络变得支离破碎，而高于<math>p'_c</math>~~时，会有n阶巨连通分量存在。巨连通分量的相对大小P~~<sub>∞</sub>由下式给出<ref name="Erdos1960" /><ref name="er59">

+

人们在随机图的渗流上也做了许多重要研究。从物理学家的角度看，这仍是一个平均场模型，所以它常被看成一个通信网络，研究结果常用图的鲁棒性来表示。设一个随机图有<math>n>>1</math>个节点，平均度为<math><k></math>。从网络中随机删除<math>1-p'</math>个节点，仅保留一部分<math>p'</math>。存在渗流临界值<math>p'_c=\tfrac{1}{\langle k\rangle}</math>，使得低于该值时，网络变得支离破碎，而高于<math>p'_c</math>时，会有<math>n</math>阶巨连通分量存在。巨连通分量的相对大小</math>P<sub>∞</sub>由下式给出:<ref name="Erdos1960" /><ref name="er59">

{{cite journal |last1= Erdős |first1= P. |last2=Rényi |first2=A. |year=1959 |title=On Random Graphs. I |journal=Publicationes Mathematicae |volume= 6|issue= |pages=290–297 |id= |url=http://www.renyi.hu/~p_erdos/1959-11.pdf |accessdate= |quote= }}

</ref><ref name="b01">{{Cite book | last = Bollobás | first = B. | title = Random Graphs | publisher = Cambridge University Press| edition = 2nd | year = 2001|id= |url= |accessdate= |quote=

第73行：第73行：

.[https://en.wikipedia.org/wiki/Bibcode bibcode]:[http://adsabs.harvard.edu/abs/1976MPCPS..80..419B 1976MPCPS..80..419B]}}

</ref>

−

<math> P_\infty= p'[1-\exp(-\langle k \rangle P_\infty)]. \, </math>

+

:<math> P_\infty= p'[1-\exp(-\langle k \rangle P_\infty)]. \, </math>

==说明==

乐多多

763

个编辑