当前位置：首页 > article >正文

复杂网络之BA无标度网络

article 2025/3/4 12:43:08

现实中的网络有两个方面在以前的网络模型中未包含进去。首先，没有考虑现实网络的增长特性（网络的规模是不断扩大的）。其次，没有考虑现实网络的优先连接特征（新的节点更倾向于与那些具有较高度的“大”节点相连接）

基于网络的增长和优先连接特征，BA无标度网络模型的构造算法如下：

① 增长：从一个具有 $m_{0}$ 个节点的网络开始，每次引入一个新的节点，与m个已存在的节点相连，这里 $m\leq m_{0}$

② 优先连接：一个新节点与一个已经存在的节点 $v_{i}$ 相连接的概率 $\prod _{i}$ 与节点 $v_{i}$ 的度 $k_{i}$ 成正比。

即， $\prod _{i} = \frac{k_{i}}{\sum_{j}^{}k_{j}}$ 。

在经过t步后，这种算法产生一个有 $N = t + m_{0}$ 个节点，mt条边的网络。

生成BA无标度网络编程：

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import random

def barabasi_albert_graph(n0, n, m):
    # 假定初始网络是一个包含n0个节点的完全网络
    G = nx.complete_graph(n0)
    targets = list(range(m))
    repeated_nodes = list(range(n0))*m
    source = n0
    while source < n:
        G.add_edges_from(zip([source] * m, targets))
        repeated_nodes.extend(targets)
        repeated_nodes.extend([source] * m)
        targets = random.sample(repeated_nodes, m)
        targets = set(targets)
        while len(targets) < m:
            x = random.choice(repeated_nodes)
            targets.add(x)
        source += 1
    return G

n0 = 3
m = 2
n = 500
G = barabasi_albert_graph(n0, n, m)
nx.draw(G, with_labels=False, node_size=50,node_color = "red")
plt.show()

BA无标度网络的度动力学：

根据增长性和择优选择，网络将最终演化成一个标度不变的状态，即网络的度分布不随时间而改变（同样也就是不随网络节点数N而改变），经计算得到度值为k的节点的概率正比于幂次项 $k^{-3}$ 。

非线性增长模型：

import igraph as ig
from matplotlib import pyplot as plt


# 定义求度分布的函数(注意是针对igraph类型的图)
def get_pdf_igraph(G):
    all_k = G.degree()
    k = list(set(all_k))  # 获取所有可能的度值
    N = len(all_k)

    Pk = []
    for ki in sorted(k):
        c = 0
        for i in G.vs:
            if G.degree(i) == ki:
                c += 1
        Pk.append(c / N)

    return sorted(k), Pk

n = 100000
m = 3
alpha1 = 0.5
alpha2 = 1.0
alpha3 = 1.5

G1 = ig.Graph.Barabasi(n, m, directed=False, power=alpha1)
G2 = ig.Graph.Barabasi(n, m, directed=False, power=alpha2)
G3 = ig.Graph.Barabasi(n, m, directed=False, power=alpha3)


k1, pk1 = get_pdf_igraph(G1)
k2, pk2 = get_pdf_igraph(G2)
k3, pk3 = get_pdf_igraph(G3)
plt.plot(k1, pk1, "ro", label=r'$\alpha = 0.5$')
plt.plot(k2, pk2, "bs", label=r'$\alpha = 1.0$')
plt.plot(k3, pk3, "gv", label=r'$\alpha = 1.5$')
plt.legend(loc=0)
plt.xscale("log")
plt.yscale("log")
plt.xlabel("$k$")
plt.ylabel("$p(k)$")
plt.show()

BA无标度网络的直径与集聚系数

对于BA网络而言，当m > 1并且N较大时，网络直径为 $\left \langle d \right \rangle \sim \frac{ln N}{ln ln N}$