198
个编辑
更改
→Barabási–Albert (BA) 优先链接模型
=== Barabási–Albert (BA) 优先链接模型 ===
=== Barabási–Albert (BA) 优先链接模型 ===
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.
[[BA模型]]是一个随机网络模型，用于说明偏好依附效应（优先链接）preferential attachment或“富人越富”效应。 在这个模型中，边最有可能附着在度数较高的节点上。 这个网络从一个 ''m''<sub>0</sub>节点的初始网络开始。 ''m''<sub>0</sub> ≥ 2，初始网络中每个节点的度至少为 1，否则它将始终与网络的其余部分断开。
[[BA模型]]是一个随机网络模型，用于说明偏好依附效应（优先链接）preferential attachment或“富人越富”效应。 在这个模型中，边最有可能附着在度数较高的节点上。 这个网络从一个 ''m''<sub>0</sub>节点的初始网络开始。 ''m''<sub>0</sub> ≥ 2，初始网络中每个节点的度至少为 1，否则它将始终与网络的其余部分断开。
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>
在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
BA模型得到的度分布是无标度的，特别是它的形式是幂律：
BA模型得到的度分布是无标度的，特别是它的形式是幂律：
: <math>P(k)\sim k^{-3} \, </math>
: <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.
中心节点表现出很高的介数中心性，这使得节点之间存在捷径。因此，BA模型的平均路径长度往往很短。该模型的聚类系数也趋于0。
中心节点表现出很高的介数中心性，这使得节点之间存在捷径。因此，BA模型的平均路径长度往往很短。该模型的聚类系数也趋于0。