更改

删除46字节 、 2020年11月21日 (六) 20:06
无编辑摘要
第7行: 第7行:  
==模型==
 
==模型==
   −
从一组 n 个孤立的顶点开始,在它们之间随机添加连续的边,这样就得到一个随机图。这个领域的研究的目的是确定在什么阶段图形的特殊性质可能出现<ref name = "Random Graphs2">[[Béla Bollobás]], ''Random Graphs'', 1985, Academic Press Inc., London Ltd.</ref>。不同的随机图模型在图上产生不同的概率分布。最常见的研究是由埃德加 · 吉尔伯特提出的,表示<math>G(n,M)</math> ,其中每个可能的边独立出现的概率为<math>0 <p< 1</math>。获得任意一个 m 边随机图的概率是 <math>p^m (1-p)^(N-m)</math > ,记号是 <math>N=\tbinom{n}{2}</math > 。<ref name = "Random Graphs3">[[Béla Bollobás]], ''Probabilistic Combinatorics and Its Applications'', 1991, Providence, RI: American Mathematical Society.</ref>
+
从一组 n 个孤立的顶点开始,在它们之间随机添加连续的边,这样就得到一个随机图。这个领域的研究的目的是确定在什么阶段图形的特殊性质可能出现<ref name = "Random Graphs2">Béla Bollobás, ''Random Graphs'', 1985, Academic Press Inc., London Ltd.</ref>。不同的随机图模型在图上产生不同的概率分布。最常见的研究是由埃德加 · 吉尔伯特提出的,表示<math>G(n,M)</math> ,其中每个可能的边独立出现的概率为<math>0 <p< 1</math>。获得任意一个 m 边随机图的概率是 <math>p^m (1-p)^(N-m)</math > ,记号是 <math>N=\tbinom{n}{2}</math > 。<ref name = "Random Graphs3">Béla Bollobás, ''Probabilistic Combinatorics and Its Applications'', 1991, Providence, RI: American Mathematical Society.</ref>
      第42行: 第42行:  
==性质==
 
==性质==
   −
随机图理论研究随机图的典型性质,即从特定分布中抽取的图的高概率性质。例如,我们可以要求一个给定的值 <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>。
      第109行: 第109行:       −
[[随机图]]的[[ER模型]]是由Paul Erdős和Alfréd Rényi于1959年发表的论文《随机图论》中首次提出的,Gilbert 在他的论文《随机图论》中独立定义了这一模型。<ref name ="On Random Graphs">[[Paul Erdős|Erdős, P.]] [[Alfréd Rényi|Rényi, A]] (1959) "On Random Graphs I" in Publ. Math. Debrecen 6, p.&nbsp;290&ndash;297 [http://www.renyi.hu/~p_erdos/1959-11.pdf]</ref><ref name = "Random graphs">{{citation |last= Gilbert |first= E. N. |authorlink=Edgar Gilbert|year=1959 |title=Random graphs |journal=Annals of Mathematical Statistics |volume= 30|issue= 4 |pages=1141–1144|doi=10.1214/aoms/1177706098 |doi-access=free }}.</ref>
+
[[随机图]]的[[ER模型]]是由Paul Erdős和Alfréd Rényi于1959年发表的论文《随机图论》中首次提出的,Gilbert 在他的论文《随机图论》中独立定义了这一模型。<ref name ="On Random Graphs">[[Paul Erdős|Erdős, P.]] [[Alfréd Rényi|Rényi, A]] (1959) "On Random Graphs I" in Publ. Math. Debrecen 6, p.&nbsp;290&ndash;297 [http://www.renyi.hu/~p_erdos/1959-11.pdf]</ref><ref name = "Random graphs">{{citation |last= Gilbert |first= E. N. |year=1959 |title=Random graphs |journal=Annals of Mathematical Statistics |volume= 30|issue= 4 |pages=1141–1144|doi=10.1214/aoms/1177706098 |doi-access=free }}.</ref>
    
==参见==
 
==参见==
7,129

个编辑