更改

随机图 (查看源代码)

2020年11月8日 (日) 12:27的版本

删除1,552字节、 2020年11月8日 (日) 12:27

无编辑摘要

第18行：第18行：

In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs. Its practical applications are found in all areas in which complex networks need to be modeled – many random graph models are thus known, mirroring the diverse types of complex networks encountered in different areas. In a mathematical context, random graph refers almost exclusively to the Erdős–Rényi random graph model. In other contexts, any graph model may be referred to as a random graph.

−

在数学领域中，'''~~~~随机图 Random Graph ~~~~'''是指图上的概率分布的一般术语。随机图可以简单地用概率分布表示，也可以用生成它们的随机过程表示。随机图的理论处于图论和概率论的交汇点上。从数学的角度来看，随机图可以用来回答有关典型图的性质的问题。在所有需要对复杂网络进行建模的领域都能看到它的实际应用——由于它反映了在不同领域遇到的不同类型的复杂网络，许多随机图模型就此被人们所熟知。在数学上，随机图几乎完全指的是 '''~~~~Erdős-Rényi 随机图模型 Erdős–Rényi Random Graph Model ~~~~'''。在其他情况下，任何图形模型都可以称为随机图。

+

在数学领域中，'''随机图 Random Graph'''是指图上的概率分布的一般术语。随机图可以简单地用概率分布表示，也可以用生成它们的随机过程表示。随机图的理论处于图论和概率论的交汇点上。从数学的角度来看，随机图可以用来回答有关典型图的性质的问题。在所有需要对复杂网络进行建模的领域都能看到它的实际应用——由于它反映了在不同领域遇到的不同类型的复杂网络，许多随机图模型就此被人们所熟知。在数学上，随机图几乎完全指的是 '''Erdős-Rényi 随机图模型 Erdős–Rényi Random Graph Model'''。在其他情况下，任何图形模型都可以称为随机图。

第45行：第45行：

If instead we start with an infinite set of vertices, and again let every possible edge occur independently with probability 0 < p < 1, then we get an object G called an infinite random graph. Except in the trivial cases when p is 0 or 1, such a G almost surely has the following property:

−

如果我们从一个无限的顶点集合开始，然后再次让每个可能的边以概率0 < ''p'' < 1独立出现，那么我们得到一个对象 ''G'' 称为'''~~~~无限随机图 Infinite Graph ~~~~'''。除了在 ''p'' = 0或1的平凡情况下，这样的 ''G'' 在大多数情况下肯定具有以下性质:

+

如果我们从一个无限的顶点集合开始，然后再次让每个可能的边以概率0 < ''p'' < 1独立出现，那么我们得到一个对象 ''G'' 称为'''无限随机图 Infinite Graph'''。除了在 ''p'' = 0或1的平凡情况下，这样的 ''G'' 在大多数情况下肯定具有以下性质:

第61行：第61行：

It turns out that if the vertex set is countable then there is, up to isomorphism, only a single graph with this property, namely the Rado graph. Thus any countably infinite random graph is almost surely the Rado graph, which for this reason is sometimes called simply the random graph. However, the analogous result is not true for uncountable graphs, of which there are many (nonisomorphic) graphs satisfying the above property.

−

结果表明，如果顶点集是可数的，那么在'''~~~~同构 Isomorphism ~~~~'''意义下，只有一个图具有这个性质，即 Rado 图。因此，任何可数无限随机图几乎可以肯定是 Rado 图，由于这个原因，有时被简称为随机图。然而，对于'''~~~~不可数图 Uncountable Graph ~~~~'''类似的结果是不正确的，不可数图中有许多'''~~~~(不同构)图 Nonisomorphic Graph ~~~~'''满足上述性质。

+

结果表明，如果顶点集是可数的，那么在'''同构 Isomorphism'''意义下，只有一个图具有这个性质，即 Rado 图。因此，任何可数无限随机图几乎可以肯定是 Rado 图，由于这个原因，有时被简称为随机图。然而，对于'''不可数图 Uncountable Graph'''类似的结果是不正确的，不可数图中有许多'''(不同构)图 Nonisomorphic Graph'''满足上述性质。

