更改

随机图 (查看源代码)

2020年9月6日 (日) 17:18的版本

添加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—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 > 连接的概率。在研究这些问题时，研究人员往往集中在随机图的渐近行为上——各种概率收敛到的值变得非常大。'''渗流理论 Percolation Theory '''刻画了随机图，特别是无穷大图的连通性。

+

随机图理论研究随机图的典型性质，即从特定分布中抽取的图的高概率性质。例如，我们可以要求一个给定的值 <math>n</math> 和 <math>p</math> 什么是 <math>G(n，p)</math> 连接的概率。在研究这些问题时，研究人员往往集中在随机图的渐近行为上——各种概率收敛到的值变得非常大。'''渗流理论 Percolation Theory '''刻画了随机图，特别是无穷大图的连通性。

第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 ''' 与图形(也称为网络)的'''健壮性 Robustness '''有关。给定一个随机图形，其中的节点是 <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>的网络则存在一个巨大的'''连接元件 Connected Component '''(图论)。

+

'''渗流 Percolation ''' 与图形(也称为网络)的'''健壮性 Robustness '''有关。给定一个随机图形，其中的节点是 <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> 的网络则存在一个巨大的'''连接元件 Connected Component '''(图论)。

<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 '''~~指的是去除一个节点的邻居、次近邻等。直到网络节点的~~ <math>1-p</math> ~~的一部分被移除。结果表明，对于泊松分布为~~ <math>p_c=\tfrac{1{\langle k\rangle}</math> ~~的随机图，正如对于随机删除一样。对于其他类型的度分布，局部攻击和随机攻击是不同的。~~

+

'''局部渗滤 Localized Percolation '''指的是去除一个节点的邻居、次近邻等。直到网络中概率为 <math>1-p</math> 的一部分节点被移除。结果表明，对于泊松分布为 <math>p_c=\tfrac{1{\langle k\rangle}</math> 的随机图，和随机删除是一样的。对于其他类型的度分布，局部攻击和随机攻击是不同的。

''(threshold functions, evolution of <math>\tilde G</math>)''

923397935

274

个编辑