yanxiaoyong的个人博客分享 http://blog.sciencenet.cn/u/yanxiaoyong 在路上……

博文

复杂网络分析库NetworkX学习笔记(3):网络演化模型

已有 44752 次阅读 2010-6-22 09:22 |个人分类:NetworkX|系统分类:科研笔记| 复杂网络, NetworkX


NetworkX提供了4种常见网络的建模方法,分别是:规则图,ER随机图,WS小世界网络和BA无标度网络。本文首先介绍在NetworkX生成这些网络模型的方法,然后以BA无标度网络的建模为例,分析利用NetworkX进行复杂网络演化模型设计的基本思路,以便将来开发出我们自己的模型。同时这篇文章里还涉及到一点复杂网络可视化的方法(后边有时间会另文介绍网络可视化的方法)。


一、规则图

规则图差不多是最没有复杂性的一类图了,在NetworkX中,用random_graphs.random_regular_graph(d, n)方法可以生成一个含有n个节点,每个节点有d个邻居节点的规则图。下面是一段示例代码,生成了包含20个节点、每个节点有3个邻居的规则图:

import networkx as nx
import matplotlib.pyplot as plt
RG = nx.random_graphs.random_regular_graph(3,20)  #生成包含20个节点、每个节点有3个邻居的规则图RG
pos = nx.spectral_layout(RG)          #定义一个布局,此处采用了spectral布局方式,后变还会介绍其它布局方式,注意图形上的区别
nx.draw(RG,pos,with_labels=False,node_size = 30)  #绘制规则图的图形,with_labels决定节点是非带标签(编号),node_size是节点的直径
plt.show()  #显示图形


运行结果如下:

图1   NetworkX生成的规则图


二、ER随机图

ER随机图是早期研究得比较多的一类“复杂”网络,这个模型的基本思想是以概率p连接N个节点中的每一对节点。在NetworkX中,可以用random_graphs.erdos_renyi_graph(n,p)方法生成一个含有n个节点、以概率p连接的ER随机图:

import networkx as nx
import matplotlib.pyplot as plt
ER = nx.random_graphs.erdos_renyi_graph(20,0.2)  #生成包含20个节点、以概率0.2连接的随机图
pos = nx.shell_layout(ER)          #定义一个布局,此处采用了shell布局方式
nx.draw(ER,pos,with_labels=False,node_size = 30)
plt.show()

运行结果如下:

图2   NetworkX生成的随机图


三、WS小世界网络

在NetworkX中,可以用random_graphs.watts_strogatz_graph(n, k, p)方法生成一个含有n个节点、每个节点有k个邻居、以概率p随机化重连边的WS小世界网络,下面是一个例子:

import networkx as nx
import matplotlib.pyplot as plt
WS = nx.random_graphs.watts_strogatz_graph(20,4,0.3)  #生成包含20个节点、每个节点4个近邻、随机化重连概率为0.3的小世界网络
pos = nx.circular_layout(WS)          #定义一个布局,此处采用了circular布局方式
nx.draw(WS,pos,with_labels=False,node_size = 30)  #绘制图形
plt.show()

运行结果如下:

图3   NetworkX生成的WS小世界网络


四、BA无标度网络

在NetworkX中,可以用random_graphs.barabasi_albert_graph(n, m)方法生成一个含有n个节点、每次加入m条边的BA无标度网络,下面是一个例子:

import networkx as nx
import matplotlib.pyplot as plt
BA= nx.random_graphs.barabasi_albert_graph(20,1)  #生成n=20、m=1的BA无标度网络
pos = nx.spring_layout(BA)          #定义一个布局,此处采用了spring布局方式
nx.draw(BA,pos,with_labels=False,node_size = 30)  #绘制图形
plt.show()

运行结果如下:


图4   NetworkX生成的BA无标度网络

 

五、对BA模型实现代码的分析

前面我们介绍了NetworkX提供的4种网络演化模型的应用方法,但仅停留在使用已有的模型是不够的,实际工作中我们可能会自己开发一些网络演化模型。利用NetworkX提供的数据结构,我们可以比较方便的完成这一工作。下面以NetworkX中BA模型的实现代码为例,分析用NetworkX开发网络演化模型的一般思路。NetworkX中关于网络建模的代码在random_graphs.py这个文件中,可以用记事本打开它。为了叙述简便起见,我删掉了原始代码中的一些错误处理与初始条件定义的语句,红色部分是翻译后的注释。

#定义一个方法,它有两个参数:n - 网络节点数量;m - 每步演化加入的边数量
def barabasi_albert_graph(n, m):
    # 生成一个包含m个节点的空图 (即BA模型中t=0时的m0个节点)
    G=empty_graph(m) 
    # 定义新加入边要连接的m个目标节点
    targets=range(m) 
    # 将现有节点按正比于其度的次数加入到一个数组中,初始化时的m个节点度均为0,所以数组为空
    repeated_nodes=[]    
    # 添加其余的 n-m 个节点,第一个节点编号为m(Python的数组编号从0开始)
    source=m
    # 循环添加节点
    while source<n:
        # 从源节点连接m条边到选定的m个节点targets上(注意targets是上一步生成的)
        G.add_edges_from(zip([source]*m,targets))
        # 对于每个被选择的节点,将它们加入到repeated_nodes数组中(它们的度增加了1)
        repeated_nodes.extend(targets)
        # 将源点m次加入到repeated_nodes数组中(它的度增加了m)
        repeated_nodes.extend([source]*m)
        # 从现有节点中选取m个节点 ,按正比于度的概率(即度优先连接)
        targets=set()
        while len(targets)<m:
            #按正比于度的概率随机选择一个节点,见注释1
            x=random.choice(repeated_nodes)
            #将其添加到目标节点数组targets中
            targets.add(x)       
        #挑选下一个源点,转到循环开始,直到达到给定的节点数n
        source += 1
    #返回所得的图G
    return G

注释1:此步是关键,random.choice方法是从一个数组中随机地挑选一个元素。由于repeated_nodes数组中的节点出现次数是正比于节点度的,所以这样处理可以保证按度大小的概率选出节点,即实现了度优先连接。如果是按正比于节点适应性等非整数值优先连接,可以参考我的另一篇博文《根据值的大小随机取数组元素的方法》。


六、小结

NetworkX的优势之一就是开源,这也是所有Python库的优势(Python是脚本语言,它没有办法隐藏源代码)。NetworkX的源代码结构清晰,风格简练,注释详尽,是学习、研究复杂网络不错的参考资料。当然在这方面我也是初学者,更多的功能还需要在实际应用中不断去发掘和领会…………








复杂网络研究
https://blog.sciencenet.cn/blog-404069-337689.html

上一篇:复杂网络分析库NetworkX学习笔记(2):统计指标计算
下一篇:复杂网络分析库NetworkX学习笔记(4):网络可视化

3 黄富强 伊振中 violetcoming

发表评论 评论 (21 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-12-2 08:54

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部