图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

# 从源节点连接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)

#按正比于度的概率随机选择一个节点，见注释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的源代码结构清晰，风格简练，注释详尽，是学习、研究复杂网络不错的参考资料。当然在这方面我也是初学者，更多的功能还需要在实际应用中不断去发掘和领会…………

本文引用地址： http://www.sciencenet.cn/m/user_content.aspx?id=337689

* 本文仅代表博主个人观点，与科学网无关。

本文标签： 复杂网络 NetworkX

相关文章：

[转载]复杂网络常见的数据和程序代码网站

[转载]复杂网络资源

会议视频分享：Multi-disciplinary approach of complexity,...

节点度相关性对无标度网络上随机游走的影响 [转载]幂率分布研究的实验数据——圣达菲研究所 [转载]第六届全国复杂网络学术会议[大会日程安排] 一类复杂网络的新家族：广义Farey树网络及其三维金字塔

[转载]复杂网络的新应用（结构力学） 揭示复杂性：从经典分形到复杂网络

人群密集经济是―万堵之源‖！

当前推荐数：2 推荐人： huangfuqiang yizhenzhong

推荐到博客首页评论顺排 [5] 标题：

发表评论人：[游客]amazon [2010-6-29 0:15:47] ip:158.132.150.*

1、 Networkx的图采用了 字典-字典-字典 结构，这个很特殊，不是邻接矩阵或链表。

请老师举例讲一下，比如对于一个三角形，3个点，3个边，或者4个点全连接，对应的 G 的数据结构是

什么样子的。

举例有助于快速理解。 2。

G.add_edges_from(zip([source]*m,targets)) 这个不理解。

zip 函数像C++ java 一样也是返回值的吗？返回的难道是一个二维数组？

比如zip([4 4],[0 2])产生：【4 4；0 2】

add_edges_from 又具体是怎么弄？估计前提得理解 G 的―字典-字典-字典‖

博主回复：1、例如对于图A-B-C，它的数据结构是{A: {B: {}}, C: {B: {}}, B: {A: {}, C: {}}}（注意每个字母前后都有单引号，这回复有问题，把引号给过滤掉了，详细说明请参见http://networkx.lanl.gov/reference/introduction.html）

2、zip([4,4],[0,2])返回[(4, 0), (4, 2)]，zip([1,2,3],[4,5,6])返回[(1, 4), (2, 5), (3, 6)]

3、add_edges_from((4, 0), (4, 2))相当于依次运行：add_edge(4,0)和add_edge(4,2)，它的含义是从一个二元组构成的数组中依次将每个二元组作为一条边添加到图中。希望以上回答你能满意。另外如果你对这个库感兴趣，建议你装一个Python和NX自己编几行代码，很快就会熟悉它。光看代码有时候难以体会含义，要先熟悉Python的元组（Tuple，相当于不可变数组）、列表（List，相当于可变数组）和字典（Dict，就是哈希表）这三种基本数据结构，以及Python的函数编程思想。

[4] 标题：

发表评论人：[游客]amazon [2010-6-28 22:50:25] ip:158.132.150.*

对python 语法不懂 推测：

#类似于 C++ 的函数

def barabasi_albert_graph(n, m):

# 生成一个包含m个节点的空图----猜：G 不是一个邻接矩阵呢，也不是一个链表的数据结构，更可能是一个类的对象， G=empty_graph(m)

# range(5) 函数的结果是一个数组：【0 1 2 3 4】，和matlab的：0:1:4一样 targets=range(m)

# 提供一个摸彩票用的黑箱子，开始是空的， repeated_nodes=[]

----------------------------补注 repeated_nodes---------------------------

# 以后会装2个黄球，5个红球，12个蓝球，胳膊申请去，闭上眼睛摸球。。。要摸出m个球。 # 如果 node-0 的degree是2，node-1 的degree是5，node-2 的degree是7， # 则repeated_nodes=[0 0 1 1 1 1 1 2 2 2 2 2 2 2 ], # 这样等概率随机选择时，node2 被选中的概率高。

# repeated_nodes 最大是一个 n*m*2 大小的数组，内存消耗，超出了栈的大小，可能影响速度 --------------------------------------------------------------------------

# 开始有了m个节点，分别是：0 1 2 ... m-1, 所以下一个要添加的是m，最后一个是n-1 # Python的数组编号从0开始 source=m

# 循环添加节点,python的while不用大括号，不用end 完全靠对齐？ while source

# 从源节点连接m条边到选定的m个节点targets上（注意targets是上一步生成的）

# 猜测是从empty_graph类中继承了一个method：add_edges_from

# 但是不知道zip([source]*m,targets)是什么意思，[source]*m 似乎是source 执行m次 # python特殊的语法习惯？

G.add_edges_from(zip([source]*m,targets))

# extend是数组自有的一个功能，把某个数复制几个，加到数组里，默认复制一个。 repeated_nodes.extend(targets) repeated_nodes.extend([source]*m)

# 清空箱子 targets=set()

然后挑m个新的node装到箱子里,为下一轮连接m条边用 while len(targets)

x=random.choice(repeated_nodes)

targets.add(x) ---- 换成 targets.extend(x) 似乎也对。 #挑选下一个源点，转到循环开始，直到达到给定的节点数n source += 1 #返回所得的图G return G

博主回复：你分析得很正确。Python是很怪，但是很简单，你和我一开始一样，受C++毒害太深了，嘿嘿，不好转变过来：）其实Python很简单优美。回答你的一些问题（可能我理解的也不对）：

1、 Networkx的图采用了 字典-字典-字典 结构，这个很特殊，不是邻接矩阵或链表。

2、 Python完全靠缩进定义代码快，所以程序可读性很好（因为是强制的，不像C++等语言不同人会写出不同风格的代码来）

3、 Zip是拉链函数，它把两个数组的元素一对一的对应起来组成一个二维数组（想象一下拉链的样子）。 4、 [source]*m 是生成一个含有m个source的数组 5、 extend是扩展数组，它接受另一个数组作为参数 6、 add也是扩展数组，但它只接受一个元素作为参数