复杂网络简介

1、复杂网络Complex Network计算机学院 目录1 引言2复杂网络的统计特性3 复杂网络模型4 总结 引言引言 自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的, 其中节点用来代表真实系统中不同的个体, 而边则用来表示个体之间的关系, 通常是当两个节点之间具有某种特定的关系时连一条边, 反之则不连边。有边相连的两个节点在网络中被看作是相邻的。1引言引言复杂网络的发展背景复杂网络的发展背景 例如, 神经系统可以看作是大量神经细胞通过神经纤维相互连接形成的网络；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线

2、、同轴电缆等相互连接形成的网络。类似的还有电力网络、社会关系网络、交通网络等等。1引言引言神经网络计算机网络 数学家和物理学家在考虑网络的时候, 往往只关心节点之间有没有边相连, 至于节点在什么位置, 边长还是短, 是弯曲还是平直, 有没有相交等等都是他们不在意的。因此, 我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质网络的拓扑性质, 相应的结构叫做网络的拓扑结构网络的拓扑结构. 那么, 什么样的拓扑结构比较适用于描述真实的系统呢? 1引言引言 两百多年来, 对这个问题的研究经历了三个阶段。在最初的一百多年里, 科学家们认为真实系统各因素之间的关系可以用一些

3、规则的结构表示, 例如二维平面上的欧几里德格网欧几里德格网, 它看起来像是格子体恤衫上的花纹; 又如最近邻环网最近邻环网, 它总是会让你想到一群手牵着手、围着篝火跳圆圈舞的姑娘. 1引言引言 到了20 世纪50 年代末, 数学家们想出了一种新的构造网络的方法, 在这种方法下, 两个节点之间连边与否不再是确定的事情, 而是根据一个概率决定. 数学家把这样生成的网络叫做随机网络随机网络, 它在接下来的40 年里一直被很多科学家认为是描述真实系统最适宜的网络. 直到最近几年，由于计算机数据处理和运算能力的飞速发展, 科学家们发现大量的真实网络既不是规则网络，也不是随机网络, 而是具有与前两者皆不同的

4、统计特征的网络。这样的一些网络被科学家们叫做复杂网络（复杂网络（Complex Network) )，对于它们的研究标志着第三阶段的到来。1引言引言大规模复杂网络1引言引言复杂网络的定义复杂网络的定义 具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。钱学森统计特性2 最短路径长度、平均最短路径长度、介数1 度、度分布和度相关性2复杂网络的统计特性复杂网络的统计特性3 聚类系数4 社区结构5 层次性2复杂网络的统计特性复杂网络的统计特性度、度分布和度相关性度、度分布和度相关性 无向网络的节点的度度是指与节点连接的边数；而有向网络的节点的度分为入度和出度。网络中所有节

5、点度的列表称为度序列，度序列的平均值称为网络的平均度, 记为。给定了网络的度序列就确定了该网络的度分布。度分布度分布是指从图中随机选择一个节点其度为k的概率，记为P(k)。度分布是网络的最基本的拓扑特性。根据度分布，可以将网络分为随机图、无标度网络和指数网络等。度分布一个非常有用的表示( 生成函数表示法)为:其中pk 表示度为k的节点在网络中的比例. 2复杂网络的统计特性复杂网络的统计特性度、度分布和度相关性度、度分布和度相关性 在随机图模型中, 任意两个节点间相连的概率为p, 即任意节点连接到任意的其它节点的概率都是相同的. 但在许多现实网络中, 存在着一定的混合模式，即一个节点倾向于连接到

6、某一些节点。研究者也发现，许多网络边的两节点间的度也存在依赖关系, 即度度-度相关性度相关性。 如果度高的节点倾向于连接其它度高的节点, 称为同配混合；如果度高的节点倾向于连接其它度低的节点称为异配混合。网络的同配性(异配性)影响网络的结构和行为. 按照度同配混合的网络比对应的异配网络更利于渗流；对于节点删除, 同配混合的网络要比异配和中性的网络更具有鲁棒性.2复杂网络的统计特性复杂网络的统计特性最短路径长度、平均最短路径长度、介数最短路径长度、平均最短路径长度、介数 对于无权网络, 网络中任意两点间的最短路径最短路径是从一个节点到另一个节点的最少边数；对于有权网络, 两点间的最短路径是指权值

