第322行: |
第322行: |
| \frac{\mathbb E [k]}{n-1} u_1^{*n}(n-2),& n>1, \\ | | \frac{\mathbb E [k]}{n-1} u_1^{*n}(n-2),& n>1, \\ |
| u(0) & n=1, | | u(0) & n=1, |
− | \end{cases}</math>其中 <math>u(k)</math> 表示度分布且 <math>u_1(k)=\frac{(k+1)u(k+1)}{\mathbb E[k]}</math>。 The giant component can be destroyed by randomly removing the critical fraction <math>p_c</math> of all edges. This process is called [[Percolation theory|percolation on random networks]]. When the second moment of the degree distribution is finite, <math display="inline">\mathbb E [k^2]<\infty</math>, this critical edge fraction is given by<ref>{{Cite journal|last=Kryven|first=Ivan|date=2018-01-01|title=Analytic results on the polymerisation random graph model|journal=Journal of Mathematical Chemistry|language=en|volume=56|issue=1|pages=140–157|doi=10.1007/s10910-017-0785-1|issn=0259-9791|doi-access=free}}</ref> <math>p_c=1-\frac{\mathbb E[k]}{ \mathbb E [k^2] - \mathbb E[k]}</math>, and the [[Average path length|average vertex-vertex distance]] <math>l</math> in the giant component scales logarithmically with the total size of the network, <math>l = O(\log N) </math>.<ref name=":1" /> | + | \end{cases}</math>其中 <math>u(k)</math> 表示度分布且 <math>u_1(k)=\frac{(k+1)u(k+1)}{\mathbb E[k]}</math>。 通过随机移除临界比例<math>p_c</math>的边,可以摧毁超大连通分量。这个过程叫做 [[渗流理论|随机网络的渗流]]。当度分布的二阶矩是有限的,即<math display="inline">\mathbb E [k^2]<\infty</math>,这个边数的临界比例<ref>{{Cite journal|last=Kryven|first=Ivan|date=2018-01-01|title=Analytic results on the polymerisation random graph model|journal=Journal of Mathematical Chemistry|language=en|volume=56|issue=1|pages=140–157|doi=10.1007/s10910-017-0785-1|issn=0259-9791|doi-access=free}}</ref> <math>p_c=1-\frac{\mathbb E[k]}{ \mathbb E [k^2] - \mathbb E[k]}</math>, 且超大连通分量中 [[平均路径长度|顶点与顶点间的平均距离]] <math>l</math> 的大小和网络的总结点数呈对数关系, <math>l = O(\log N) </math>.<ref name=":1" />。 |
| | | |
− | In the directed configuration model, the degree of a node is given by two numbers, in-degree <math>k_\text{in}</math> and out-degree <math>k_\text{out}</math>, and consequently, the degree distribution is two-variate. The expected number of in-edges and out-edges coincides, so that <math display="inline">\mathbb E [k_\text{in}]=\mathbb E [k_\text{out}]</math>. The directed configuration model contains the [[giant component]] iff<ref>{{Cite journal|last=Kryven|first=Ivan|date=2016-07-27|title=Emergence of the giant weak component in directed random graphs with arbitrary degree distributions|journal=Physical Review E|volume=94|issue=1|pages=012315|doi=10.1103/PhysRevE.94.012315|pmid=27575156|arxiv=1607.03793|bibcode=2016PhRvE..94a2315K}}</ref><math display="block">2\mathbb{E}[k_\text{in}]
| + | 在有向配置模型中,节点的度取决于两个量,入度<math>k_\text{in}</math> 和出度 <math>k_\text{out}</math>,因此度分布是二维的。入度和出度的期望值相等,即 <math display="inline">\mathbb E [k_\text{in}]=\mathbb E [k_\text{out}]</math>。有向配置模型中包含[[超大连通分量]] iff<ref>{{Cite journal|last=Kryven|first=Ivan|date=2016-07-27|title=Emergence of the giant weak component in directed random graphs with arbitrary degree distributions|journal=Physical Review E|volume=94|issue=1|pages=012315|doi=10.1103/PhysRevE.94.012315|pmid=27575156|arxiv=1607.03793|bibcode=2016PhRvE..94a2315K}}</ref><math display="block">2\mathbb{E}[k_\text{in}] |
| \mathbb{E}[k_\text{in}k_\text{out}] | | \mathbb{E}[k_\text{in}k_\text{out}] |
| - \mathbb{E}[k_\text{in}] | | - \mathbb{E}[k_\text{in}] |
第331行: |
第331行: |
| \mathbb{E}[k_\text{in}^2] | | \mathbb{E}[k_\text{in}^2] |
| +\mathbb{E}[k_\text{in}^2] \mathbb{E}[k_\text{out}^2] | | +\mathbb{E}[k_\text{in}^2] \mathbb{E}[k_\text{out}^2] |
− | - \mathbb{E}[k_\text{in} k_\text{out}]^2 >0.</math>Note that <math display="inline">\mathbb E [k_\text{in}]</math> and <math display="inline">\mathbb E [k_\text{out}]</math> are equal and therefore interchangeable in the latter inequality. The probability that a randomly chosen vertex belongs to a component of size <math>n</math> is given by:<ref>{{Cite journal|last=Kryven|first=Ivan|date=2017-11-02|title=Finite connected components in infinite directed and multiplex networks with arbitrary degree distributions|journal=Physical Review E|volume=96|issue=5|pages=052304|doi=10.1103/PhysRevE.96.052304|pmid=29347790|arxiv=1709.04283|bibcode=2017PhRvE..96e2304K}}</ref><math display="block">h_\text{in}(n)=\frac{\mathbb E[k_{in}]}{n-1} \tilde u_\text{in}^{*n}(n-2), \;n>1, \; \tilde u_\text{in}=\frac{k_\text{in}+1}{\mathbb E[k_\text{in}]}\sum\limits_{k_\text{out}\geq 0}u(k_\text{in}+1,k_\text{out}),</math>for in-components, and | + | - \mathbb{E}[k_\text{in} k_\text{out}]^2 >0.</math>注意 <math display="inline">\mathbb E [k_\text{in}]</math> 和 <math display="inline">\mathbb E [k_\text{out}]</math> 是相等的,因此在后面的不等式中二者可交换。对于图中任意一个节点,它属于大小为<math>n</math>的子图的概率由下式给出:<ref>{{Cite journal|last=Kryven|first=Ivan|date=2017-11-02|title=Finite connected components in infinite directed and multiplex networks with arbitrary degree distributions|journal=Physical Review E|volume=96|issue=5|pages=052304|doi=10.1103/PhysRevE.96.052304|pmid=29347790|arxiv=1709.04283|bibcode=2017PhRvE..96e2304K}}</ref><math display="block">h_\text{in}(n)=\frac{\mathbb E[k_{in}]}{n-1} \tilde u_\text{in}^{*n}(n-2), \;n>1, \; \tilde u_\text{in}=\frac{k_\text{in}+1}{\mathbb E[k_\text{in}]}\sum\limits_{k_\text{out}\geq 0}u(k_\text{in}+1,k_\text{out}),</math>对于入分量, |
| | | |
| <math>h_\text{out}(n)=\frac{\mathbb E[k_\text{out}]}{n-1} \tilde u_\text{out}^{*n}(n-2), \;n>1, \;\tilde u_\text{out}=\frac{k_\text{out}+1}{\mathbb E[k_\text{out}]}\sum\limits_{k_\text{in}\geq0}u(k_\text{in},k_\text{out}+1), | | <math>h_\text{out}(n)=\frac{\mathbb E[k_\text{out}]}{n-1} \tilde u_\text{out}^{*n}(n-2), \;n>1, \;\tilde u_\text{out}=\frac{k_\text{out}+1}{\mathbb E[k_\text{out}]}\sum\limits_{k_\text{in}\geq0}u(k_\text{in},k_\text{out}+1), |
第337行: |
第337行: |
| </math> | | </math> |
| | | |
− | for out-components.
| + | 对于出分量。 |
| | | |
| === Watts–Strogatz small world model === | | === Watts–Strogatz small world model === |