| 第403行： |
第403行： |
| | | | |
| | 由于Watts–Strogatz 模型的初始网络具有非随机的规则结构，它具有很高的聚集系数和平均路径长度。每次重新连接都可能在高度连接的集群之间创建一条捷径。随着重连接概率的增加，聚集系数的下降速度慢于平均路径长度。实际上，这使得网络的平均路径长度显著降低，而聚集系数只略微降低。更高的重连接概率<math>p</math>会导致更多的边重新连接，这实际上使Watts Strogatz模型趋于随机网络。 | | 由于Watts–Strogatz 模型的初始网络具有非随机的规则结构，它具有很高的聚集系数和平均路径长度。每次重新连接都可能在高度连接的集群之间创建一条捷径。随着重连接概率的增加，聚集系数的下降速度慢于平均路径长度。实际上，这使得网络的平均路径长度显著降低，而聚集系数只略微降低。更高的重连接概率<math>p</math>会导致更多的边重新连接，这实际上使Watts Strogatz模型趋于随机网络。 |
| − |
| |
| − | === Barabási–Albert (BA) preferential attachment model ===
| |
| − |
| |
| − | 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>
| |
| − |
| |
| − | 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.
| |
| | | | |
| | ====Mediation-driven attachment (MDA) model==== | | ====Mediation-driven attachment (MDA) model==== |