更改

网络科学 (查看源代码)

2020年5月23日 (六) 14:33的版本

添加25字节、 2020年5月23日 (六) 14:33

第359行：第359行：

for out-components.

−

配置模型以一个度序列<ref>{{Cite journal|last=Bender|first=Edward A|last2=Canfield|first2=E.Rodney|date=May 1978|title=The asymptotic number of labeled graphs with given degree sequences|journal=Journal of Combinatorial Theory, Series A|volume=24|issue=3|pages=296–307|doi=10.1016/0097-3165(78)90059-6|issn=0097-3165}}</ref><ref name=":0">{{Cite journal|last=Molloy|first=Michael|last2=Reed|first2=Bruce|date=March 1995|title=A critical point for random graphs with a given degree sequence|journal=Random Structures & Algorithms|language=en|volume=6|issue=2–3|pages=161–180|doi=10.1002/rsa.3240060204|issn=1042-9832|citeseerx=10.1.1.24.6195}}</ref> 或度分布<ref name=":1">{{Cite journal|last=Newman|first=M. E. J.|last2=Strogatz|first2=S. H.|last3=Watts|first3=D. J.|date=2001-07-24|title=Random graphs with arbitrary degree distributions and their applications|journal=Physical Review E|volume=64|issue=2|pages=026118|doi=10.1103/PhysRevE.64.026118|pmid=11497662|arxiv=cond-mat/0007235|bibcode=2001PhRvE..64b6118N}}</ref> （用于生成度序列）作为输入, 生成除了度序列外各方面随机连接的图。这意味着对于给定的度序列，图是一致随机地从符合这个度序列的所有图的集合中选择的。图中任意节点的度<math>k</math>是一个[[独立同分布|独立同分布]]的随机变量，其值为整数。当 <math display="inline">\mathbb E [k^2] - 2 \mathbb E [k]>0</math> 时，配置图包含[[超大分量|超大连通分量]]，其大小是无穷。<ref name=":0" /> 其他分量大小是有限的，可以用大小分布来定量表示。图中任意取的一个节点和大小为<math>n</math>~~的分量相连接的概率由度分布的~~[[卷积幂]]给出：<ref>{{Cite journal|last=Kryven|first=Ivan|date=2017-05-02|title=General expression for the component size distribution in infinite configuration networks|journal=Physical Review E|volume=95|issue=5|pages=052303|doi=10.1103/PhysRevE.95.052303|pmid=28618550|arxiv=1703.05413|bibcode=2017PhRvE..95e2303K}}</ref><math display="block">w(n)=\begin{cases}

+

配置模型以一个度序列<ref>{{Cite journal|last=Bender|first=Edward A|last2=Canfield|first2=E.Rodney|date=May 1978|title=The asymptotic number of labeled graphs with given degree sequences|journal=Journal of Combinatorial Theory, Series A|volume=24|issue=3|pages=296–307|doi=10.1016/0097-3165(78)90059-6|issn=0097-3165}}</ref><ref name=":0">{{Cite journal|last=Molloy|first=Michael|last2=Reed|first2=Bruce|date=March 1995|title=A critical point for random graphs with a given degree sequence|journal=Random Structures & Algorithms|language=en|volume=6|issue=2–3|pages=161–180|doi=10.1002/rsa.3240060204|issn=1042-9832|citeseerx=10.1.1.24.6195}}</ref> 或度分布<ref name=":1">{{Cite journal|last=Newman|first=M. E. J.|last2=Strogatz|first2=S. H.|last3=Watts|first3=D. J.|date=2001-07-24|title=Random graphs with arbitrary degree distributions and their applications|journal=Physical Review E|volume=64|issue=2|pages=026118|doi=10.1103/PhysRevE.64.026118|pmid=11497662|arxiv=cond-mat/0007235|bibcode=2001PhRvE..64b6118N}}</ref> （用于生成度序列）作为输入，生成除了度序列外各方面随机连接的图。这意味着对于给定的度序列，图是从符合这个度序列的所有图的集合中随机均匀地选择的。图中任意节点的度<math>k</math>是一个[[独立同分布|独立同分布]]的随机变量，其值为整数。当 <math display="inline">\mathbb E [k^2] - 2 \mathbb E [k]>0</math> 时，配置图包含[[超大分量|超大连通分量]]，其大小是无穷。<ref name=":0" /> 其他分量大小是有限的，可以用大小分布来定量表示。图中任意取的一个节点和大小为<math>n</math>的分量相连接的概率 <math>w(n)</math> 由度分布的[[卷积幂]]给出：<ref>{{Cite journal|last=Kryven|first=Ivan|date=2017-05-02|title=General expression for the component size distribution in infinite configuration networks|journal=Physical Review E|volume=95|issue=5|pages=052303|doi=10.1103/PhysRevE.95.052303|pmid=28618550|arxiv=1703.05413|bibcode=2017PhRvE..95e2303K}}</ref><math display="block">w(n)=\begin{cases}

\frac{\mathbb E [k]}{n-1} u_1^{*n}(n-2),& 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>。通过随机移除临界比例<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" />。

+

\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" />。

在有向配置模型中，节点的度取决于两个量，入度<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}]

第371行：第371行：

\mathbb{E}[k_\text{in}^2]

+\mathbb{E}[k_\text{in}^2] \mathbb{E}[k_\text{out}^2]

−

- \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>~~对于入分量，~~

+

- \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) </math>。

−

</math>

−

~~对于出分量。~~

=== Watts–Strogatz 小世界模型 ===

苏格兰

198

个编辑