BA网络模型

来自集智百科
跳转到: 导航搜索

目录

BA Model 的平均场理论

Barabási, Albert-László; Albert, Réka. (October 15, 1999). "Emergence of scaling in random networks". Science. 286 (5439): 509–512. arXiv:cond-mat/9910332 Freely accessible. Bibcode:1999Sci...286..509B. [1]


R. Albert, A.-L. Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics 74, 47-97 (2002) [2]

H. Jeong - Z. Néda - A. L. Barabási (2003) Measuring preferential attachment in evolving networks. Europhys. Lett., 61 (4), p. 567 [3]


模型设定

  • 初始状态有m_0个节点
  • 1. 增长原则:每次加入一个节点i (加入时间记为t_i), 每个节点的加入带来m条边,2m个度的增加
    • 其中老节点分到的度数是m,新加入的那一个节点分到的度数为m
    • 那么到时间t的时候,网络的总节点数是m_0 + t,网络的总度数为2mt
  • 2. 优先链接原则:每一次从m条边中占有一条边的概率正比于节点的度k_i
    • 那么显然,加入的越早(t_i越小)越容易获得更多的链接数。
    • 从时间0开始,每一个时间步系统中的节点度k_i是不断增加的。

度的增长/时间依赖性

k_i在一个时间步获得一个度的概率表示为\prod (k_i) , 那么有:

\prod (k_i)  = \frac{k_i}{\sum k_i} =  \frac{k_i}{2mt}

一个时间步,k_i随t的变化率可以表达为:

\frac{\partial k_i}{\partial t} = \Delta k \prod (k_i) = m \frac{k_i}{2mt} = \frac{k_i}{2t}

\frac{\partial k_i}{k_i} = \frac{\partial t}{2t}

\int \frac{1}{k_i} d k_i = \int \frac{1}{2t} dt

积分结果为:

k_i =(Ct) ^ {0.5} 公式(1)

此时,根据模型的初始条件,每个新加入节点获得的度是m:

k_i(t_i) = m 代入公式(1)

可以得到C = m^{2}/t_i 公式(2)

代入公式(1),得到:

k_i = m (\frac{t}{t_i})^{0.5} 公式(3)

对于一个节点i,其加入网络的时间t_i是固定的,我们可以观察其度k_i随着时间的幂律关系。

H. Jeong - Z. Néda - A. L. Barabási (2003) Measuring preferential attachment in evolving networks. Europhys. Lett., 61 (4), p. 567 [4]

累积概率分布

当我们思考一个累积概率分布的时候,我们想要的是k_i(t) < k的概率:P(k_i(t) < k)

由公式(3),可以知道:

P(k_i(t)  \frac{m^2 t}{k^2} ) = 1 - P(t_i \leqslant \frac{m^2 t}{k^2} ) 公式(4)

在初始状态 t = 0, 有m_0个节点,那么t_{m_0} = 0

假设我们将节点加入的时间步是均匀的,那么t_i的概率是一个常数:

P(t_i) = \frac{1}{m_0 + t} 公式(5)

均匀分布的性质

  • 设连续型随机变量X的概率密度函数为 f(x)=1/(b-a),a≤x≤b, 则称随机变量X服从[a,b]上的均匀分布,记为X~U[a,b]。
  • 若[x1,x2]是[a,b]的任一子区间,则 P{x_1≤x≤x_2}=(x_2-x_1)/(b-a).

根据均匀分布的性质,将公式(5)代入公式(4)得到:

P(k_i(t) < k)  = 1-  \frac{m^2 t}{k^2} P(t_i)  =  1 - \frac{m^2 t}{k^2 (m_0 + t)} 公式(6)


对累积概率函数求微分,就可以到达概率密度函数:

P( k ) = \frac{\partial P(k_i(t) < k)}{\partial k} = \frac{2m^2 t}{m_0 + k} \frac{1}{k^3} 公式(7)

也就是说:\gamma = 3, 与m无关。

Implementation

def barabasi_albert_graph(n, m, seed=None):
    if m < 1 or m >= n:
        return []
 
    if seed is not None:
        random.seed(seed)
 
    plot_G = nx.empty_graph(n)
 
    nx.draw_circular(plot_G, with_labels=True, font_weight='bold')
    pos = nx.circular_layout(plot_G)
    ax = plt.gca()
#     yield ax
 
    # Add m initial nodes (m0 in barabasi-speak)
    G = nx.empty_graph(m)
    # Target nodes for new edges
    targets = list(range(m))
    # List of existing nodes, with nodes repeated once for each adjacent edge
    repeated_nodes = []
    # Start adding the other n-m nodes. The first node is m.
    source = m
    while source < n:
        G.add_edges_from(zip([source] * m, targets))
 
        plot_G = nx.empty_graph(m)
        plot_G.add_edges_from(zip([source] * m, targets))
 
        nx.draw_networkx_edges(plot_G, pos, ax=ax)
        yield ax
 
        # Add edges to m nodes from the source.
 
        # Add one node to the list for each new edge just created.
        repeated_nodes.extend(targets)
        # And the new node "source" has m edges to add to the list.
        repeated_nodes.extend([source] * m)
        # Now choose m unique nodes from the existing nodes
        # Pick uniformly from repeated_nodes (preferential attachement)
        targets = nx.random_graphs._random_subset(repeated_nodes, m)
        source += 1
    return G

[仓库地址]

References

  1. Barabási, Albert-László; Albert, Réka. (October 15, 1999). "Emergence of scaling in random networks". Science. 286 (5439): 509–512. arXiv:cond-mat/9910332 Freely accessible. Bibcode:1999Sci...286..509B.
  2. R. Albert, A.-L. Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics 74, 47-97 (2002)
  3. H. Jeong - Z. Néda - A. L. Barabási (2003) Measuring preferential attachment in evolving networks. Europhys. Lett., 61 (4), p. 567
  4. H. Jeong - Z. Néda - A. L. Barabási (2003) Measuring preferential attachment in evolving networks. Europhys. Lett., 61 (4), p. 567
个人工具
名字空间
操作
导航
工具箱