第308行: |
第308行: |
| | | |
| === Erdős–Rényi 随机图模型 === | | === Erdős–Rényi 随机图模型 === |
| + | [[File:ER model.svg|thumb|This [[Erdős–Rényi model]] is generated with {{math|<VAR>N</VAR> {{=}} 4}} nodes. For each edge in the complete graph formed by all {{mvar|N}} nodes, a random number is generated and compared to a given probability. If the random number is less than {{mvar|p}}, an edge is formed on the model.]] |
| + | The '''[[Erdős–Rényi model]]''', named for [[Paul Erdős]] and [[Alfréd Rényi]], is used for generating [[random graph]]s in which edges are set between nodes with equal probabilities. It can be used in the [[probabilistic method]] to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs. |
| + | |
| + | To generate an Erdős–Rényi model <math>G(n, p) |
| + | |
| + | </math> two parameters must be specified: the total number of nodes {{mvar|n}} and the probability {{mvar|p}} that a random pair of nodes has an edge. |
| + | |
| + | Because the model is generated without bias to particular nodes, the degree distribution is binomial: for a randomly chosen vertex <math>v</math>, |
| + | : <math>P(\deg(v) = k) = {n-1\choose k} p^k (1-p)^{n-1-k}.</math> |
| + | |
| + | In this model the clustering coefficient is {{math|0}} [[Almost surely|a.s]]. The behavior of <math>G(n, p) |
| + | |
| + | </math> can be broken into three regions. |
| + | |
| + | ''Subcritical'' <math>n p < 1 |
| + | |
| + | </math>: All components are simple and very small, the largest component has size <math>|C_1| = O(\log n) |
| + | |
| + | </math>; |
| + | |
| + | ''Critical'' <math>n p = 1 |
| + | |
| + | </math>: <math>|C_1| = O(n^\frac{2}{3}) |
| + | |
| + | </math>; |
| + | |
| + | ''Supercritical'' <math>n p >1 |
| + | |
| + | </math>:<math>|C_1| \approx yn |
| + | </math> where <math>y = y(n p) |
| + | |
| + | </math> is the positive solution to the equation <math>e^{-p n y }=1-y |
| + | |
| + | </math>. |
| + | |
| + | The largest connected component has high complexity. All other components are simple and small <math>|C_2| = O(\log n) |
| + | |
| + | </math>. |
| + | |
| | | |
| 以[[Paul Erdős]]和[[Alfréd Rényi]]命名的'''[[Erdős–Rényi 模型]]'''用于生成[[随机图]],它的边是等概率连接的节点的集合。[[随机图]]可以用来证明[[概率方法]]中满足某些条件的图的存在性,或者对几乎所有图给出某个性质的严格定义。 | | 以[[Paul Erdős]]和[[Alfréd Rényi]]命名的'''[[Erdős–Rényi 模型]]'''用于生成[[随机图]],它的边是等概率连接的节点的集合。[[随机图]]可以用来证明[[概率方法]]中满足某些条件的图的存在性,或者对几乎所有图给出某个性质的严格定义。 |