7、之和为最小的路径。网络中任意两个节点之间的最短路径长度的最大值称为网络的直径。平均最短路径长度平均最短路径长度是网络中所有节点对之间的最短路径长度的平均值。 平均路径长度可以做为网络信息传递效率的度量, 网络的效率定义为：这里, n表示节点数，dij为两个节点i和j之间的最短路径长度。网络的平均最短路径长度较小的现象称为小世界效应。许多现实网络具有小世界效应，如电影演员网络( 平均最短路径为3.48)，对等网络(平均最短路径为4.28)，代谢网络(平均最短路径是2.56). 2复杂网络的统计特性复杂网络的统计特性最短路径长度、平均最短路径长度、介数最短路径长度、平均最短路径长度、介数 为了度量

8、节点在网络中的重要性中心性，引进了节点介数介数概念，定义如下：边介数是经过这条边的节点对的最短路径数，它在社区发现中为区分一个社区的内部边和社区之间的边提供了一种有效的度量标准.2复杂网络的统计特性复杂网络的统计特性聚类系数聚类系数 二元关系R, 如果aRb, bRc, 那么aRc, 则称R是传递的。熟人网络中，也有类似的特性，即拥有一个共同朋友的两个人他们也彼此熟悉，这种性质称为网络的聚类性，也称为传递性。传递性意味着出现三角形，定义节点i 聚类系数如下：整个网络的聚类系数C就是所有节点i的聚类系数C i的平均值, 且有0 C 1。 对于一些无标度网络, 局部聚类系数Ci 随着节点i的度下降

9、而下降。随机网络的聚类系数为O(n ) ，当网络规模极大时趋于零，而多数现实网络的聚类系数显著大于零，a即具有明显的聚类特性。-2复杂网络的统计特性复杂网络的统计特性社区结构社区结构 社区结构是许多现实网络具有的一个共同的特征, 即网络的节点可以分成几个组, 每个组内部的节点连接稠密, 而组之间的节点连接稀疏，下图是一个包含三个社区的一个简单网络。 社区结构的发现具有重要的意义，例如在WWW 中的社区对应着一组关于某个主题的网页；社会网络中的社区对应着有着共同爱好或背景的一群人；生化网络中的社区则对应着某个复合体或某种功能。因此，社区发现是当前复杂网络研究的一个热点方向，并且已经提出了各种方法

10、，如基于介数度量的方法、随机游走方法、电阻网络方法、拉普拉斯特征值方法、极值优化方法、派系过滤算法等。2复杂网络的统计特性复杂网络的统计特性社区结构社区结构 一个广泛使用的度量网络的社区结构的量是模块度，它定义为：设网络分为n个社区，则定义一个n * n的矩阵e，每一行和每一列都代表一个社区，矩阵元素eij表示社区i和j间的边数占网络总边数的比例，eii就表示社区i内部边所占的比例，ai =eij表示第i行或第i列元素之和, 即与第i个社区的节点相连的边的总比例, 则模块度定义为:即社区内部边的比例减去具有同样社区划分但节点间是随机连接的网络的这一值的期望。Q的值在-1与1之间，Q 越接近1(

11、 这是最大值)预示着具有越强的社区结构。2复杂网络的统计特性复杂网络的统计特性层次性层次性 按层次组织是许多复杂系统的一个共同特征。在代谢网络中，有许多小的连接密集的簇，它们会相互结合形成较大较稀疏的簇，而这些簇又可能进一步形成更大更稀疏的簇。这种自相似地嵌套形成了我们现实网络的严格而又精细的结构。有趣地是，网络的层次性特性, 可以通过简单的量来捕获，即C ( k)曲线满足C(K) k。 Clauset等人建立了一种层次随机图模型，利用该模型对现实网络进行拟合，发现网络的层次结构可以解释网络的许多其它特征，如平均度、聚类系数和最短路径等。发现网络中的连接往往需要在实验室或现场付出高昂的费用，这

