763
个编辑
更改
跳到导航
跳到搜索
第161行：
第161行： − Network models serve as a foundation to understanding interactions within empirical complex networks. Various [[random graph]] generation models produce network structures that may be used in comparison to real-world complex networks. − + − [[File:ER model.svg|thumb|This [[Erdős–Rényi model]] is generated with {{math|<VAR>N</VAR> {{=}} 4}} nodes. For each edge in the complete graph formed by all {{mvar|N}} nodes, a random number is generated and compared to a given probability. If the random number is less than {{mvar|p}}, an edge is formed on the model.]] − The '''[[Erdős–Rényi model]]''', named for [[Paul Erdős]] and [[Alfréd Rényi]], is used for generating [[random graph]]s in which edges are set between nodes with equal probabilities. It can be used in the [[probabilistic method]] to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs. − − To generate an Erdős–Rényi model <math>G(n, p) − − </math> two parameters must be specified: the total number of nodes {{mvar|n}} and the probability {{mvar|p}} that a random pair of nodes has an edge. − − Because the model is generated without bias to particular nodes, the degree distribution is binomial: for a randomly chosen vertex <math>v</math>, − : <math>P(\deg(v) = k) = {n-1\choose k} p^k (1-p)^{n-1-k}.</math> − − In this model the clustering coefficient is {{math|0}} [[Almost surely|a.s]]. The behavior of <math>G(n, p) − − </math> can be broken into three regions. − − ''Subcritical'' <math>n p < 1 − − </math>: All components are simple and very small, the largest component has size <math>|C_1| = O(\log n) − − </math>; − − ''Critical'' <math>n p = 1 − − </math>: <math>|C_1| = O(n^\frac{2}{3}) − − </math>; − − ''Supercritical'' <math>n p >1 − − </math>:<math>|C_1| \approx yn − </math> where <math>y = y(n p) − − </math> is the positive solution to the equation <math>e^{-p n y }=1-y − − </math>. − − The largest connected component has high complexity. All other components are simple and small <math>|C_2| = O(\log n) − − </math>. − 生成Erdős–Rényi 模型 <math>G(n, p)+ − − 第220行：
第179行： − + − + − + − ''临界'' <math>n p = 1+ − </math>: <math>|C_1| = O(n^\frac{2}{3})+ − − </math>; − − ''超临界'' <math>n p >1 − − </math>:<math>|C_1| \approx yn − </math> 其中 <math>y = y(n p) − − </math> 是方程 <math>e^{-p n y }=1-y − − </math>的正根。 − − − − − The configuration model takes a degree sequence<ref>{{Cite journal|last=Bender|first=Edward A|last2=Canfield|first2=E.Rodney|date=May 1978|title=The asymptotic number of labeled graphs with given degree sequences|journal=Journal of Combinatorial Theory, Series A|volume=24|issue=3|pages=296–307|doi=10.1016/0097-3165(78)90059-6|issn=0097-3165}}</ref><ref name=":0">{{Cite journal|last=Molloy|first=Michael|last2=Reed|first2=Bruce|date=March 1995|title=A critical point for random graphs with a given degree sequence|journal=Random Structures & Algorithms|language=en|volume=6|issue=2–3|pages=161–180|doi=10.1002/rsa.3240060204|issn=1042-9832|citeseerx=10.1.1.24.6195}}</ref> or degree distribution<ref name=":1">{{Cite journal|last=Newman|first=M. E. J.|last2=Strogatz|first2=S. H.|last3=Watts|first3=D. J.|date=2001-07-24|title=Random graphs with arbitrary degree distributions and their applications|journal=Physical Review E|volume=64|issue=2|pages=026118|doi=10.1103/PhysRevE.64.026118|pmid=11497662|arxiv=cond-mat/0007235|bibcode=2001PhRvE..64b6118N}}</ref> (which subsequently is used to generate a degree sequence) as the input, and produces randomly connected graphs in all respects other than the degree sequence. This means that for a given choice of the degree sequence, the graph is chosen uniformly at random from the set of all graphs that comply with this degree sequence. The degree <math>k</math> of a randomly chosen vertex is an [[Independent and identically distributed random variables|independent and identically distributed]] random variable with integer values. When <math display="inline">\mathbb E [k^2] - 2 \mathbb E [k]>0</math>, the configuration graph contains the [[Giant component|giant connected component]], which has infinite size.<ref name=":0" /> The rest of the components have finite sizes, which can be quantified with the notion of the size distribution. The probability <math>w(n)</math> that a randomly sampled node is connected to a component of size <math>n</math> is given by [[convolution power]]s of the degree distribution:<ref>{{Cite journal|last=Kryven|first=Ivan|date=2017-05-02|title=General expression for the component size distribution in infinite configuration networks|journal=Physical Review E|volume=95|issue=5|pages=052303|doi=10.1103/PhysRevE.95.052303|pmid=28618550|arxiv=1703.05413|bibcode=2017PhRvE..95e2303K}}</ref><math display="block">w(n)=\begin{cases} − \frac{\mathbb E [k]}{n-1} u_1^{*n}(n-2),& n>1, \\ − u(0) & n=1, − \end{cases}</math>where <math>u(k)</math> denotes the degree distribution and <math>u_1(k)=\frac{(k+1)u(k+1)}{\mathbb E[k]}</math>. The giant component can be destroyed by randomly removing the critical fraction <math>p_c</math> of all edges. This process is called [[Percolation theory|percolation on random networks]]. When the second moment of the degree distribution is finite, <math display="inline">\mathbb E [k^2]<\infty</math>, this critical edge fraction is given by<ref>{{Cite journal|last=Kryven|first=Ivan|date=2018-01-01|title=Analytic results on the polymerisation random graph model|journal=Journal of Mathematical Chemistry|language=en|volume=56|issue=1|pages=140–157|doi=10.1007/s10910-017-0785-1|issn=0259-9791|doi-access=free}}</ref> <math>p_c=1-\frac{\mathbb E[k]}{ \mathbb E [k^2] - \mathbb E[k]}</math>, and the [[Average path length|average vertex-vertex distance]] <math>l</math> in the giant component scales logarithmically with the total size of the network, <math>l = O(\log N) </math>.<ref name=":1" /> − − In the directed configuration model, the degree of a node is given by two numbers, in-degree <math>k_\text{in}</math> and out-degree <math>k_\text{out}</math>, and consequently, the degree distribution is two-variate. The expected number of in-edges and out-edges coincides, so that <math display="inline">\mathbb E [k_\text{in}]=\mathbb E [k_\text{out}]</math>. The directed configuration model contains the [[giant component]] iff<ref>{{Cite journal|last=Kryven|first=Ivan|date=2016-07-27|title=Emergence of the giant weak component in directed random graphs with arbitrary degree distributions|journal=Physical Review E|volume=94|issue=1|pages=012315|doi=10.1103/PhysRevE.94.012315|pmid=27575156|arxiv=1607.03793|bibcode=2016PhRvE..94a2315K}}</ref><math display="block">2\mathbb{E}[k_\text{in}] − \mathbb{E}[k_\text{in}k_\text{out}] − - \mathbb{E}[k_\text{in}] − \mathbb{E}[k_\text{out}^2] − - \mathbb{E}[k_\text{in}] − \mathbb{E}[k_\text{in}^2] − +\mathbb{E}[k_\text{in}^2] \mathbb{E}[k_\text{out}^2] − - \mathbb{E}[k_\text{in} k_\text{out}]^2 >0.</math>Note that <math display="inline">\mathbb E [k_\text{in}]</math> and <math display="inline">\mathbb E [k_\text{out}]</math> are equal and therefore interchangeable in the latter inequality. The probability that a randomly chosen vertex belongs to a component of size <math>n</math> is given by:<ref>{{Cite journal|last=Kryven|first=Ivan|date=2017-11-02|title=Finite connected components in infinite directed and multiplex networks with arbitrary degree distributions|journal=Physical Review E|volume=96|issue=5|pages=052304|doi=10.1103/PhysRevE.96.052304|pmid=29347790|arxiv=1709.04283|bibcode=2017PhRvE..96e2304K}}</ref><math display="block">h_\text{in}(n)=\frac{\mathbb E[k_{in}]}{n-1} \tilde u_\text{in}^{*n}(n-2), \;n>1, \; \tilde u_\text{in}=\frac{k_\text{in}+1}{\mathbb E[k_\text{in}]}\sum\limits_{k_\text{out}\geq 0}u(k_\text{in}+1,k_\text{out}),</math>for in-components, and − − <math>h_\text{out}(n)=\frac{\mathbb E[k_\text{out}]}{n-1} \tilde u_\text{out}^{*n}(n-2), \;n>1, \;\tilde u_\text{out}=\frac{k_\text{out}+1}{\mathbb E[k_\text{out}]}\sum\limits_{k_\text{in}\geq0}u(k_\text{in},k_\text{out}+1), − − </math> − − for out-components. 第283行：
第208行： − [[File:Watts-Strogatz-rewire.png|thumb|The [[Watts and Strogatz model]] uses the concept of rewiring to achieve its structure. The model generator will iterate through each edge in the original lattice structure. An edge may changed its connected vertices according to a given rewiring probability. <math>\langle k\rangle = 4</math> in this example.]] − The [[Watts and Strogatz model]] is a random graph generation model that produces graphs with [[small-world properties]]. − − An initial lattice structure is used to generate a Watts–Strogatz model. Each node in the network is initially linked to its <math>\langle k\rangle</math> closest neighbors. Another parameter is specified as the rewiring probability. Each edge has a probability <math>p</math> that it will be rewired to the graph as a random edge. The expected number of rewired links in the model is <math>pE = pN\langle k\rangle/2</math>. − As the Watts–Strogatz model begins as non-random lattice structure, it has a very high clustering coefficient along with high average path length. Each rewire is likely to create a shortcut between highly connected clusters. As the rewiring probability increases, the clustering coefficient decreases slower than the average path length. In effect, this allows the average path length of the network to decrease significantly with only slightly decreases in clustering coefficient. Higher values of p force more rewired edges, which in effect makes the Watts–Strogatz model a random network.+ − 由于Watts–Strogatz 模型的初始网络具有非随机的晶格结构，因此它具有很高的聚集系数和平均路径长度。每次重新连接都可能在高度连接的集群之间创建一条捷径。随着重连接概率的增加，聚集系数的下降速度慢于平均路径长度的下降速度。实际上，这使得网络的平均路径长度显著降低，而聚集系数只略微降低。更高的重连接概率<math>p</math>会导致更多的边重新连接，这实际上使Watts–Strogatz模型趋于随机网络。 − The [[Barabási–Albert model]] is a random network model used to demonstrate a preferential attachment or a "rich-get-richer" effect. In this model, an edge is most likely to attach to nodes with higher degrees.The network begins with an initial network of ''m''<sub>0</sub> nodes. ''m''<sub>0</sub> ≥ 2 and the degree of each node in the initial network should be at least 1, otherwise it will always remain disconnected from the rest of the network. − − In the BA model, new nodes are added to the network one at a time. Each new node is connected to <math>m</math> existing nodes with a probability that is proportional to the number of links that the existing nodes already have. Formally, the probability ''p''<sub>''i''</sub> that the new node is connected to node ''i'' is<ref name=RMP>{{Cite journal − |url = http://www.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/StatisticalMechanics_Rev%20of%20Modern%20Physics%2074,%2047%20(2002).pdf − |author1 = R. Albert − |author2 = A.-L. Barabási − |title = Statistical mechanics of complex networks − |journal = [[Reviews of Modern Physics]] − |volume = 74 − |issue = 1 − |pages = 47–97 − |year = 2002 − |doi = 10.1103/RevModPhys.74.47 − |bibcode = 2002RvMP...74...47A − |arxiv = cond-mat/0106096 − |url-status = dead − |archiveurl = https://web.archive.org/web/20150824235818/http://www3.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/StatisticalMechanics_Rev%20of%20Modern%20Physics%2074,%2047%20(2002).pdf − |archivedate = 2015-08-24 − |citeseerx = 10.1.1.242.4753 − }}</ref> − − : <math>p_i = \frac{k_i}{\sum_j k_j},</math> − − where ''k''<sub>''i''</sub> is the degree of node ''i''. Heavily linked nodes ("hubs") tend to quickly accumulate even more links, while nodes with only a few links are unlikely to be chosen as the destination for a new link. The new nodes have a "preference" to attach themselves to the already heavily linked nodes. − − [[File:Barabasi-albert model degree distribution.svg|thumb|The degree distribution of the BA Model, which follows a power law. In loglog scale the power law function is a straight line.<ref name=Barabasi1999>{{Cite journal − |url = http://www.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/EmergenceRandom_Science%20286,%20509-512%20(1999).pdf − |author = [[Albert-László Barabási]] & [[Réka Albert]] − |title = Emergence of scaling in random networks − |journal = [[Science (journal)|Science]] − |volume = 286 − |pages = 509–512 − |date = October 1999 − |doi = 10.1126/science.286.5439.509 − |issue = 5439 − |pmid = 10521342 − |arxiv = cond-mat/9910332 − |bibcode = 1999Sci...286..509B − |url-status = dead − |archiveurl = https://web.archive.org/web/20120417112354/http://www.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/EmergenceRandom_Science%20286,%20509-512%20(1999).pdf − |archivedate = 2012-04-17 − }}</ref>]] − The degree distribution resulting from the BA model is scale free, in particular, it is a power law of the form: − : <math>P(k)\sim k^{-3} \, </math> 第370行：
第246行： + 第392行：
第269行： − Hubs exhibit high betweenness centrality which allows short paths to exist between nodes. As a result, the BA model tends to have very short average path lengths. The clustering coefficient of this model also tends to 0.+ − While the diameter, D, of many models including the Erdős Rényi random graph model and several small world networks is proportional to log N, the BA model exhibits D~loglogN (ultrasmall world).<ref>{{cite journal|last=Cohen|first=R. |title=Scale-free networks are ultrasmall|journal=Phys. Rev. Lett.|year=2003|volume=90|pages=058701|url=http://havlin.biu.ac.il/Publications.php?keyword=Scale-free+networks+are+ultrasmall&year=*&match=all|doi=10.1103/PhysRevLett.90.058701|pmid=12633404|first2=S.|last2=Havlin|issue=5|bibcode=2003PhRvL..90e8701C |arxiv=cond-mat/0205476}}</ref> + − Note that the average path length scales with N as the diameter.+ + − 中心节点表现出很高的介数中心性，这使得节点之间存在捷径。因此，BA模型的平均路径长度往往很短。该模型的聚集系数也趋于0。 − 当包括Erdős Rényi随机图模型和一些小世界网络在内的许多模型的直径D正比于log N时，BA模型表现为D~loglogN（超小世界）。<ref>{{cite journal|last=Cohen|first=R. |title=Scale-free networks are ultrasmall|journal=Phys. Rev. Lett.|year=2003|volume=90|pages=058701|url=http://havlin.biu.ac.il/Publications.php?keyword=Scale-free+networks+are+ultrasmall&year=*&match=all|doi=10.1103/PhysRevLett.90.058701|pmid=12633404|first2=S.|last2=Havlin|issue=5|bibcode=2003PhRvL..90e8701C |arxiv=cond-mat/0205476}}</ref> − 注意，平均路径长度随N的变化和直径相同。 − In the [[mediation-driven attachment model|mediation-driven attachment (MDA) model]] in which a new node coming with <math>m</math> edges picks an existing connected node at random and then connects itself not with that one but with <math>m</math> of its neighbors chosen also at random. The probability <math>\Pi(i)</math> that the node <math>i</math> of the existing node picked is − − : <math> \Pi(i) = \frac{k_i} N \frac{ \sum_{j=1}^{k_i} \frac 1 {k_j} }{k_i}.</math> 第410行：
第282行： − The factor <math>\frac{\sum_{j=1}^{k_i}{\frac{1}{k_j}}}{k_i}</math> is the inverse of the harmonic mean+ − (IHM) of degrees of the <math>k_i</math> neighbors of a node <math>i</math>. Extensive numerical investigation suggest that for an approximately <math>m> 14</math> the mean IHM value in the large <math>N</math> limit becomes a constant which means <math>\Pi(i) \propto k_i</math>. It implies that the higher the − links (degree) a node has, the higher its chance of gaining more links since they can be − reached in a larger number of ways through mediators which essentially embodies the intuitive − idea of rich get richer mechanism (or the preferential attachment rule of the Barabasi–Albert model). Therefore, the MDA network can be seen to follow − the PA rule but in disguise.<ref>{{cite journal | last1 = Hassan | first1 = M. K. | last2 = Islam | first2 = Liana | last3 = Arefinul Haque | first3 = Syed | date = March 2017 | title = Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks | doi = 10.1016/j.physa.2016.11.001 | journal = Physica A | volume = 469 | issue = | pages = 23–30 | arxiv = 1411.3444 | bibcode = 2017PhyA..469...23H }}</ref> − 因子 <math>\frac{\sum_{j=1}^{k_i}{\frac{1}{k_j}}}{k_i}</math>是节点 <math>i</math>的<math>k_i</math>个相邻节点的度的调和平均（IHM）的逆。大量的数值研究表明，对于<math>m> 14</math>，IHM的值在大<math>N</math>极限下会变成常数，这意味着<math>\Pi(i) \propto k_i</math>。这表明一个节点的连接（度）越高，获得更多连接的机会就更大，因为它们可以通过中介以更多的方式连接到，这本质上体现了富人越富机制的直观思想（或者BA模型优先链接的规则）。因此，可以看出MDA网络以伪装的方式遵循优先链接规则。<ref>{{cite journal | last1 = Hassan | first1 = M. K. | last2 = Islam | first2 = Liana | last3 = Arefinul Haque | first3 = Syed | date = March 2017 | title = Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks | doi = 10.1016/j.physa.2016.11.001 | journal = Physica A | volume = 469 | issue = | pages = 23–30 | arxiv = 1411.3444 | bibcode = 2017PhyA..469...23H }}</ref> + − However, for <math>m=1</math> it describes the winner takes it all mechanism as we find that almost <math>99\%</math> of the total nodes have degree one and one is super-rich in degree. As <math>m</math> value increases the disparity between the super rich and poor decreases and as <math>m>14</math> we find a transition from rich get super richer to rich get richer mechanism. − − 然而，当<math>m=1</math> 时，它描述了赢者通吃的机制，因为我们可以发现，几乎<math>99\%</math> 的节点的度仅为1，而某一个节点的度超级大。当<math>m</math>的值增加时，超级富人和穷人之间的差距减小；当<math>m>14</math>时，从赢者通吃机制转变为富人更富机制。 − Another model where the key ingredient is the nature of the vertex has been introduced by Caldarelli et al.<ref>Caldarelli G., A. Capocci, P. De Los Rios, M.A. Muñoz, Physical Review Letters 89, 258702 (2002)</ref> Here a link is created between two vertices <math>i,j</math> with a probability given by a linking function <math>f(\eta_i,\eta_j)</math> of the [[Fitness model (network theory)|fitnesses]] of the vertices involved. − − The degree of a vertex i is given by <ref>Servedio V.D.P., G. Caldarelli, P. Buttà, Physical Review E 70, 056126 (2004)</ref> − − :<math>k(\eta_i)=N\int_0^\infty f(\eta_i,\eta_j) \rho(\eta_j) \, d\eta_j </math> 第438行：
第297行： − − If <math>k(\eta_i)</math> is an invertible and increasing function of <math>\eta_i</math>, then − the probability distribution <math>P(k)</math> is given by − − :<math>P(k)=\rho(\eta(k)) \cdot \eta'(k)</math> 第448行：
第302行： − − As a result, if the fitnesses <math>\eta</math> are distributed as a power law, then also the node degree does. − − Less intuitively with a fast decaying probability distribution as − <math>\rho(\eta)=e^{-\eta}</math> together with a linking function of the kind − − :<math> f(\eta_i,\eta_j)=\Theta(\eta_i+\eta_j-Z)</math> 第463行：
第310行： − − − with <math>Z</math> a constant and <math>\Theta</math> the Heavyside function, we also obtain − scale-free networks. − − Such model has been successfully applied to describe trade between nations by using GDP as fitness for the various nodes <math>i,j</math> and a linking function of the kind − <ref>Garlaschelli D., M I Loffredo Physical Review Letters 93, 188701 (2004)</ref> − <ref>Cimini G., T. Squartini, D. Garlaschelli and A. Gabrielli, Scientific Reports 5, 15758 (2015)</ref> − − :<math> \frac{\delta \eta_i\eta_j}{1+ \delta \eta_i\eta_j}.</math>
→网络模型
== 网络模型 ==
== 网络模型 ==
网络模型是理解经验上复杂网络内相互作用的基础，各种各样的[[随机图]]生成的模型所产生的网络结构可与现实中的复杂网络进行比较。
网络模型是理解经验上复杂网络内相互作用的基础，各种各样的[[随机图]]生成的模型所产生的网络结构可与现实中的复杂网络进行比较。
=== Erdős–Rényi 随机图模型 ===
=== [ER随机图模型|Erdős–Rényi 随机图模型] ===
[[File:ER model.svg|thumb|该 [[Erdős–Rényi 模型]] 由 {{math|<VAR>N</VAR> {{=}} 4}} 个节点生成。对于由所有 {{mvar|N}} 个节点构成的完整图中的每一条边，生成一个随机数，并与给定的概率进行比较。假如随机数小于 {{mvar|p}} ，则在模型上形成一条边。]]
[[File:ER model.svg|thumb|该 [[Erdős–Rényi 模型]] 由 {{math|<VAR>N</VAR> {{=}} 4}} 个节点生成。对于由所有 {{mvar|N}} 个节点构成的完整图中的每一条边，生成一个随机数，并与给定的概率进行比较。假如随机数小于 {{mvar|p}} ，则在模型上形成一条边。]]
以[[Paul Erdős]]和[[Alfréd Rényi]]命名的'''[[Erdős–Rényi 模型]]'''用于生成[[随机图]]，它的边是等概率连接的节点的集合。[[随机图]]可以用来证明[[概率方法]]中满足某些条件的图的存在性，或者对几乎所有图给出某个性质的严格定义。
以[[Paul Erdős]]和[[Alfréd Rényi]]命名的'''[[Erdős–Rényi 模型]]'''用于生成[[随机图]]，它的边是等概率连接的节点的集合。[[随机图]]可以用来证明[[概率方法]]中满足某些条件的图的存在性，或者对几乎所有图给出某个性质的严格定义。
生成Erdős–Rényi模型 <math>G(n, p)</math>需要给定两个参数：总的节点数{{mvar|n}}，以及任意两个节点间有连接的概率{{mvar|p}} 。
</math>需要给定两个参数：总的节点数{{mvar|n}}，以及任意两个节点间有连接的概率{{mvar|p}} 。
由于模型是在不偏向特定节点的情况下生成的，因此度分布是二项分布：对任意的节点<math>v</math>
由于模型是在不偏向特定节点的情况下生成的，因此度分布是二项分布：对任意的节点<math>v</math>
</math> 的行为可以分为三个区域：
</math> 的行为可以分为三个区域：
''亚临界'' <math>n p < 1
''亚临界'' <math>n p < 1</math>: 所有分量都是简单而且很小的，其中最大分量的大小为 <math>|C_1| = O(\log n)</math>;
</math>: 所有分量都是简单而且很小的，其中最大分量的大小为 <math>|C_1| = O(\log n)
''临界'' <math>n p = 1</math>: <math>|C_1| = O(n^\frac{2}{3})</math>;
</math>;
''超临界'' <math>n p >1</math>:<math>|C_1| \approx yn</math> 其中 <math>y = y(n p)
</math> 是方程 <math>e^{-p n y }=1-y</math>的正根。
最大的连通分量复杂性最高，其他所有分量都是简单而且很小的 <math>|C_2| = O(\log n)</math>.
最大的连通分量复杂性最高，其他所有分量都是简单而且很小的 <math>|C_2| = O(\log n)
</math>.
=== 配置模型 ===
=== 配置模型 ===
配置模型以一个度序列<ref>{{Cite journal|last=Bender|first=Edward A|last2=Canfield|first2=E.Rodney|date=May 1978|title=The asymptotic number of labeled graphs with given degree sequences|journal=Journal of Combinatorial Theory, Series A|volume=24|issue=3|pages=296–307|doi=10.1016/0097-3165(78)90059-6|issn=0097-3165}}</ref><ref name=":0">{{Cite journal|last=Molloy|first=Michael|last2=Reed|first2=Bruce|date=March 1995|title=A critical point for random graphs with a given degree sequence|journal=Random Structures & Algorithms|language=en|volume=6|issue=2–3|pages=161–180|doi=10.1002/rsa.3240060204|issn=1042-9832|citeseerx=10.1.1.24.6195}}</ref> 或度分布<ref name=":1">{{Cite journal|last=Newman|first=M. E. J.|last2=Strogatz|first2=S. H.|last3=Watts|first3=D. J.|date=2001-07-24|title=Random graphs with arbitrary degree distributions and their applications|journal=Physical Review E|volume=64|issue=2|pages=026118|doi=10.1103/PhysRevE.64.026118|pmid=11497662|arxiv=cond-mat/0007235|bibcode=2001PhRvE..64b6118N}}</ref> （用于生成度序列）作为输入，生成除了度序列外各方面随机连接的图。这意味着对于给定的度序列，图是从符合这个度序列的所有图的集合中随机均匀地选择的。图中任意节点的度<math>k</math>是一个[[独立同分布|独立同分布]]的随机变量，其值为整数。当 <math display="inline">\mathbb E [k^2] - 2 \mathbb E [k]>0</math> 时，配置图包含[[超大分量|超大连通分量]]，其大小是无穷。<ref name=":0" /> 其他分量大小是有限的，可以用大小分布来定量表示。图中任意取的一个节点和大小为<math>n</math>的分量相连接的概率 <math>w(n)</math> 由度分布的[[卷积幂]]给出：<ref>{{Cite journal|last=Kryven|first=Ivan|date=2017-05-02|title=General expression for the component size distribution in infinite configuration networks|journal=Physical Review E|volume=95|issue=5|pages=052303|doi=10.1103/PhysRevE.95.052303|pmid=28618550|arxiv=1703.05413|bibcode=2017PhRvE..95e2303K}}</ref><math display="block">w(n)=\begin{cases}
配置模型以一个度序列<ref>{{Cite journal|last=Bender|first=Edward A|last2=Canfield|first2=E.Rodney|date=May 1978|title=The asymptotic number of labeled graphs with given degree sequences|journal=Journal of Combinatorial Theory, Series A|volume=24|issue=3|pages=296–307|doi=10.1016/0097-3165(78)90059-6|issn=0097-3165}}</ref><ref name=":0">{{Cite journal|last=Molloy|first=Michael|last2=Reed|first2=Bruce|date=March 1995|title=A critical point for random graphs with a given degree sequence|journal=Random Structures & Algorithms|language=en|volume=6|issue=2–3|pages=161–180|doi=10.1002/rsa.3240060204|issn=1042-9832|citeseerx=10.1.1.24.6195}}</ref> 或度分布<ref name=":1">{{Cite journal|last=Newman|first=M. E. J.|last2=Strogatz|first2=S. H.|last3=Watts|first3=D. J.|date=2001-07-24|title=Random graphs with arbitrary degree distributions and their applications|journal=Physical Review E|volume=64|issue=2|pages=026118|doi=10.1103/PhysRevE.64.026118|pmid=11497662|arxiv=cond-mat/0007235|bibcode=2001PhRvE..64b6118N}}</ref> （用于生成度序列）作为输入，生成除了度序列外各方面随机连接的图。这意味着对于给定的度序列，图是从符合这个度序列的所有图的集合中随机均匀地选择的。图中任意节点的度<math>k</math>是一个[[独立同分布|独立同分布]]的随机变量，其值为整数。当 <math display="inline">\mathbb E [k^2] - 2 \mathbb E [k]>0</math> 时，配置图包含[[超大分量|超大连通分量]]，其大小是无穷。<ref name=":0" /> 其他分量大小是有限的，可以用大小分布来定量表示。图中任意取的一个节点和大小为<math>n</math>的分量相连接的概率 <math>w(n)</math> 由度分布的[[卷积幂]]给出：<ref>{{Cite journal|last=Kryven|first=Ivan|date=2017-05-02|title=General expression for the component size distribution in infinite configuration networks|journal=Physical Review E|volume=95|issue=5|pages=052303|doi=10.1103/PhysRevE.95.052303|pmid=28618550|arxiv=1703.05413|bibcode=2017PhRvE..95e2303K}}</ref><math display="block">w(n)=\begin{cases}
=== Watts–Strogatz 小世界模型 ===
=== Watts–Strogatz 小世界模型 ===
[[File:Watts-Strogatz-rewire.png|thumb|[[Watts–Strogatz 模型]]利用重连接的概念构造小世界网络结构。模型生成器会遍历初始晶格结构中的所有边，每一条边会以给定的重连接概率改变它两端的节点，例如<math>\langle k\rangle = 4</math>。]]
[[File:Watts-Strogatz-rewire.png|thumb|[[Watts–Strogatz 模型]]利用重连接的概念构造小世界网络结构。模型生成器会遍历初始晶格结构中的所有边，每一条边会以给定的重连接概率改变它两端的节点，例如<math>\langle k\rangle = 4</math>。]]
[[Watts–Strogatz 模型]]是一个随机图生成模型，能够产生具有[[小世界性质]]的网络。
[[Watts–Strogatz 模型]]是一个随机图生成模型，能够产生具有[[小世界性质]]的网络。
Watts–Strogatz 模型在一个初始的晶格结构的基础上生成。网络中每个节点最初都与它的 <math>\langle k\rangle</math> 个最近邻节点连接。给定另外一个参数为重连接概率，每条边以 <math>p</math> 的概率在图中随机重连。该模型中重连接边数的期望值为 <math>pE = pN\langle k\rangle/2</math>。
Watts–Strogatz 模型在一个初始的晶格结构的基础上生成。网络中每个节点最初都与它的 <math>\langle k\rangle</math> 个最近邻节点连接。给定另外一个参数为重连接概率，每条边以 <math>p</math> 的概率在图中随机重连。该模型中重连接边数的期望值为 <math>pE = pN\langle k\rangle/2</math>。
由于Watts–Strogatz 模型的初始网络具有非随机的晶格结构，因此它具有很高的聚集系数和平均路径长度。每次重新连接都可能在高度连接的集群之间创建一条捷径。随着重连接概率的增加，聚集系数的下降速度慢于平均路径长度的下降速度。实际上，这使得网络的平均路径长度显著降低，而聚集系数只略微降低。更高的重连接概率<math>p</math>会导致更多的边重新连接，这实际上使Watts–Strogatz模型趋于随机网络。
=== Barabási–Albert (BA) 优先链接模型 ===
=== Barabási–Albert (BA) 优先链接模型 ===
[[BA模型]]是一个随机网络模型，用于说明偏好依附效应（优先链接）或“富人越富”效应。在这个模型中，一条边最有可能附着在度数较高的节点上。这个网络从 ''m''<sub>0</sub>节点的初始网络开始。 ''m''<sub>0</sub> ≥ 2时，初始网络中每个节点的度至少为 1，否则它将始终与网络的其余部分断开。
[[BA模型]]是一个随机网络模型，用于说明偏好依附效应（优先链接）或“富人越富”效应。在这个模型中，一条边最有可能附着在度数较高的节点上。这个网络从 ''m''<sub>0</sub>节点的初始网络开始。 ''m''<sub>0</sub> ≥ 2时，初始网络中每个节点的度至少为 1，否则它将始终与网络的其余部分断开。
在BA模型中，每次向网络中添加一个新节点。每个新节点和已有的<math>m</math>个节点相连接，连接的概率与现有节点已拥有的连接数成正比。形式上，新节点与节点 ''i'' 相连的概率 ''p''<sub>''i''</sub> 为 <ref name=RMP>{{Cite journal
在BA模型中，每次向网络中添加一个新节点。每个新节点和已有的<math>m</math>个节点相连接，连接的概率与现有节点已拥有的连接数成正比。形式上，新节点与节点 ''i'' 相连的概率 ''p''<sub>''i''</sub> 为 <ref name=RMP>{{Cite journal
其中 ''k''<sub>''i''</sub> 是节点 ''i'' 的度。大量连接的节点（“中心”）倾向于快速累积更多的连接，而只有少量连接的节点不太可能拥有新连接。新节点“偏好”将自己连接到已经高度连接的节点上。
其中 ''k''<sub>''i''</sub> 是节点 ''i'' 的度。大量连接的节点（“中心”）倾向于快速累积更多的连接，而只有少量连接的节点不太可能拥有新连接。新节点“偏好”将自己连接到已经高度连接的节点上。
[[File:Barabasi-albert model degree distribution.svg|thumb|BA模型的度分布服从幂律。在对数标度中幂律函数是一条直线。<ref name=Barabasi1999>{{Cite journal
[[File:Barabasi-albert model degree distribution.svg|thumb|BA模型的度分布服从幂律。在对数标度中幂律函数是一条直线。<ref name=Barabasi1999>{{Cite journal
中心节点表现出很高的介数中心性，这使得节点之间存在捷径。因此，BA模型的平均路径长度往往很短。该模型的聚集系数也趋于0。
当包括Erdős Rényi随机图模型和一些小世界网络在内的许多模型的直径D正比于log N时，BA模型表现为D~loglogN（超小世界）。<ref>{{cite journal|last=Cohen|first=R. |title=Scale-free networks are ultrasmall|journal=Phys. Rev. Lett.|year=2003|volume=90|pages=058701|url=http://havlin.biu.ac.il/Publications.php?keyword=Scale-free+networks+are+ultrasmall&year=*&match=all|doi=10.1103/PhysRevLett.90.058701|pmid=12633404|first2=S.|last2=Havlin|issue=5|bibcode=2003PhRvL..90e8701C |arxiv=cond-mat/0205476}}</ref> 注意，平均路径长度随N的变化和直径相同。
===中介驱动依附(MDA)模型===
===中介驱动依附(MDA)模型===
在[[中介驱动依附模型|中介驱动依附(MDA)模型]]中，一个带有<math>m</math>边的新节点随机选择一个已连接的节点，然后不与那个节点连接，而是随机地与它的<math>m</math>个相邻节点连接。随机选择已连接节点的概率<math>\Pi(i)</math> 为
在[[中介驱动依附模型|中介驱动依附(MDA)模型]]中，一个带有<math>m</math>边的新节点随机选择一个已连接的节点，然后不与那个节点连接，而是随机地与它的<math>m</math>个相邻节点连接。随机选择已连接节点的概率<math>\Pi(i)</math> 为
因子 <math>\frac{\sum_{j=1}^{k_i}{\frac{1}{k_j}}}{k_i}</math>是节点 <math>i</math>的<math>k_i</math>个相邻节点的度的调和平均 IHM的逆。大量的数值研究表明，对于<math>m> 14</math>，IHM的值在大<math>N</math>极限下会变成常数，这意味着<math>\Pi(i) \propto k_i</math>。这表明一个节点的连接（度）越高，获得更多连接的机会就更大，因为它们可以通过中介以更多的方式连接到，这本质上体现了富人越富机制的直观思想（或者BA模型优先链接的规则）。因此，可以看出MDA网络以伪装的方式遵循优先链接规则。<ref>{{cite journal | last1 = Hassan | first1 = M. K. | last2 = Islam | first2 = Liana | last3 = Arefinul Haque | first3 = Syed | date = March 2017 | title = Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks | doi = 10.1016/j.physa.2016.11.001 | journal = Physica A | volume = 469 | issue = | pages = 23–30 | arxiv = 1411.3444 | bibcode = 2017PhyA..469...23H }}</ref>
然而，当<math>m=1</math> 时，它描述了赢者通吃的机制，因为我们可以发现，几乎<math>99\%</math> 的节点的度仅为1，而某一个节点的度超级大。当<math>m</math>的值增加时，超级富人和穷人之间的差距减小；当<math>m>14</math>时，从赢者通吃机制转变为富人更富机制。
=== 适应度模型 ===
=== 适应度模型 ===
Caldarelli等人引入了另一个模型，其中关键成分是顶点的性质。<ref>Caldarelli G., A. Capocci, P. De Los Rios, M.A. Muñoz, Physical Review Letters 89, 258702 (2002)</ref> 两个顶点<math>i,j</math>之间的连接概率由连接函数<math>f(\eta_i,\eta_j)</math> 给出，该函数是网络节点[[适应性模型（图论）|适应性]]的函数。
Caldarelli等人引入了另一个模型，其中关键成分是顶点的性质。<ref>Caldarelli G., A. Capocci, P. De Los Rios, M.A. Muñoz, Physical Review Letters 89, 258702 (2002)</ref> 两个顶点<math>i,j</math>之间的连接概率由连接函数<math>f(\eta_i,\eta_j)</math> 给出，该函数是网络节点[[适应性模型（图论）|适应性]]的函数。
节点的度由下式给出<ref>Servedio V.D.P., G. Caldarelli, P. Buttà, Physical Review E 70, 056126 (2004)</ref>
节点的度由下式给出<ref>Servedio V.D.P., G. Caldarelli, P. Buttà, Physical Review E 70, 056126 (2004)</ref>
:<math>k(\eta_i)=N\int_0^\infty f(\eta_i,\eta_j) \rho(\eta_j) \, d\eta_j </math>
:<math>k(\eta_i)=N\int_0^\infty f(\eta_i,\eta_j) \rho(\eta_j) \, d\eta_j </math>
如果<math>k(\eta_i)</math>是<math>\eta_i</math>的可逆递增函数，那么<math>P(k)</math>的概率分布为
如果<math>k(\eta_i)</math>是<math>\eta_i</math>的可逆递增函数，那么<math>P(k)</math>的概率分布为
:<math>P(k)=\rho(\eta(k)) \cdot \eta'(k)</math>
:<math>P(k)=\rho(\eta(k)) \cdot \eta'(k)</math>
因此，如果适应性<math>\eta</math>是幂律分布，那么节点的度也遵循幂律分布。
因此，如果适应性<math>\eta</math>是幂律分布，那么节点的度也遵循幂律分布。
不那么直观地，一个快速衰减的概率分布函数
不那么直观地，一个快速衰减的概率分布函数
:<math> f(\eta_i,\eta_j)=\Theta(\eta_i+\eta_j-Z)</math>
:<math> f(\eta_i,\eta_j)=\Theta(\eta_i+\eta_j-Z)</math>
其中 <math>Z</math> 是常数且 <math>\Theta</math> 是 Heavyside函数，我们同样得到了无标度网络。
其中 <math>Z</math> 是常数且 <math>\Theta</math> 是 Heavyside函数，我们同样得到了无标度网络。
该模型已成功地应用于描述国家间贸易，其中GDP作为不同节点 <math>i,j</math> 的适应性，并且连接函数是如下的形式
该模型已成功地应用于描述国家间贸易，其中GDP作为不同节点 <math>i,j</math> 的适应性，并且连接函数是如下的形式