421
个编辑
更改
跳到导航
跳到搜索
第35行：
第35行： − + − +
→性质
==性质==
==性质==
随机图理论研究随机图的典型性质，即从特定分布中抽取的图的高概率性质。例如，我们可以要求一个给定的值 <math>n</math> 和 <math>p</math> <math>G(n，p)</math> 连接的概率。在研究这些问题时，研究人员往往集中在随机图的趋近行为上——各种概率收敛到的值变得非常大。'''渗流理论 Percolation Theory'''刻画了随机图，特别是无穷大图的'''连通性 Connectedness'''。
随机图理论研究随机图的典型性质，即从特定分布中抽取的图的高概率性质。例如，我们可以要求一个给定的值 <math>n</math> 和 <math>p</math>来表示<math>G(n，p)</math> 连接的概率。在研究这些问题时，研究人员往往集中在随机图的趋近行为上——各种概率收敛到的值变得非常大。'''[[渗流理论]] Percolation Theory'''刻画了随机图，特别是无穷大图的'''连通性 Connectedness'''。
'''渗流 Percolation''' 与图形(也称为网络)的'''紧密性 Robustness'''有关。给定一个随机图形，其中的节点是 <math>n</math> 和一个平均度 <math>\langle k\rangle</math> 。接下来我们随机移除一部分概率为 <math>1-p</math> 的节点，只留下一部分概率为 <math>p</math> 的节点。存在一个'''临界渗透阈值 Critical Percolation Threshold'''<math>p_c=\tfrac{1}{\langle k\rangle}</math>，当低于这个临界渗透阈值，网络变得支离破碎，而高于临界渗透阈值 <math>p_c</math> 的网络则存在一个巨大的''连接元件 Connected Component'''(图论)<ref>{{cite book |title=Networks: An Introduction |last= Newman |first=M. E. J. |year= 2010 |publisher= Oxford}}</ref><ref>{{cite book |title= Complex Networks: Structure, Robustness and Function |authors= Reuven Cohen and [[Shlomo Havlin]] |year= 2010 |url= http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php |publisher= Cambridge University Press}}</ref>。
'''渗流 Percolation''' 与图形(也称为网络)的'''鲁棒性 Robustness'''有关。给定一个随机图形，其中的节点是 <math>n</math> 和一个平均度 <math>\langle k\rangle</math> 。接下来我们随机移除一部分概率为 <math>1-p</math> 的节点，只留下一部分概率为 <math>p</math> 的节点。存在一个'''临界渗透阈值 Critical Percolation Threshold'''<math>p_c=\tfrac{1}{\langle k\rangle}</math>，当低于这个临界渗透阈值，网络变得支离破碎，而高于临界渗透阈值 <math>p_c</math> 的网络则存在一个巨大的''连接元件 Connected Component'''(图论)<ref>{{cite book |title=Networks: An Introduction |last= Newman |first=M. E. J. |year= 2010 |publisher= Oxford}}</ref><ref>{{cite book |title= Complex Networks: Structure, Robustness and Function |authors= Reuven Cohen and [[Shlomo Havlin]] |year= 2010 |url= http://havlin.biu.ac.il/Shlomo%20Havlin%20books_com_net.php |publisher= Cambridge University Press}}</ref>。
'''局部渗滤 Localized Percolation'''指的是去除一个节点的邻居、次近邻等。直到网络中概率为 <math>1-p</math> 的一部分节点被移除。结果表明，对于服从泊松分布的随机图，其度分布为 <math>p_c=\tfrac{1}{\langle k\rangle}</math> ，和随机删除是一样的。对于其他类型的度分布 <math>p_c</math>，局部攻击和随机攻击是不同的。<ref name="ShaoHuang2015">{{cite journal|last1=Shao|first1=Shuai|last2=Huang|first2=Xuqing|last3=Stanley|first3=H Eugene|last4=Havlin|first4=Shlomo|title=Percolation of localized attack on complex networks|journal=New Journal of Physics|volume=17|issue=2|year=2015|pages=023049|issn=1367-2630|doi=10.1088/1367-2630/17/2/023049|arxiv=1412.3124|bibcode=2015NJPh...17b3049S}}</ref>
'''局部渗滤 Localized Percolation'''指的是去除一个节点的邻居、次近邻等。直到网络中概率为 <math>1-p</math> 的一部分节点被移除。结果表明，对于服从泊松分布的随机图，其度分布为 <math>p_c=\tfrac{1}{\langle k\rangle}</math> ，和随机删除是一样的。对于其他类型的度分布 <math>p_c</math>，局部攻击和随机攻击是不同的。<ref name="ShaoHuang2015">{{cite journal|last1=Shao|first1=Shuai|last2=Huang|first2=Xuqing|last3=Stanley|first3=H Eugene|last4=Havlin|first4=Shlomo|title=Percolation of localized attack on complex networks|journal=New Journal of Physics|volume=17|issue=2|year=2015|pages=023049|issn=1367-2630|doi=10.1088/1367-2630/17/2/023049|arxiv=1412.3124|bibcode=2015NJPh...17b3049S}}</ref>