第69行：第69行：

Another model, which generalizes Gilbert's random graph model, is the random dot-product model. A random dot-product graph associates with each vertex a real vector. The probability of an edge uv between any vertices u and v is some function of the dot product u • v of their respective vectors.

−

另一个模型，概括了吉尔伯特的随机图模型，是'''~~~~随机点积模型 Random Dot-product Model'''。一个'''~~~~随机点积图 Random Dot-product Graph ~~~~''' 将每个顶点与一个实向量相关联。任意顶点 ''u'' 和 ''v'' 之间的边 ''uv'' 的概率是它们各自向量的点积 ''u'' · ''v'' 的某个函数。

+

另一个模型，概括了吉尔伯特的随机图模型，是'''随机点积模型 Random Dot-product Model'''。一个'''随机点积图 Random Dot-product Graph''' 将每个顶点与一个实向量相关联。任意顶点 ''u'' 和 ''v'' 之间的边 ''uv'' 的概率是它们各自向量的点积 ''u'' · ''v'' 的某个函数。

第77行：第77行：

The network probability matrix models random graphs through edge probabilities, which represent the probability <math>p_{i,j}</math> that a given edge <math>e_{i,j}</math> exists for a specified time period. This model is extensible to directed and undirected; weighted and unweighted; and static or dynamic graphs structure.

−

'''~~~~网络转移矩阵 NetWork Probability Matrix ~~~~'''通过边概率对随机图进行建模，这些边概率代表给定的边存在一个特定的时间段的概率。这个模型可以扩展到有向和无向，加权和无权，以及静态或动态的图形结构。

+

'''网络转移矩阵 NetWork Probability Matrix'''通过边概率对随机图进行建模，这些边概率代表给定的边存在一个特定的时间段的概率。这个模型可以扩展到有向和无向，加权和无权，以及静态或动态的图形结构。

第93行：第93行：

Random regular graphs form a special case, with properties that may differ from random graphs in general.

−

'''~~~~随机正则图 Random Regular Graph ~~~~'''是一种特殊情况，其性质可能与一般随机图不同。

+

'''随机正则图 Random Regular Graph'''是一种特殊情况，其性质可能与一般随机图不同。

第121行：第121行：

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 ~~~~'''刻画了随机图，特别是无穷大图的'''~~~~连通性 Connectedness ~~~~'''。

+

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

第129行：第129行：

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> 的节点。存在一个'''~~~~临界渗透阈值 Critical Percolation Threshold ~~~~'''<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> 的节点。存在一个'''临界渗透阈值 Critical Percolation Threshold'''<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" />

第139行：第139行：

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> ，和随机删除是一样的。对于其他类型的度分布 <math>p_c</math>，局部攻击和随机攻击是不同的。

+

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

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

第145行：第145行：

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

−

''('''~~~~阈值函数 Threshold Functions ~~~~''', <math>\tilde G</math> 的演化)''

+

''('''阈值函数 Threshold Functions''', <math>\tilde G</math> 的演化)''

第153行：第153行：

Random graphs are widely used in the probabilistic method, where one tries to prove the existence of graphs with certain properties. The existence of a property on a random graph can often imply, via the Szemerédi regularity lemma, the existence of that property on almost all graphs.

−

随机图在概率方法中得到了广泛的应用，它试图证明具有一定性质的图的存在性。通过 '''~~~~Szemerédi 正则引理 Szemerédi Regularity Lemma ~~~~'''，随机图上一个性质的存在常常意味着几乎所有图上该性质的存在。

+

随机图在概率方法中得到了广泛的应用，它试图证明具有一定性质的图的存在性。通过 '''Szemerédi 正则引理 Szemerédi Regularity Lemma'''，随机图上一个性质的存在常常意味着几乎所有图上该性质的存在。

第183行：第183行：

If edges, <math>M</math> in a random graph, <math>G_M</math> is large enough to ensure that almost every <math>G_M</math> has minimum degree at least 1, then almost every <math>G_M</math> is connected and, if <math>n</math> is even, almost every <math>G_M</math> has a perfect matching. In particular, the moment the last isolated vertex vanishes in almost every random graph, the graph becomes connected.

−

如果随机图中的边 <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'''。特别是，在几乎每个随机图中，最后一个孤立点消失的那一刻，图会变连通。

