致 谢
 
至此论文完成之际，我的短暂的研究生生涯也即将结束。回首三年生活，历
 
历在目，不禁感慨万千，自己所得之进步，诚非一人之力，离不开众人之理解与
 
支持，关心和帮助。在此，我谨向在科研和生活中帮助过我，支持过我的每一位
 
老师，同学和朋友表示衷心的感谢！没有你们，就没有我今日的成果。同时也向
 
奋斗在复杂网络领域的同仁们致以崇高的敬意！是你们众策群力，推动了这一领
 
域在中国的继续前进。
 
言有所尽，不能尽表其意；篇有所限，不能一一列出。然而我的导师冯文峰
 
教授，是我首先需要感谢的，在他悉心的指导和鼓励下，我跨进了复杂系统和复
 
杂网络这个大门，并产生了浓厚的兴趣。他亲切的关心我的学习和生活，孜孜不
 
倦的解答我在科研中所遇到的各种问题，本论文从选题到构思，都得到了导师的
 
大力支持和指导。导师渊博的知识，活跃的思想，严谨的治学作风都给我留下了
 
深刻的印象。
 
再次感谢所有帮助，支持和关心我的人们！
 
最后感谢国家自然科学基金对该项目的资助！
 
摘 要
 
在自然界和人类社会，网络是普遍存在的，如基因网络，神经网络，人际交互
 
网络，因特网等等，对复杂网络的研究，可以使我们更好的理解自然界和人类社
 
会中所出现的一些现象，并加以控制。网络作为一门用来研究复杂系统的新学科，
 
近几年来得到了学术界的广泛关注，其中网络的拓扑结构对系统功能的影响，网
 
络上的演化动力学对网络结构与行为的影响等逐渐成为了各领域研究者所研究的
 
热点问题。
 
本文首先介绍了复杂网络与演化博弈的一些基本概念，然后对随机网络，无标
 
度网络和小世界网络这三种常见的网络模型进行了介绍。此外，还对网络上的演
 
化博弈的研究现状做了简单的回顾。
 
在第二章中，建立了在信息不完备情况下的多人间接博弈模型，在该模型中存
 
在两种个体：决策者和选择者，决策者可以选择自己的策略，选择者根据决策者
 
的策略来选择自己的邻居，其中决策者的信息对选择者并不是完全透明的。然后
 
从理论上推导出了在系统达到稳定态时网络的度分布与决策者的合作频率分布之
 
间的函数关系，并得出了系统在达到博弈均衡态时所满足的条件，给出了当合作
 
者占优时系统所要满足的条件。最后，用计算机模拟了规则网络上的演化动态，
 
分析了平均邻居个数对演化结果的影响。
 
在第三章中，建立了基于博弈意愿的演化博弈模型，该模型假定每个个体存在
 
一个博弈意愿，代表了该个体与邻居交互的概率，每对邻居之间进行博弈的概率
 
为两者博弈意愿的乘积。然后，分别研究了其在随机网络、无标度网络和小世界
 
网络上的演化行为。通过对模拟结果进行分析，得出了一些比较有意思的结论。
 
在最后一章中，对该领域的研究进行了总结与展望。
 
关键词：复杂网络；演化博弈；囚徒困境；合作行为；信息完备性；多人间接
 
博弈；博弈意愿
 
I
 
II
 
Abstract
 
In nature and human society, the network is ubiquitous, such as gene networ
 
ks, neural networks, interpersonal interaction networks and internet etc. The resea
 
rch on complex networks can lead us a better understand of the phenomenon ari
 
sing from national world and human society. As a new subject in the research o
 
f complex system, the study of network has been paid more attention by academ
 
e in recent years.

1.定义
 
网络演化（evolution），通过网络演化构建网络结构是对网络进行定量研究的基础，对网络的运营管理，大规模网络行为的理解等方面具有重要影响。
 
2.演化模型分类
 
1按照网络演化的部件来分
 
（1)基于点、边的网络演化模型
 基于点、边的网络演化模型是指:在网络演化过程中，网络中的节点和边都可增加或删除的演化模型。 BA模型是典型的基于点、边的网络演化模型，新加入的节点会引入新边连接到已有的老节点。BA模型是基于增长和择优连接2个原理提出的。增长原理强调了网络节点的演化，择优连接强调了网络边的演化。BA模型具有幂律度分布的特性，但有些特性与真实网络的测试结果不符。许多模型在此基础上进行了改进
 （2）基于边的网络演化模型
 基于边的网络演化模型是指：在网络演化过程中，网络中的节点数目保持不变，但是边可以增加或者减少的演化模型。ER模型在给定的节点之间采用随机连边策略产生随机图模型；WS模型在给定的节点之间采用边重连的策略产生小世界网络模型；
 
2.以是否考虑权重来分
 
（1)无权网络演化模型
 
网络的边没有赋予权重，则该网络是无权网络。基本的BA，WS，ER都是无权网络演化模型。根据BA模型的网络增长和择优连接2条规则，这些模型可分为两类：修改增长规则的无权网络演化模型和修改连接规则的无权网络演化模型。
 无权网络演化模型主要针对网络的拓扑演化机制进行研究而不考虑网络的功能、承载业务等。演化结论主要是通过对网络拓扑结构的评判（是否具有幂律度分布特性、小世界效应等）来验证。故无权网络演化模型与实际网络的演化还有一定的差距。
 
