更改

跳到导航 跳到搜索
添加4字节 、 2020年9月6日 (日) 17:18
第118行: 第118行:  
The theory of random graphs studies typical properties of random graphs, those that hold with high probability for graphs drawn from a particular distribution.  For example, we might ask for a given value of <math>n</math> and <math>p</math> what the probability is that <math>G(n,p)</math> is connected.  In studying such questions, researchers often concentrate on the asymptotic behavior of random graphs&mdash;the values that various probabilities converge to as <math>n</math> grows very large. Percolation theory characterizes the connectedness of random graphs, especially infinitely large ones.
 
The theory of random graphs studies typical properties of random graphs, those that hold with high probability for graphs drawn from a particular distribution.  For example, we might ask for a given value of <math>n</math> and <math>p</math> what the probability is that <math>G(n,p)</math> is connected.  In studying such questions, researchers often concentrate on the asymptotic behavior of random graphs&mdash;the values that various probabilities converge to as <math>n</math> grows very large. Percolation theory characterizes the connectedness of random graphs, especially infinitely large ones.
   −
随机图理论研究随机图的典型性质,即从特定分布中抽取的图的高概率性质。例如,我们可以要求一个给定的值 < math >n</math > 和 < math >p</math > 什么是 < math >G(n,p)</math > 连接的概率。在研究这些问题时,研究人员往往集中在随机图的渐近行为上——各种概率收敛到的值变得非常大。'''<font color="#FF8000">渗流理论 Percolation Theory </font>'''刻画了随机图,特别是无穷大图的连通性。
+
随机图理论研究随机图的典型性质,即从特定分布中抽取的图的高概率性质。例如,我们可以要求一个给定的值 <math>n</math> 和 <math>p</math> 什么是 <math>G(n,p)</math> 连接的概率。在研究这些问题时,研究人员往往集中在随机图的渐近行为上——各种概率收敛到的值变得非常大。'''<font color="#FF8000">渗流理论 Percolation Theory </font>'''刻画了随机图,特别是无穷大图的连通性。
      第126行: 第126行:  
Percolation is related to the robustness of the graph (called also network).  Given a random graph of <math>n</math> nodes and an average degree <math>\langle k\rangle</math>. Next we remove randomly a fraction <math>1-p</math> of nodes and leave only a fraction <math>p</math>. There exists a critical percolation threshold <math>p_c=\tfrac{1}{\langle k\rangle}</math> below which the network becomes fragmented while above <math>p_c</math> a giant connected component exists.
 
Percolation is related to the robustness of the graph (called also network).  Given a random graph of <math>n</math> nodes and an average degree <math>\langle k\rangle</math>. Next we remove randomly a fraction <math>1-p</math> of nodes and leave only a fraction <math>p</math>. There exists a critical percolation threshold <math>p_c=\tfrac{1}{\langle k\rangle}</math> below which the network becomes fragmented while above <math>p_c</math> a giant connected component exists.
   −
'''<font color="#FF8000">渗流 Percolation </font>''' 与图形(也称为网络)的'''<font color="#FF8000">健壮性 Robustness </font>'''有关。给定一个随机图形,其中的节点是 <math>n</math> 和一个平均度 <math>\langle k\rangle</math> 。接下来我们随机移除一部分概率为<math>1-p</math>的节点,只留下一部分概率为<math>p</math>的节点。存在一个临界渗透阈值<math>p_c=\tfrac{1}{\langle k\rangle}</math>,当低于这个临界渗透阈值,网络变得支离破碎,而高于临界渗透阈值<math>p_c</math>的网络则存在一个巨大的'''<font color="#FF800">连接元件 Connected Component </font>'''(图论)。
+
'''<font color="#FF8000">渗流 Percolation </font>''' 与图形(也称为网络)的'''<font color="#FF8000">健壮性 Robustness </font>'''有关。给定一个随机图形,其中的节点是 <math>n</math> 和一个平均度 <math>\langle k\rangle</math> 。接下来我们随机移除一部分概率为 <math>1-p</math> 的节点,只留下一部分概率为 <math>p</math> 的节点。存在一个临界渗透阈值 <math>p_c=\tfrac{1}{\langle k\rangle}</math>,当低于这个临界渗透阈值,网络变得支离破碎,而高于临界渗透阈值 <math>p_c</math> 的网络则存在一个巨大的'''<font color="#FF800">连接元件 Connected Component </font>'''(图论)。
    
<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><ref name ="On Random Graphs" />
 
<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><ref name ="On Random Graphs" />
第136行: 第136行:  
Localized percolation refers to removing a node its neighbors, next nearest neighbors etc. until a fraction of <math>1-p</math> of nodes from the network is removed. It was shown that for random graph with Poisson distribution of degrees <math>p_c=\tfrac{1}{\langle k\rangle}</math> exactly as for random removal. For other types of degree distributions <math>p_c</math> for localized attack is different from random attack
 
Localized percolation refers to removing a node its neighbors, next nearest neighbors etc. until a fraction of <math>1-p</math> of nodes from the network is removed. It was shown that for random graph with Poisson distribution of degrees <math>p_c=\tfrac{1}{\langle k\rangle}</math> exactly as for random removal. For other types of degree distributions <math>p_c</math> for localized attack is different from random attack
   −
'''<font color="#FF8000">局部渗滤 Localized Percolation </font>'''指的是去除一个节点的邻居、次近邻等。直到网络节点的 <math>1-p</math> 的一部分被移除。结果表明,对于泊松分布为 <math>p_c=\tfrac{1{\langle k\rangle}</math> 的随机图,正如对于随机删除一样。对于其他类型的度分布,局部攻击和随机攻击是不同的。
+
'''<font color="#FF8000">局部渗滤 Localized Percolation </font>'''指的是去除一个节点的邻居、次近邻等。直到网络中概率为 <math>1-p</math> 的一部分节点被移除。结果表明,对于泊松分布为 <math>p_c=\tfrac{1{\langle k\rangle}</math> 的随机图,和随机删除是一样的。对于其他类型的度分布,局部攻击和随机攻击是不同的。
    
''(threshold functions, evolution of <math>\tilde G</math>)''
 
''(threshold functions, evolution of <math>\tilde G</math>)''
274

个编辑

导航菜单