第191行：第191行：

Almost every graph process on an even number of vertices with the edge raising the minimum degree to 1 or a random graph with slightly more than <math>\tfrac{n}{4}\log(n)</math> edges and with probability close to 1 ensures that the graph has a complete matching, with exception of at most one vertex.

−

几乎每个偶数顶点上的最小度提高到1的图或稍大于 <math>\tfrac{n}{4}\log(n)</math> 边且概率接近1的随机图都能确保图有'''~~~~完全匹配 Complete Matching ~~~~'''，但最多只有一个顶点。

+

几乎每个偶数顶点上的最小度提高到1的图或稍大于 <math>\tfrac{n}{4}\log(n)</math> 边且概率接近1的随机图都能确保图有'''完全匹配 Complete Matching'''，但最多只有一个顶点。

第199行：第199行：

For some constant <math>c</math>, almost every labeled graph with <math>n</math> vertices and at least <math>cn\log(n)</math> edges is Hamiltonian. With the probability tending to 1, the particular edge that increases the minimum degree to 2 makes the graph Hamiltonian.

−

对于某些常数 <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的特殊边会使图成为哈密尔顿图。

第207行：第207行：

Properties of random graph may change or remain invariant under graph transformations. Mashaghi A. et al., for example, demonstrated that a transformation which converts random graphs to their edge-dual graphs (or line graphs) produces an ensemble of graphs with nearly the same degree distribution, but with degree correlations and a significantly higher clustering coefficient.

−

在图变换下，随机图的性质可以改变或保持不变。例如，Mashaghi A.等人证明了将随机图转换为其 '''~~~~边-对偶图 Edge-Dual Graphs ~~~~'''(或 '''~~~~线图 Liner Graph ~~~~''')的变换会产生一个度分布几乎相同，但具有 '''~~~~度相关性 Degree Correlations ~~~~''' 和显著更高的 '''~~~~聚类系数 Clustering Coefficent ~~~~'''的图的集合。

+

在图变换下，随机图的性质可以改变或保持不变。例如，Mashaghi A.等人证明了将随机图转换为其 '''边-对偶图 Edge-Dual Graphs'''(或 '''线图 Liner Graph''')的变换会产生一个度分布几乎相同，但具有 '''度相关性 Degree Correlations''' 和显著更高的 '''聚类系数 Clustering Coefficent'''的图的集合。

== Coloring 着色==

−

'''~~~~着色 Coloring ~~~~'''

+

'''着色 Coloring'''

Given a random graph ''G'' of order ''n'' with the vertex ''V''(''G'') = {1, ..., ''n''}, by the [[greedy algorithm]] on the number of colors, the vertices can be colored with colors 1, 2, ... (vertex 1 is colored 1, vertex 2 is colored 1 if it is not adjacent to vertex 1, otherwise it is colored 2, etc.).<ref name = "Random Graphs2" />

第216行：第216行：

Given a random graph G of order n with the vertex V(G) = {1, ..., n}, by the greedy algorithm on the number of colors, the vertices can be colored with colors 1, 2, ... (vertex 1 is colored 1, vertex 2 is colored 1 if it is not adjacent to vertex 1, otherwise it is colored 2, etc.).

−

给定一个 ''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为染相同的颜色，否则染不同的颜色，以此类推。).

The number of proper colorings of random graphs given a number of ''q'' colors, called its [[chromatic polynomial]], remains unknown so far. The scaling of zeros of the chromatic polynomial of random graphs with parameters ''n'' and the number of edges ''m'' or the connection probability ''p'' has been studied empirically using an algorithm based on symbolic pattern matching.<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>