（2）含权网络演化模型
 
网络的边赋予相应的权重，则该网络就成为含权网络或加权网络。现实世界的网络几乎都是加权网络。
 
3.以演化网络采用的演化机制来分
 
（1) 单一演化机制模型
 
是指，网络在演化过程中只采取一种演化机制的模型，如BA，WS等以及基于这些模型的改进模型都是单一演化机制的模型。
 
（2) 混合演化机制模型
 
是指，网络在演化过程中，采取多种演化机制的模型
 
4.以演化网络是否动态来分
 
在相邻2个时间步内，网络节点及节点之间的关系（边）一直保持不变，则将这类网络称为静态网络，大多数都是静态演化模型

 
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
 
# 从源节点连接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://blog.sciencenet.cn/blog-404069-337689.html
 
上一篇：复杂网络分析库NetworkX学习笔记(2)：统计指标计算
 
下一篇：复杂网络分析库NetworkX学习笔记(4)：网络可视化

一 概述
 
1.2 复杂网络特征和类型
 
复杂网络一般具有随机、小世界、无标度、超小世界、社区结构、分形结构等。依据这些特征将复杂网络分为随机网络、小世界网络、无标度网络、超小世界网络、社区网络、分形网络等。
 1.2.1 随机网络
 
1959年Erdos和Renyi提出了可以通过网络节点间以不变的概率p随机的布置连线来有效模拟通 信和生命科学中的网络。在此模型中，节点的度分布遵循泊松分布，E-R模型所生成的随即网络具有节点之间聚集程度较低的现象和较大的特征路径长度。
 
1.2.2 小世界网络
 
研究结果表示：很多实际网络的平均最短路径长度较小，而聚集系数相对较大，具有这样特性的网络被称为小世界网络。从现实生活中很容易理解小世界现象。假如你有在火车上和陌生人聊天的经历，说不定就会发现，陌生人和你是一个城市的或者在一个小区里生活过，甚至你们拥有共同的朋友。很多人会有这样的遭遇，发现世界真的很小。这就是小世界描述的现象。
 
1998年Watts和Strogatz在Nature上发表论文提出了“小世界模型”，即WS模型。该模型包含网络较大的聚集系数和随即网络较小的平均距离，能描述完全规则网络到完全随机网络之间的转变，即小世界现象是一种中间形态。
 1.2.3 无标度网络
 
Barabasi和Albert和Adamic发现，Web网页的连接和随机图论预测的不一样，每个网页的入度非常不均衡，服从幂律分布，所谓幂律分布，指变量x的分布函数为一个幂函数。幂函数具有一些有趣的性质，如自相似性，例如树干进行分叉形成树枝并不断重复最终变成了一棵树。对于自相似的事物不具备特征的尺度或标度，把自相似的一部分放大，可得到整体的图像，但无法找到一个特征量来定义事物的尺寸大小。这就是“无标度”的由来。
 Barabasi和Albert 提出的BA模型于1999年发表在Nature上，认为，无标度网络是演化生成的网络，该网络源于种子网络，种子网络依据偏好性连接规则生长，由此可得到无标度网络。偏好连接指的是，新加入系统的节点更倾向于链接到具有较大度值的节点上。节点具有一致的偏好，导致具有较大度值的节点会获得越来越多的连接体现富者更富的现象，也就是马太效应。
 
1.2.4 超小世界网络
 
WS模型刻画的小世界网络其中网络度分布为指数分布。Cohen和Havlin 计算了度分布为幂律分布情形下的网络平均距离。当幂指数为为2~3时，平均距离近似于ln(ln(N))，N为网络节点数，当大于3时，平均距离近似于ln(N),ln(ln(N))远小于ln(N),所以在一定情形下，网络平均距离比小世界还小，这种现象成为超小世界。
 1.2.5 网络社区结构
 
我们常说“物以类聚人以群分”。当用网络来刻画具有聚类特性的事物时，网络必然也会呈现聚类的特性。在复杂网络领域，每个聚类后的子网络称为社区;具有聚类特性的网络称为具有社区结构的网络，也称社区网络。
 
社区网络特点：社区之间的边较少较稀疏，社区内部的边较多较稠密。社区划分算法（GN）算法，由Newman和Girvan提出，该算法基于边介数的定义。边介数定义为：网络中所有最短路径中经过该边的路径的数目占最短路径总数的比例。
 
GN算法思想：逐步删除边介数最大的边，使得网络被分割成互不联通的子网络。这些互不联通的子网络可以视为社区。
 1.2.6 网络分形结构
 
有研究探讨了长度转换情形下的网络自相似性，即网络的分形结构。宋朝鸣等也通过重整化方法计算了一些实际网络的额合资技术分型维度，指出有些网络是分形网络，有些网络不是分形网络
 
 
 
学习笔记参考自郑波尽《复杂网络的结构与演化》