12、就使得许多现实网络是不完备的， 在这种情形下预测网络中丢失的连接具有重要的意义。Clauset进一步利用建立的模型设计了一个丢失连接的预测器，它与传统的方法相比, 能够应用于更广泛类型的网络结构。 复杂网络模型复杂网复杂网络模型络模型随机图小世界网络无标度网络BA模型3复杂网络模型复杂网络模型 随机图是图论中最年轻的分支之一，对它的系统研究起源于1959年保罗埃尔德什和阿尔弗雷德雷尼的工作，他们发表了一系列的论文，建立了丰富的随机图理论的基础。现实网络具有复杂的拓扑结构和未知的组织原理，总是呈献出某种随机性，因此用随机图作为网络的模型是最直接的一种选择。 一个随机图实际上是将给定的顶点之间随机

13、地连上边。边的产生可以依赖于不同的随机方式，这样就产生了不同的随机图模型。一个典型的模型是埃尔德什和雷尼共同研究的ER模型。ER模型是指在给定 n 个顶点后，规定每两个顶点之间都以 p 的概率连起来（0 p 1），而且这些判定之间两两无关。这样得到的随机图一般记作 或 ERn(p)。3复杂网络模型复杂网络模型随机图随机图 许多现实网络如技术网络、生物网络和社会网络等，既不是完全规则的，也不是完全随机的，而是介于两者之间。Watts和Strogatz基于这些观察, 提出了WS模型，是指对一个具有n个节点的环格，初始时每个节点有k个邻居，将每条边以概率p进行随机重绕的过程。由于该模型生成的网络具有

14、较短的特征路径，即网络具有小世界效应，故称为小世界网络，WS模型也因此常称为小世界网络(模型)。小世界网络小世界网络3复杂网络模型复杂网络模型 上述的构造过程有可能破坏网络的连通，因此Newman和Watts稍后提出了通过随机化加边的方法构造小世界网络的模型，即NW 模型。还有许多改进的模型：加点、加边、去点、去边以及不同形式的交叉，产生多种形式的小世界模型。 小世界网络具有高的聚类系数，WS小世界网络的聚类系数为：而NW小世界网络的聚类系数为： 小世界网络的典型特征是平均最短路径满足对数标度，但是到目前为止还没有精确的解析表达式。小世界网络的度分布与多数现实网络并不能很好匹配，对于NW模型和

15、WS模型，其表达式都比较复杂。小世界网络小世界网络3复杂网络模型复杂网络模型 节点度服从幂律分布，是指具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地表示，幂函数曲线是一条下降相对缓慢的曲线，这使得度很大的节点可以在网络中存在。对于随机网络和规则网络，度分布区间非常狭窄，几乎找不到偏离节点度均值较大的点，故其平均度可以被看作其节点度的一个特征标度。在这个意义上，我们把节点度服从幂律分布的网络叫做无标度网络无标度网络无标度网络3复杂网络模型复杂网络模型 1999年, Albert-Lszl Barabsi 和Rka Alber受WWW 形成的启发, 提出了构造无标度网络的演

16、化模型，常称为BA模型。该模型考虑了现实网络的两个重要特性：增长特性和择优连接特性。该模型的构成过程如下： 初始时刻有m0个孤立的节点, 在每一个时间步t= 1,2,3, , n-m0 加上一个新的节点j，同时加上从此节点出发的m条边, 将新节点j连接到网络中已经存在的节点，i是按照正比于i的度的规律来选择边的另一端节点：BA模型模型3复杂网络模型复杂网络模型 BA无标度网络的聚类系数为：可见，BA无标度网络不具有高的聚类系数。 BA无标度网络具有小世界特性，其平均路径长度为：BA模型模型3复杂网络模型复杂网络模型总结总结 复杂网络作为一门新兴的交叉学科正处于蓬勃发展阶段，为各学科中的复杂系统提供了一种对其进行认识和处理的统一的框架，同时为处理包括计算机科学在内的许多学科中的复杂问题提供了新的观点和方法。 加入复杂网络研究的学者主要来自图论、统计物理学、计算机网络研究、生态学、社会学以及经济学等领域，研究所涉及的网络主要有：生命科学领域的各种网络（如细胞网络、蛋白质蛋白质作用网络、蛋白质折叠网络、神经网络、生态网络）、Internet/WWW网络、社会网络，包括流行性疾