第222行：第222行：

The number of proper colorings of random graphs given a number of q colors, called its chromatic polynomial, remains unknown so far. The scaling of zeros of the chromatic polynomial of random graphs with parameters n and the number of edges m or the connection probability p has been studied empirically using an algorithm based on symbolic pattern matching.

−

给定一个 ''q'' 颜色的随机图的真染色数，称为它的'''~~~~染色多项式 Chormatic Polynomial ~~~~'''（到目前为止还没有确定的正式名称）。利用'''~~~~符号模式匹配算法 Algorithm Based On Symbolic Pattern Matching ~~~~''' ，对参数为 ''n'' 、边数为 ''m'' 或连接概率为 ''p'' 的随机图的染色多项式零点的标度进行了实验研究。。

+

给定一个 ''q'' 颜色的随机图的真染色数，称为它的'''染色多项式 Chormatic Polynomial'''（到目前为止还没有确定的正式名称）。利用'''符号模式匹配算法 Algorithm Based On Symbolic Pattern Matching''' ，对参数为 ''n'' 、边数为 ''m'' 或连接概率为 ''p'' 的随机图的染色多项式零点的标度进行了实验研究。。

== Random trees 随机树图==

−

'''~~~~随机树图 Random Tree ~~~~'''

+

'''随机树图 Random Tree'''

第234行：第234行：

A random tree is a tree or arborescence that is formed by a stochastic process. In a large range of random graphs of order n and size M(n) the distribution of the number of tree components of order k is asymptotically Poisson. Types of random trees include uniform spanning tree, random minimal spanning tree, random binary tree, treap, rapidly exploring random tree, Brownian tree, and random forest.

−

随机树是由随机过程组成的树状图。在 ''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'''。

== Conditional random graphs 条件随机图==

−

'''~~~~条件随机图 Conditional Random Graphs ~~~~'''

+

'''条件随机图 Conditional Random Graphs'''

第259行：第259行：

Special cases are conditionally uniform random graphs, where <math>P</math> assigns equal probability to all the graphs having specified properties. They can be seen as a generalization of the Erdős–Rényi model G(n,M), when the conditioning information is not necessarily the number of edges M, but whatever other arbitrary graph property <math>\mathcal{P}(G)</math>. In this case very few analytical results are available and simulation is required to obtain empirical distributions of average properties.

−

特殊情况是'''~~~~条件均匀随机图 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> 时。在这种情况下，很少有分析结果可用，就需要通过模拟来获得平均性质的经验分布。

==Interdependent graphs 相互依存图==

−

'''~~~~相互依存图 Interdependent Graph ~~~~'''

+

'''相互依存图 Interdependent Graph'''

In interdependent graphs nodes in one network (graph) depend on other networks to function. So failures in one or several graphs induce cascading failures between the graphs which may lead to abrupt collapse.<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>

第268行：第268行：

In interdependent graphs nodes in one network (graph) depend on other networks to function. So failures in one or several graphs induce cascading failures between the graphs which may lead to abrupt collapse.

−

在相互依存图中，一个网络（graph）中的节点依赖于其他网络来工作。因此，一个或多个图中的故障会导致图之间的'''~~~~级联故障 Cascading Failures ~~~~'''，从而引起网络突然崩溃。

+

在相互依存图中，一个网络（graph）中的节点依赖于其他网络来工作。因此，一个或多个图中的故障会导致图之间的'''级联故障 Cascading Failures'''，从而引起网络突然崩溃。

==History 历史==

第277行：第277行：

The earliest use of a random graph model was by Helen Hall Jennings and Jacob Moreno in 1938 where a "chance sociogram" (a directed Erdős-Rényi model) was considered in studying comparing the fraction of reciprocated links in their network data with the random model. Another use, under the name "random net", was by Solomonoff and Rapoport in 1951, using a model of directed graphs with fixed out-degree and randomly chosen attachments to other vertices.

