# ER随机图模型

## 定义

ER随机图模型有两个密切相关的版本。

• 在模型G(n, M)中，从n个节点、M个连边构成的所有图的集合里随机选择一个图。例如，在G(3, 2)模型中，3个节点和2个连边能构成三种可能的图，每种图的概率为1/3。
• 在模型G(n, p)中，随机连接节点构成一个图。图中每个连边彼此独立，连接的概率为p。等价地，拥有n个节点、M个连边的所有图具有相同的概率 $p^M (1-p)^{{n \choose 2}-M}$。


## 两种模型的比较

G(n, p)中可能的连边数为 $\binom{n}{2}p$，由大数定律G(n, p)中的每个图几乎必有大概这么多连边（假设可能的连边数趋于无穷）。因此，粗略的结果是如果pn2 → ∞，那么当 $M=\tbinom{n}{2} p$随着n的增加而增加时，G(n, p)将与G(n, M)有相似的表现。许多图的性质都是这样。如果P是满足对子图序单调的任意一种图的性质（即若A是B的子图且A满足P，则B也满足P），那么命题“G(n, p)中几乎所有图满足P”等价于“ $G(n, \tbinom{n}{2} p)$中几乎所有图满足P”（其中pn2 → ∞）。例如，当P是连通性时，或P是包含哈密顿圈的性质时，上述关系就成立。然而，它对非单调性质（如具有偶数连边的性质）未必成立。 如今在实际应用中，G(n, p)模型更加常用，部分原因是通过连边的独立性进行分析较为容易。

## G(n, p)的性质 $P(\deg(v) = k) = {n-1\choose k}p^k(1-p)^{n-1-k},$ $P(\deg(v) = k) \to \frac{(np)^k \mathrm{e}^{-np}}{k!} \quad \text{ as } n \to \infty \text{ and } np = \text{ constant },$


• 若np<1，则G(n, p)中的一个图几乎一定没有连通分量的大小大于O(log(n))。
• 若np=1，则G(n, p)中的一个图几乎必有最大的连通分量，其阶为n 2/3
• 若np→c>1，其中c为常数，则G(n, p)中的一个图几乎必有唯一的包含节点有限部分的巨连通集团。没有连通分量会有超过O(log(n))个节点。
• $p<\tfrac{(1-\varepsilon)\ln n} n$，则G(n, p)中的一个图几乎必有孤立节点，因而它是不连通的。
• 解析失败 (<math_output_error>): p>\tfrac{(1+\varepsilon)\ln n} n

，则G(n, p)中的一个图几乎一定是连通的。 因此 $\tfrac{\ln n} n$是G(n, p)连通性的重要临界值。 当n趋于无穷大时，还有许多图的性质几乎处处成立。例如，存在k(n)（近似等于2log 2 (n)）使得G(n, 0.5)中最大团的大小几乎必为k(n)或k(n)+1。 因此，尽管确定图中最大团的大小是NP完全的，但“典型”图中最大团的大小（根据此模型）是非常好理解的。 ER图的连边对偶图是几乎有着相同度分布的图，但具有度相关性，且集聚系数更高。

## 与渗流的关系 $P_\infty= p'[1-\exp(-\langle k \rangle P_\infty)]. \,$


## 说明

G(n, p)模型的两个主要假设（连边独立，每条连边可能性相同）可能不适合为某些现实生活中的现象建模。尤其是ER图的度分布没有厚尾，而许多实际网络的分布是厚尾的。此外，与许多社交网络不同，ER图集聚系数较低。其他较好的替代模型可见 BA模型（Barabási–Albert model）和WS小世界网络模型（Watts and Strogatz model）。这两个替代模型不是渗流过程，它们分别是生长模型和断边重连模型。Buldyrev（布尔德列夫）等人最近又设计了一种用于交互的ER网络模型。

## 历史

1959年，Edgar Gilbert在研究之前提到的连通性临界值的论文中，首次引入了G(n, p)模型。G(n, M)模型则是Erdős和Rényi在他们1959年的论文中提出来的。与Gilbert一样，他们首先研究的是G(n, M)的连通性，1960年，他们做了更详细的分析。

