复杂网络之BA无标度网络

2024/12/27 2:49:57 来源：https://blog.csdn.net/weixin_64443786/article/details/144187468 浏览: 次关键词：复杂网络之BA无标度网络

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

基于网络的增长和优先连接特征，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 randomdef barabasi_albert_graph(n0, n, m):# 假定初始网络是一个包含n0个节点的完全网络G = nx.complete_graph(n0)targets = list(range(m))repeated_nodes = list(range(n0))*msource = n0while 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 += 1return Gn0 = 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 = 0for i in G.vs:if G.degree(i) == ki:c += 1Pk.append(c / N)return sorted(k), Pkn = 100000
m = 3
alpha1 = 0.5
alpha2 = 1.0
alpha3 = 1.5G1 = 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}$