复杂网络（四）

一、规则网络

1. 孤立节点网络
2. 全局耦合网络（又称完全网络）
3. 星型网络
4. 一维环
5. 二维晶格

编程实践：

import networkx as nx
import matplotlib.pyplot as pltn = 10
#创建孤立节点图
G1 = nx.Graph()
G1.add_nodes_from(list(range(n)))
plt.figure(figsize = (4,4))
nx.draw(G1, pos = nx.circular_layout(G1),with_labels = True, node_size = 500, node_color = 'r', font_size = 10, font_weight = 'bold')
plt.show()#创建完全图
G2 = nx.complete_graph(n)
plt.figure(figsize = (4,4))
nx.draw(G2, pos = nx.circular_layout(G2),with_labels = True, node_size = 500, node_color = 'r', font_size = 10, font_weight = 'bold')
plt.show()#创建一维环状图
G3 = nx.cycle_graph(n)
plt.figure(figsize = (4,4))
nx.draw(G3,pos = nx.circular_layout(G3),node_size = 500, node_color = 'r', font_size = 10, font_weight = 'bold')
plt.show()#创建K近邻(耦合)图
G4 = nx.watts_strogatz_graph(n,4,0)
plt.figure(figsize = (4,4))
nx.draw(G4, pos = nx.circular_layout(G4),with_labels = True, node_size = 500, node_color = 'r', font_size = 10, font_weight = 'bold')
plt.show()#二维方格图
G5 = nx.grid_graph((6,6),periodic=False)
plt.figure(figsize = (4,4))
nx.draw(G5, with_labels = False, node_size = 500, node_color = 'r', font_size = 10, font_weight = 'bold')
plt.show()

二、ER随机网络的生成算法

（1）G(N,L)模型：N个节点通过L条随机放置的链接彼此相连

（2）G(N,p)模型：N个节点中，每对节点之间以概率p彼此相连

G(N,p)步骤如下：

（1）从N个孤立节点开始

（2）选择一对节点，产生一个0到1之间的随机数。如果该随机数小于p，在这对节点之间放置一条链接；否则，该节点对保持不连接。

（3）对所有N(N - 1)/2个节点对，重复步骤。

编程实践：

import random
import itertoolsimport matplotlib.pyplot as plt
import networkx as nxdef GNL(N,L):G = nx.Graph()G.add_nodes_from(range(N))nlist = list(G)edge_count = 0while edge_count < L:u = random.choice(nlist)v = random.choice(nlist)if u == v or G.has_edge(u,v):continueelse:G.add_edge(u,v)edge_count += 1return G
# G = GNL(100,200)def GNP(N,p):edges = itertools.combinations(range(N), 2)G = nx.Graph()G.add_nodes_from(range(N))nlist = list(G)for u,v in itertools.combinations(nlist,2):if random.random() < p:G.add_edge(u,v)return G
# G = GNP(100,0.2)
#可以直接调用库函数来生成这种两种网络
n,m,p = 10,20,0.2
g1 = nx.gnm_random_graph(n,m)
g2 = nx.erdos_renyi_graph(n,p)plt.figure(figsize = (8,4))
nx.draw(g1, pos = nx.circular_layout(g1),with_labels = False, node_size = 500, node_color = 'r', font_size = 10, font_weight = 'bold')
plt.title("G(N,L)")
plt.show()nx.draw(g2, pos = nx.circular_layout(g2),with_labels = False, node_size = 500, node_color = 'r', font_size = 10, font_weight = 'bold')
plt.title("G(N,p)")
plt.show()

三、ER随机网络结构特征

期望连边数，在连接概率为p的ER随机图中，可知其平均度为 pN

ER随机网络的度分布：规模小服从二项分布，规模大时服从泊松分布

编程实践：

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import math
from scipy import stats#定义求度分布函数
def get_pdf(G,kmin,kmax):k = list(range(kmin,kmax + 1))N = len(G.nodes())Pk = []for ki in k:c = 0for i in G.nodes():if G.degree(i) == ki:c += 1Pk.append(c/N)return k,Pksamples = 100 #统计平均
N = [100,1000]kmin,kmax,avk = 20,80,50
s1 = np.zeros(kmax - kmin + 1)
s2 = np.zeros(kmax - kmin + 1)
for i in range(samples):ER1 = nx.gnp_random_graph(N[0],avk/N[0])x1,y1 = get_pdf(ER1,kmin,kmax)ER2 = nx.gnp_random_graph(N[1],avk/N[1])x2,y2 = get_pdf(ER2,kmin,kmax)s1 += np.array(y1)s2 += np.array(y2)#计算二项分布理论值
n = 100
p = 0.5
k = np.arange(20,81)
pk_b = stats.binom.pmf(k,n,p)#计算泊松分布理论值
pk_p = [np.exp(-avk)*(avk**ki)/math.factorial(ki) for ki in range(kmin,kmax + 1)]plt.figure(figsize=(6,4))
plt.plot(x1, s1/samples, 'ro', label='$N = 100$')
plt.plot(x2, s2/samples, 'bs', label='$N = 1000$')
plt.plot(x2, pk_b, 'g-', label='binomial')
plt.plot(x2, pk_p, 'r-', label='poisson')
plt.legend(loc=0)
plt.xlabel("$k$")
plt.ylabel("$p_k$")
plt.xlim([20,80])
plt.show()