在網絡理論中,無尺度網絡(或稱無标度網絡)是帶有一類特性的複雜網絡,其典型特征是在網絡中的大部分節點隻和很少節點連接配接,而有極少的節點與非常多的節點連接配接。這種關鍵的節點(稱為“樞紐”或“集散節點”)的存在使得無尺度網絡對意外故障有強大的承受能力,但面對協同性攻擊時則顯得脆弱。現實中的許多網絡都帶有無尺度的特性,例如網際網路、金融系統網絡、社會人際網絡等等。
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的期望值即為無标度網絡平均度的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 ([email protected])
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()
計算平均度結構為:
我們可以得到的BA網絡如下圖:
度分布如下圖:
當節點數越大,Pi愈加符合真實網絡分布時,平均度分布将更加接近給定值,同時網絡更加符合幂律分布
參考文獻:
何凱,楊學剛,楊愚魯.給定平均連接配接度的無标度網絡演化模型[J].計算機工程,2006(17):181-183.