## 另请参阅

• 双相演化（Dual-phase evolution）描述了与ER模型相关的性质推动系统中秩序出现的方式。
• 指数随机图模型（Exponential random graph models）描述的是给定网络统计数据和各种相关参数的“n”节点图的一般概率分布。
• 随机块模型（Stochastic block model），是ER模型的推广，是具有潜在社团结构的图。
• WS小世界网络模型
• BA模型

## 参考文献

1. Erdős, P.; Rényi, A. (1959). "On Random Graphs. I". Publicationes Mathematicae 6: 290–297.
2. Bollobás, B. (2001). Random Graphs (2nd ed.). Cambridge University Press. ".ISBN 0-521-79722-5"
3. E.N. Gilbert (1959). "Random Graphs". Annals of Mathematical Statistics 30 (4): 1141–1144. ".doi:10.1214/aoms/1177706098"
4. Newman, Mark. E. J.; Strogatz, S. H.; Watts, D. J. (2001). "Random graphs with arbitrary degree distributions and their applications". Physical Review E 64: 026118. ".doi:10.1103/PhysRevE.64.026118 .arxiv:cond-mat/0007235 .bibcode:2001PhRvE..64b6118N", Eq. (1)
5. Erdős, P.; Rényi, A. (1960). "On the evolution of random graphs". Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Publications of the Mathematical Institute of the Hungarian Academy of Sciences] 5: 17–61. 这里的概率p指的是 $N(n) = \tbinom{n}{2} p$
6. Matula, David W. (February 1972). "The employee party problem". Notices of the American Mathematical Society 19: A-382.
7. Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (April 2003). "Generating correlated networks from uncorrelated ones". Physical Review E 67 (4): 046107 .doi:10.1103/PhysRevE.67.046107 .arxiv:cond-mat/0212469 .bibcode:2003PhRvE..67d6107R.
8. Bollobás, B.; Erdős, P. (1976). "Cliques in Random Graphs". Mathematical Proceedings of the Cambridge Philosophical Society 80 (3): 419–427. ".doi:10.1017/S0305004100053056 .bibcode:1976MPCPS..80..419B"
9. Buldyrev, S. V.; Parshani, R.; Paul, G.; Stanley, H. E.; Havlin, S. (2010). "Catastrophic cascade of failures in interdependent networks". Nature 464 (7291): 1025–8. ".doi:10.1038/nature08932 .PMID:20393559 .arxiv:0907.1182 .bibcode:2010Natur.464.1025B"
{"ft_lang_label":"__label__zh","ft_lang_prob":0.8348888,"math_prob":0.9687248,"size":5075,"snap":"2020-24-2020-29","text_gpt3_token_len":3554,"char_repetition_ratio":0.07493591,"word_repetition_ratio":0.0,"special_character_ratio":0.2987192,"punctuation_ratio":0.2338362,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98082113,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],"im_url_duplicate_count":[null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null,2,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-07-11T05:54:55Z\",\"WARC-Record-ID\":\"<urn:uuid:938e17fc-234c-493f-b435-1ac364706488>\",\"Content-Length\":\"45268\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:4c986b2a-4012-4c2f-978c-1f0b14c7489e>\",\"WARC-Concurrent-To\":\"<urn:uuid:a8dbd91f-2fba-4a24-8174-85e8d9f03376>\",\"WARC-IP-Address\":\"139.129.106.176\",\"WARC-Target-URI\":\"http://wiki.caiyunapp.com/index.php?title=ER%E9%9A%8F%E6%9C%BA%E5%9B%BE%E6%A8%A1%E5%9E%8B&oldid=20236\",\"WARC-Payload-Digest\":\"sha1:UCBNYNFK77OJMAWUUGN3RHGMZRDJA5GN\",\"WARC-Block-Digest\":\"sha1:FC7XOSZMZYOIESSSOGJKLYZRSBBUIIEU\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-29/CC-MAIN-2020-29_segments_1593655921988.66_warc_CC-MAIN-20200711032932-20200711062932-00297.warc.gz\"}"}