−

最早使用随机图模型的是海伦·霍尔·詹宁斯和雅各布·莫雷诺，他们在1938年提出了一个“偶然社会记录模型”(一个有向的 Erdős-Rényi 模型) ，用来比较他们的网络数据中的回传链接的比例和随机模型。另一个被称为“'''~~~~随机网络 Random Net ~~~~'''”的随机图模型应用是1951年 Solomonoff 和 Rapoport 使用的有向图模型，这些有向图具有固定的出度，并且随机选择附加到其他顶点。

+

最早使用随机图模型的是海伦·霍尔·詹宁斯和雅各布·莫雷诺，他们在1938年提出了一个“偶然社会记录模型”(一个有向的 Erdős-Rényi 模型) ，用来比较他们的网络数据中的回传链接的比例和随机模型。另一个被称为“'''随机网络 Random Net'''”的随机图模型应用是1951年 Solomonoff 和 Rapoport 使用的有向图模型，这些有向图具有固定的出度，并且随机选择附加到其他顶点。

第290行：第290行：

* [[Bose–Einstein condensation: a network theory approach]]

−

'''~~~~玻色-爱因斯坦凝聚Bose–Einstein Condensation ~~~~''': a network theory approach

+

'''玻色-爱因斯坦凝聚Bose–Einstein Condensation''': a network theory approach

* [[Cavity method]]

−

'''~~~~空腔法 Cavity Method ~~~~'''

+

'''空腔法 Cavity Method'''

* [[Complex networks]]

−

'''~~~~复杂网络 Complex Network ~~~~'''

+

'''复杂网络 Complex Network'''

* [[Dual-phase evolution]]

−

'''~~~~Dual-phase Evolution ~~~~'''

+

'''Dual-phase Evolution'''

* [[Erdős–Rényi model]]

−

'''~~~~Erdős–Rényi model ~~~~'''

+

'''Erdős–Rényi model'''

* [[Exponential random graph model]]

−

'''~~~~指数随机图模型 Exponential Random Graph Model ~~~~'''

+

'''指数随机图模型 Exponential Random Graph Model'''

* [[Graph theory]]

−

'''~~~~图论 Graph Theory ~~~~'''

+

'''图论 Graph Theory'''

* [[Interdependent networks]]

−

'''~~~~相互依存图 Interdependent Networks ~~~~'''

+

'''相互依存图 Interdependent Networks'''

* [[Network science]]

−

'''~~~~网络科学 Network Science ~~~~'''

+

'''网络科学 Network Science'''

* [[Percolation]]

−

'''~~~~渗流 Percolation ~~~~'''

+

'''渗流 Percolation'''

* [[Percolation theory]]

−

'''~~~~渗流理论 Percolation Theory ~~~~'''

+

'''渗流理论 Percolation Theory'''

* [[Regular graph]]

−

'''~~~~正则图 Regular Graph ~~~~'''

+

'''正则图 Regular Graph'''

* [[Scale free network]]

−

'''~~~~无标度网络 Scale Free Network ~~~~'''

+

'''无标度网络 Scale Free Network'''

* [[Semilinear response]]

−

'''~~~~半线性相应 Semilinear Response ~~~~'''

+

'''半线性相应 Semilinear Response'''

* [[Stochastic block model]]

−

'''~~~~随机块体模型 Stochastic Block Model ~~~~'''

+

'''随机块体模型 Stochastic Block Model'''

*[[Lancichinetti–Fortunato–Radicchi benchmark]]

−

'''~~~~Lanchinetti Fortunato Radicchi基准 Lancichinetti–Fortunato–Radicchi Benchmark'''

+

'''Lanchinetti Fortunato Radicchi基准 Lancichinetti–Fortunato–Radicchi Benchmark'''

==References 参考文献==

打豆豆

421

个编辑

更改

随机图 (查看源代码)

2020年11月8日 (日) 12:27的版本

导航菜单

搜索