在网络理论中,无尺度网络(或称无标度网络)是带有一类特性的复杂网络,其典型特征是在网络中的大部分节点只和很少节点连接,而有极少的节点与非常多的节点连接。这种关键的节点(称为“枢纽”或“集散节点”)的存在使得无尺度网络对意外故障有强大的承受能力,但面对协同性攻击时则显得脆弱。现实中的许多网络都带有无尺度的特性,例如因特网、金融系统网络、社会人际网络等等。

Albert-László Barabási 和Réka Albert为了解释幂律的产生机制,提出了无标度网络模型(BA模型)。BA模型具有两个特性:

其一是增长性,所谓增长性是指网络规模是在不断的增大的,在研究的网络当中,网络的节点是不断的增加的;

其二就是优先连接机制,这个特性是指网络当中不断产生的新的节点更倾向于和那些连接度较大的节点相连接。BA模型对很多的现象都是可以解释的,例如研究生对导师的选择,在这个网络当中,研究生和导师都是不断增加的,而研究生总是倾向于选择已经带过很多研究生的导师。

在Python的NetworkX包中提供了无标度网络生成的方法,可以用random_graphs.barabasi_albert_graph(n, m)方法生成一个含有n个节点、每次加入m条边的BA无标度网络

该算法基本包含两个步骤,即

(1)增长:从一个具有 m_0 个节点的联通网络开始,每次引入一个新的节点, 并且连到 m 个已经存在的节点上,这里 m <= m_0。

(2)优先连接:一个新的节点与一个已经存在的节点 i 相连的概率 w 与节点 i 的度 k_i 之间的关系为 w = k_i / ( k_1 + k_2 + k_3 + ... + k_n ),其中n为网络中的节点的总个数。

但该种方法生成了固定节点数以及每次加入边数目的网络,如果通过给定的平均连接度生成无标度网络,则需要另寻思路。

通过参考论文 何凯,杨学刚,杨愚鲁.给定平均连接度的无标度网络演化模型[J].计算机工程,2006(17):181-183. 可以在遵循BA网络生长和优先附着的原则之下,生成固定无标度网络。

在每一个时间步中增加一个新的节点,与 BA 模型不同的是,该新节点不是增加固定的 m 个连接,而是按照某个给定的概率 Pi 增加 i 个连接。

基本分为初始阶段和主体阶段。在初始阶段,新连接选择网络中孤立的节点作为另一端点,直到网络中不存在孤立的节点,初始阶段结束。在主体阶段,按照优先附着的原则添加新的连接。

 

因此,通过Python实现这一算法,首先需要确定概率分布Pi,Pi的期望值即为无标度网络平均度<k>的1/2,Pi根据真实网络的一些统计数据,如低连接度节点在网络中所占的比率来确定,例如生成1000个节点,初始节点数为5,平均度为2.4的BA网络,我们首先可以确定一个Pi为[0.86, 0.08, 0.06], 满足期望值为0.86*1+0.08*2+0.06*3=2.4的条件

Python具体实现可如下所示:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2018-04-04 10:06:14
# @Author  : liulichao (llc@ruc.edu.cn)

import os

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

#总的节点数
node_num = 1000
#初始节点数
m_0 = 5
#每次给定概率分布,该分布期望值为q,也就是平均连接度/2所得值,用于确定每次增加的连接数
p = [0.86, 0.08, 0.06]

#根据概率分布取相应位置数
def random_choice(seq):
	ran = random.random()*sum(seq)
	sumtmp = 0
	N = seq.__len__()
	for i in range(N):
		sumtmp += seq[i]
		if sumtmp > ran:
			a = i
			return a + 1
	return -1

def barabasi_albert_graph(n, m_0):
	# 生成一个包含m个节点的空图 (即BA模型中t=0时的m0个节点) 
	G = nx.empty_graph(m_0)
	
	# 添加其余的 n-m 个节点,第一个节点编号为m(Python的数组编号从0开始)
	source = m_0
	repeated_nodes=[]

	# 初始阶段,连接每一个点
	init_node = list(range(m_0))
	while(len(init_node) > 0):
		edge = random_choice(p)
		targets = []
		while(len(targets) < edge and len(init_node) > 0):
			x = random.choice(init_node)
			targets.append(x)
			init_node.remove(x)

		G.add_edges_from(zip([source] * edge, targets))
		repeated_nodes.extend(targets)
		repeated_nodes.extend([source] * edge)
		source += 1

	
	#主体阶段
	while(source < n):
		# 定义新加入边要连接的边的数量
		edge = random_choice(p)
		targets=set()
		# 按正比于度的概率进行优先连接
		while(len(targets) < edge):
			#按正比于度的概率随机选择一个节点
			x = random.choice(repeated_nodes) 
			#将其添加到目标节点数组targets中
			targets.add(x)

		# 从源节点连接m条边到选定的m个节点targets上(注意targets是上一步生成的)
		# zip函数将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表
		G.add_edges_from(zip([source] * edge, targets)) 
		# 对于每个被选择的节点,将它们加入到repeated_nodes数组中(它们的度增加了1)
		repeated_nodes.extend(targets)
		# 将源点m次加入到repeated_nodes数组中(它的度增加了m)
		repeated_nodes.extend([source] * edge) 
		
		#挑选下一个源点,转到循环开始,直到达到给定的节点数n
		source += 1 
	#返回所得的图G
	return G

G = barabasi_albert_graph(node_num , m_0)

degree_total = 0;
for x in range(len(G.degree())):
	degree_total = degree_total + G.degree(x);

print('平均连接度为:',degree_total/node_num)

ps=nx.spring_layout(G)  #布置框架  
nx.draw(G , ps, with_labels=False, node_size=30)  
plt.show()

#返回图中所有节点的度分布序列
degree = nx.degree_histogram(G)
#生成x轴序列,从1到最大度
x = range(len(degree))
#将频次转换为频率,这用到Python的一个小技巧:列表内涵,Python的确很方便:)           
y = [z / float(sum(degree)) for z in degree]
#在双对数坐标轴上绘制度分布曲线
plt.loglog(x, y, color="blue", linewidth=2)
#显示图表       
plt.show()

 

计算平均度结构为:

Python实现给定平均连接度的无标度网络演化模型-数字人文技术实验室

我们可以得到的BA网络如下图:

Python实现给定平均连接度的无标度网络演化模型-数字人文技术实验室

度分布如下图:

Python实现给定平均连接度的无标度网络演化模型-数字人文技术实验室

当节点数越大,Pi愈加符合真实网络分布时,平均度分布将更加接近给定值,同时网络更加符合幂律分布

 

参考文献:

何凯,杨学刚,杨愚鲁.给定平均连接度的无标度网络演化模型[J].计算机工程,2006(17):181-183.

networkx--四种网络模型:https://www.cnblogs.com/forstudy/archive/2012/03/20/2407954.html

复杂网络分析库NetworkX学习笔记(3):网络演化模型:http://blog.sciencenet.cn/blog-404069-337689.html