7,129
个编辑
更改
跳到导航
跳到搜索
第10行：
第10行： + + + + + + + + + + + + + + + 第52行：
第67行： + + + + + + + + + + + + +
无编辑摘要
从一组 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>
一个相关性强的模型，Erdős-Rényi模型表示<math>G(n,M)</math> ，给每一个正好有''M''条边的图赋予等概率。当<math>0≤ M ≤ N</math>时，<math>G(n,M)</math>具有 <math>\tbinom{N}{M}</math> 元素，且每个元素都以概率<math>1/\tbinom{N}{M}</math> 出现。后一个模型可以看作是随机图过程<math>\tilde{G}_n</math>某个特定时间（'' M ''）的一个快照，这个时间（'' M ''）是从 <math>n</math> 个顶点开始没有边的一个随机过程，每个步骤均匀地从缺失的边集中选择一个新的边。
一个相关性强的模型，Erdős-Rényi模型表示<math>G(n,M)</math> ，给每一个正好有''M''条边的图赋予等概率。当<math>0≤ M ≤ N</math>时，<math>G(n,M)</math>具有 <math>\tbinom{N}{M}</math> 元素，且每个元素都以概率<math>1/\tbinom{N}{M}</math> 出现。后一个模型可以看作是随机图过程<math>\tilde{G}_n</math>某个特定时间（'' M ''）的一个快照，这个时间（'' M ''）是从 <math>n</math> 个顶点开始没有边的一个随机过程，每个步骤均匀地从缺失的边集中选择一个新的边。
如果我们从一个无限的顶点集合开始，然后再次让每个可能的边以概率<math>0<p< 1</math>独立出现，那么我们得到一个对象 <math>G</math> 称为'''无限随机图 Infinite Graph'''。除了在 <math>p = 0</math>或1的平凡情况下，这样的 <math>G</math> 在大多数情况下肯定具有以下性质:
如果我们从一个无限的顶点集合开始，然后再次让每个可能的边以概率<math>0<p< 1</math>独立出现，那么我们得到一个对象 <math>G</math> 称为'''无限随机图 Infinite Graph'''。除了在 <math>p = 0</math>或1的平凡情况下，这样的 <math>G</math> 在大多数情况下肯定具有以下性质:
*<blockquote>在 <math>v</math> 中，给定任何 <math>n + m</math> 个元素，<math>a_1,\ldots, a_n,b_1,\ldots, b_m \in V</math> 中有一个顶点<math>c</math>，它与每个 <math>a_1,\ldots,a_n</math> 相邻，并且不与任何 <math>b_1,\ldots,b_m</math> 相邻。</blockquote>
*<blockquote>在 <math>v</math> 中，给定任何 <math>n + m</math> 个元素，<math>a_1,\ldots, a_n,b_1,\ldots, b_m \in V</math> 中有一个顶点<math>c</math>，它与每个 <math>a_1,\ldots,a_n</math> 相邻，并且不与任何 <math>b_1,\ldots,b_m</math> 相邻。</blockquote>
结果表明，如果顶点集是可数的，那么在'''同构 Isomorphism'''意义下，只有一个图具有这个性质，即 Rado 图。因此，任何可数无限随机图几乎可以肯定是 Rado 图，由于这个原因，有时被简称为随机图。然而，对于'''不可数图 Uncountable Graph'''类似的结果是不正确的，不可数图中有许多'''不同构图 Nonisomorphic Graph'''满足上述性质。
结果表明，如果顶点集是可数的，那么在'''同构 Isomorphism'''意义下，只有一个图具有这个性质，即 Rado 图。因此，任何可数无限随机图几乎可以肯定是 Rado 图，由于这个原因，有时被简称为随机图。然而，对于'''不可数图 Uncountable Graph'''类似的结果是不正确的，不可数图中有许多'''不同构图 Nonisomorphic Graph'''满足上述性质。
另一个模型，概括了吉尔伯特的随机图模型，是'''随机点积模型 Random Dot-product Model'''。一个'''随机点积图 Random Dot-product Graph''' 将每个顶点与一个实向量相关联。任意顶点 <math>u</math> 和 <math>v</math>之间的边 <math>uv</math> 的概率是它们各自向量的点积 <math>u·v</math> 的某个函数。
另一个模型，概括了吉尔伯特的随机图模型，是'''随机点积模型 Random Dot-product Model'''。一个'''随机点积图 Random Dot-product Graph''' 将每个顶点与一个实向量相关联。任意顶点 <math>u</math> 和 <math>v</math>之间的边 <math>uv</math> 的概率是它们各自向量的点积 <math>u·v</math> 的某个函数。
'''网络转移矩阵 NetWork Probability Matrix'''通过边概率对随机图进行建模，这些边概率代表给定的边存在一个特定的时间段的概率。这个模型可以扩展到有向和无向，加权和无权，以及静态或动态的图形结构。
'''网络转移矩阵 NetWork Probability Matrix'''通过边概率对随机图进行建模，这些边概率代表给定的边存在一个特定的时间段的概率。这个模型可以扩展到有向和无向，加权和无权，以及静态或动态的图形结构。
对于 ''M''something ''pN''，其中 ''N'' 是可能的最大边数，两个最广泛使用的模型，<math>G(n,M)</math>和 <math>G(n,p)</math>在大多数情况下是可互换的<ref name ="Handbook ">[[Béla Bollobás|Bollobas, B.]] and Riordan, O.M. "Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003</ref>。
对于 ''M''something ''pN''，其中 ''N'' 是可能的最大边数，两个最广泛使用的模型，<math>G(n,M)</math>和 <math>G(n,p)</math>在大多数情况下是可互换的<ref name ="Handbook ">[[Béla Bollobás|Bollobas, B.]] and Riordan, O.M. "Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003</ref>。
'''随机正则图 Random Regular Graph'''是一种特殊情况，其性质可能与一般随机图不同。
'''随机正则图 Random Regular Graph'''是一种特殊情况，其性质可能与一般随机图不同。
一旦我们有了一个随机图的模型，图上的每个函数都变成了一个随机变量。对这个模型的研究是为了确定，或者至少估计一个属性可能发生的概率。
一旦我们有了一个随机图的模型，图上的每个函数都变成了一个随机变量。对这个模型的研究是为了确定，或者至少估计一个属性可能发生的概率。
==术语==
==术语==
在随机图的上下文中，“几乎每一个”这个术语指的是一系列空间和概率，使得出错概率趋于零。
在随机图的上下文中，“几乎每一个”这个术语指的是一系列空间和概率，使得出错概率趋于零。
==性质==
==性质==
随机图理论研究随机图的典型性质，即从特定分布中抽取的图的高概率性质。例如，我们可以要求一个给定的值 <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>
''('''阈值函数 Threshold Functions''', <math>\tilde G</math> 的演化)''
''('''阈值函数 Threshold Functions''', <math>\tilde G</math> 的演化)''
随机图在概率方法中得到了广泛的应用，它试图证明具有一定性质的图的存在性。通过 '''正则引理 Szemerédi Regularity Lemma'''，随机图上一个性质的存在常常意味着几乎所有图上该性质的存在。
随机图在概率方法中得到了广泛的应用，它试图证明具有一定性质的图的存在性。通过 '''正则引理 Szemerédi Regularity Lemma'''，随机图上一个性质的存在常常意味着几乎所有图上该性质的存在。
在随机正则图中，<math>G(n，r-reg)</math> 是 <math>r=r(n)</math>的<math>r-</math>[[正则图]]的集合，其中 <math>n</math> 和 <math>m</math> 是自然数，<math>3 \le r<n </math> ，<math>rn = 2m</math> 是偶数。
在随机正则图中，<math>G(n，r-reg)</math> 是 <math>r=r(n)</math>的<math>r-</math>[[正则图]]的集合，其中 <math>n</math> 和 <math>m</math> 是自然数，<math>3 \le r<n </math> ，<math>rn = 2m</math> 是偶数。
在 <math>G^n</math> 中，图 <math>G</math> 的度序列仅取决于集合中的边数。
在 <math>G^n</math> 中，图 <math>G</math> 的度序列仅取决于集合中的边数。
如果随机图中的边 <math>M</math>，<math>G_M</math> 大到足以确保几乎每个 <math>G_M</math> 的最小阶数至少为1，那么几乎每个 <math>G</math> 是连通的，如果 <math>n</math> 是偶数，则几乎每个 <math>G_M</math> 都有一个'''完美匹配 Perfect Matching'''。特别是，在几乎每个随机图中，最后一个孤立点消失的那一刻，图会变连通。
如果随机图中的边 <math>M</math>，<math>G_M</math> 大到足以确保几乎每个 <math>G_M</math> 的最小阶数至少为1，那么几乎每个 <math>G</math> 是连通的，如果 <math>n</math> 是偶数，则几乎每个 <math>G_M</math> 都有一个'''完美匹配 Perfect Matching'''。特别是，在几乎每个随机图中，最后一个孤立点消失的那一刻，图会变连通。
几乎每个偶数顶点上的最小度提高到1的图或稍大于 <math>\tfrac{n}{4}\log(n)</math> 边且概率接近1的随机图都能确保图有'''完全匹配 Complete Matching'''，但最多只有一个顶点。
几乎每个偶数顶点上的最小度提高到1的图或稍大于 <math>\tfrac{n}{4}\log(n)</math> 边且概率接近1的随机图都能确保图有'''完全匹配 Complete Matching'''，但最多只有一个顶点。
对于某些常数 <math>c</math> ，几乎所有带有 <math>n</math> 顶点和至少 <math>cn\log(n)</math> 边的标记图都是 '''哈密尔顿环 Hamiltonian Cycle'''的。在概率趋于1的情况下，将最小度增加到2的特殊边会使图成为哈密尔顿图。
对于某些常数 <math>c</math> ，几乎所有带有 <math>n</math> 顶点和至少 <math>cn\log(n)</math> 边的标记图都是 '''哈密尔顿环 Hamiltonian Cycle'''的。在概率趋于1的情况下，将最小度增加到2的特殊边会使图成为哈密尔顿图。
在图变换下，随机图的性质可以改变或保持不变。例如，Mashaghi A.等人证明了将随机图转换为其 '''边-对偶图 Edge-Dual Graphs'''（或 '''线图 Liner Graph'''）的变换会产生一个度分布几乎相同，但具有 '''度相关性 Degree Correlations''' 和显著更高的 '''[[聚类系数]] Clustering Coefficent'''的图的集合。<ref>{{cite journal|first1=A.|last1=Ramezanpour|first2=V.|last2=Karimipour|first3=A.|last3=Mashaghi|title=Generating correlated networks from uncorrelated ones|journal=Phys. Rev. E|volume=67|issue=46107|pages=046107|year=2003|doi=10.1103/PhysRevE.67.046107|pmid=12786436|bibcode=2003PhRvE..67d6107R|arxiv=cond-mat/0212469}}</ref>
在图变换下，随机图的性质可以改变或保持不变。例如，Mashaghi A.等人证明了将随机图转换为其 '''边-对偶图 Edge-Dual Graphs'''（或 '''线图 Liner Graph'''）的变换会产生一个度分布几乎相同，但具有 '''度相关性 Degree Correlations''' 和显著更高的 '''[[聚类系数]] Clustering Coefficent'''的图的集合。<ref>{{cite journal|first1=A.|last1=Ramezanpour|first2=V.|last2=Karimipour|first3=A.|last3=Mashaghi|title=Generating correlated networks from uncorrelated ones|journal=Phys. Rev. E|volume=67|issue=46107|pages=046107|year=2003|doi=10.1103/PhysRevE.67.046107|pmid=12786436|bibcode=2003PhRvE..67d6107R|arxiv=cond-mat/0212469}}</ref>
==着色==
==着色==
给定一个 ''n'' 阶随机图 ''G''，其顶点 ''V''(''G'') = {1，... ，''n'' } ，通过关于颜色数的'''[[贪婪算法]] Greedy Algorithm'''，可以用颜色1,2... （如果顶点1与顶点2不相邻，则顶点1与顶点2为染相同的颜色，否则染不同的颜色，以此类推。）
给定一个 ''n'' 阶随机图 ''G''，其顶点 ''V''(''G'') = {1，... ，''n'' } ，通过关于颜色数的'''[[贪婪算法]] Greedy Algorithm'''，可以用颜色1,2... （如果顶点1与顶点2不相邻，则顶点1与顶点2为染相同的颜色，否则染不同的颜色，以此类推。）
给定一个 ''q'' 颜色的随机图的真染色数，称为它的'''染色多项式 Chormatic Polynomial'''（到目前为止还没有确定的正式名称）。利用'''符号模式匹配算法 Algorithm Based On Symbolic Pattern Matching''' ，对参数为 ''n'' 、边数为 ''m'' 或连接概率为 ''p'' 的随机图的染色多项式零点的标度进行了实验研究。<ref name = "Chromatic Polynomials of Random Graphs">{{cite journal | last1 = Van Bussel | first1 = Frank | last2 = Ehrlich | first2 = Christoph | last3 = Fliegner | first3 = Denny | last4 = Stolzenberg | first4 = Sebastian | last5 = Timme | first5 = Marc | year = 2010 | title = Chromatic Polynomials of Random Graphs | url = | journal = J. Phys. A: Math. Theor. | volume = 43 | issue = 17| page = 175002 | doi = 10.1088/1751-8113/43/17/175002 | arxiv = 1709.06209 | bibcode = 2010JPhA...43q5002V }}</ref>
给定一个 ''q'' 颜色的随机图的真染色数，称为它的'''染色多项式 Chormatic Polynomial'''（到目前为止还没有确定的正式名称）。利用'''符号模式匹配算法 Algorithm Based On Symbolic Pattern Matching''' ，对参数为 ''n'' 、边数为 ''m'' 或连接概率为 ''p'' 的随机图的染色多项式零点的标度进行了实验研究。<ref name = "Chromatic Polynomials of Random Graphs">{{cite journal | last1 = Van Bussel | first1 = Frank | last2 = Ehrlich | first2 = Christoph | last3 = Fliegner | first3 = Denny | last4 = Stolzenberg | first4 = Sebastian | last5 = Timme | first5 = Marc | year = 2010 | title = Chromatic Polynomials of Random Graphs | url = | journal = J. Phys. A: Math. Theor. | volume = 43 | issue = 17| page = 175002 | doi = 10.1088/1751-8113/43/17/175002 | arxiv = 1709.06209 | bibcode = 2010JPhA...43q5002V }}</ref>
==随机树图==
==随机树图==
随机树是由随机过程组成的树状图。在 ''n'' 阶和 ''M''(''n'')大小的随机图的大范围内，''k'' 阶树分量个数的分布是渐近泊松的。[[随机树]]的类型包括'''均匀生成树 Uniform Spanning Tree、随机最小生成树 Random Minimal Tree、随机二叉树 Random Binary Tree、树、快速检索随机树 Rapidly Exploring Random Tree、布朗树 Brownian Tree和随机森林 Random Forest'''。
随机树是由随机过程组成的树状图。在 ''n'' 阶和 ''M''(''n'')大小的随机图的大范围内，''k'' 阶树分量个数的分布是渐近泊松的。[[随机树]]的类型包括'''均匀生成树 Uniform Spanning Tree、随机最小生成树 Random Minimal Tree、随机二叉树 Random Binary Tree、树、快速检索随机树 Rapidly Exploring Random Tree、布朗树 Brownian Tree和随机森林 Random Forest'''。
==条件随机图==
==条件随机图==
考虑一个给定的随机图模型定义在概率空间上<math>(\Omega,\mathcal{F},P)</math> ，并且让 <math>\mathcal{P}(G) : \Omega \rightarrow R^{m}</math> 是一个值是实数的函数，它在 <math>\Omega</math> 中为每个图赋值一个 ''m'' 属性的向量。
考虑一个给定的随机图模型定义在概率空间上<math>(\Omega,\mathcal{F},P)</math> ，并且让 <math>\mathcal{P}(G) : \Omega \rightarrow R^{m}</math> 是一个值是实数的函数，它在 <math>\Omega</math> 中为每个图赋值一个 ''m'' 属性的向量。
对于 <math>R^{m}</math> 中的一个固定的 <math>\mathbf{p}</math> ，条件随机图是这样的模型，在这个模型中，机率量测 <math>p</math> 给所有图分配零概率，例如“ <math>\mathcal{P}(G)\neq\mathbf{p}</math> 。
对于 <math>R^{m}</math> 中的一个固定的 <math>\mathbf{p}</math> ，条件随机图是这样的模型，在这个模型中，机率量测 <math>p</math> 给所有图分配零概率，例如“ <math>\mathcal{P}(G)\neq\mathbf{p}</math> 。
特殊情况是'''条件均匀随机图 Conditionally Uniform Graph'''，其中 <math>p</math> 给所有具有指定性质的图赋予相等的概率。它们可以被看作是 Erdős–Rényi 模型 ''G''(''n''，''m'')的一个推广，当条件信息不一定是边的个数 ''M''，而是其他任意图性质 <math>\mathcal{P}(G)</math> 时。在这种情况下，很少有分析结果可用，就需要通过模拟来获得平均性质的经验分布。
特殊情况是'''条件均匀随机图 Conditionally Uniform Graph'''，其中 <math>p</math> 给所有具有指定性质的图赋予相等的概率。它们可以被看作是 Erdős–Rényi 模型 ''G''(''n''，''m'')的一个推广，当条件信息不一定是边的个数 ''M''，而是其他任意图性质 <math>\mathcal{P}(G)</math> 时。在这种情况下，很少有分析结果可用，就需要通过模拟来获得平均性质的经验分布。
==相互依存图==
==相互依存图==
在相互依存图中，一个网络（图）中的节点依赖于其他网络来工作。因此，一个或多个图中的故障会导致图之间的'''级联故障 Cascading Failures'''，从而引起网络突然崩溃。<ref name="BuldyrevParshani2010">{{cite journal|last1=Buldyrev|first1=Sergey V.|last2=Parshani|first2=Roni|last3=Paul|first3=Gerald|last4=Stanley|first4=H. Eugene|last5=Havlin|first5=Shlomo|title=Catastrophic cascade of failures in interdependent networks|journal=Nature|volume=464|issue=7291|year=2010|pages=1025–1028|issn=0028-0836|doi=10.1038/nature08932|pmid=20393559|arxiv=1012.0206|bibcode=2010Natur.464.1025B}}</ref><ref name="GaoBuldyrev2011">{{cite journal|last1=Gao|first1=Jianxi|last2=Buldyrev|first2=Sergey V.|last3=Stanley|first3=H. Eugene|last4=Havlin|first4=Shlomo|title=Networks formed from interdependent networks|journal=Nature Physics|volume=8|issue=1|year=2011|pages=40–48|issn=1745-2473|doi=10.1038/nphys2180|bibcode=2012NatPh...8...40G|citeseerx=10.1.1.379.8214}}</ref>
在相互依存图中，一个网络（图）中的节点依赖于其他网络来工作。因此，一个或多个图中的故障会导致图之间的'''级联故障 Cascading Failures'''，从而引起网络突然崩溃。<ref name="BuldyrevParshani2010">{{cite journal|last1=Buldyrev|first1=Sergey V.|last2=Parshani|first2=Roni|last3=Paul|first3=Gerald|last4=Stanley|first4=H. Eugene|last5=Havlin|first5=Shlomo|title=Catastrophic cascade of failures in interdependent networks|journal=Nature|volume=464|issue=7291|year=2010|pages=1025–1028|issn=0028-0836|doi=10.1038/nature08932|pmid=20393559|arxiv=1012.0206|bibcode=2010Natur.464.1025B}}</ref><ref name="GaoBuldyrev2011">{{cite journal|last1=Gao|first1=Jianxi|last2=Buldyrev|first2=Sergey V.|last3=Stanley|first3=H. Eugene|last4=Havlin|first4=Shlomo|title=Networks formed from interdependent networks|journal=Nature Physics|volume=8|issue=1|year=2011|pages=40–48|issn=1745-2473|doi=10.1038/nphys2180|bibcode=2012NatPh...8...40G|citeseerx=10.1.1.379.8214}}</ref>
==历史==
==历史==
最早使用随机图模型的是海伦·霍尔·詹宁斯和雅各布·莫雷诺，他们在1938年提出了一个“偶然社会记录模型”（一个有向的 Erdős-Rényi 模型）<ref>{{cite journal |last1=Moreno |first1=Jacob L |last2=Jennings |first2=Helen Hall |title=Statistics of Social Configurations |journal=Sociometry |date=Jan 1938 |volume=1 |issue=3/4 |pages=342–374 |doi=10.2307/2785588 }}</ref> ，用来比较他们的网络数据中的回传链接的比例和随机模型。另一个被称为“'''随机网络 Random Net'''”的随机图模型应用是1951年 Solomonoff 和 Rapoport 使用的有向图模型，这些有向图具有固定的出度，并且随机选择附加到其他顶点。<ref>{{cite journal |last1=Solomonoff |first1=Ray |last2=Rapopst |first2=Anatol |title=Connectivity of random nets |journal=Bulletin of Mathematical Biophysics |date=June 1951 |volume=13 |issue=2 |pages=107–117 |doi=10.1007/BF02478357}}</ref>
最早使用随机图模型的是海伦·霍尔·詹宁斯和雅各布·莫雷诺，他们在1938年提出了一个“偶然社会记录模型”（一个有向的 Erdős-Rényi 模型）<ref>{{cite journal |last1=Moreno |first1=Jacob L |last2=Jennings |first2=Helen Hall |title=Statistics of Social Configurations |journal=Sociometry |date=Jan 1938 |volume=1 |issue=3/4 |pages=342–374 |doi=10.2307/2785588 }}</ref> ，用来比较他们的网络数据中的回传链接的比例和随机模型。另一个被称为“'''随机网络 Random Net'''”的随机图模型应用是1951年 Solomonoff 和 Rapoport 使用的有向图模型，这些有向图具有固定的出度，并且随机选择附加到其他顶点。<ref>{{cite journal |last1=Solomonoff |first1=Ray |last2=Rapopst |first2=Anatol |title=Connectivity of random nets |journal=Bulletin of Mathematical Biophysics |date=June 1951 |volume=13 |issue=2 |pages=107–117 |doi=10.1007/BF02478357}}</ref>
[[随机图]]的Erdős–Rényi 模型是由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. 290–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>
[[随机图]]的Erdős–Rényi 模型是由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. 290–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>
==参见==
==参见==