随机图——节点42，边118
平均度为5.62，集聚系数为0.133。
ER模型
Erdös和Rényi （ER）最早提出随机网络 模型并进行了深入研究，他们是用概率统 计方法研究随机图统计特性的创始人。
给定N个节点，没有边，以概率p用边连接 任意一对节点，用这样的方法产生一随机 网络。
ER模型
小世界实验--- 六度分离
米尔格伦的实验过程是：他计划通过人传人的送信方式来统 计人与人之间的联系。
首先把信交给志愿者A，告诉他信最终要送给收信人S。如果 他不认识S，那么就送信到某个他认识的人B手里，理由是A认 为在他的交集圈里B是最可能认识S的。但是如果B也不认识S， 那么B同样把信送到他的一个朋友C手中，……，就这样一步 步最后信终于到达S那里。这样就从A到B到C到……最后到S连 成了一个链。斯坦利•米尔格伦就是通过对这个链做了统计后 做出了六度分离的结论。
性现实中的网络是由一个个较小的社团组成,而这些社团又可 以包括更小的社团。发现网络中的社团结构,对于了解网络结 构，分析网络特性都具有很重要的意义。
复杂网络研究内容
1）复杂网络模型 典型的复杂网络：随机网、小世界网、无标度网等； 实际网络及其分类。
2）网络的统计量及与网络结构的相关性 度分布的定义和意义，聚集性、连通性的统计量及其实际 意义等。
度(degree)：节点 i 的度 ki 定义为与该节点连接的其他
节点的数目。
★ 直观上看，一个节点的度越大就意味着这个节点在
某种意义上越“重要”（“能力大”）。
网络的平均度：网络中所有节点的度和的平均值
dv
vV G
，记作<k>。
p
度分布函数p(k):随机选定节点的度恰好为k的概率
电力系统复杂网络受到随意攻击
网络图的基本概念
图的基本元素：节点、边
G (V,E)
关联，邻接 有限图，无限图 规则图，随机图 有向图，无向图
度、平均度 节点的度分布 最短路径与平均路径长度 集聚系数
a
b
c
d
e
有向图、无向图、不连通图
复杂网络的统计特征
按分布定义：如果网络中有一定数量的连 接的节点数与此连接数量成减函数，这个 网络就叫无尺度网络。
Scale-free网络的发现
信息交换网（万维网、国际互联网、电话网、电力网） 社会网络（电影演员合作网、科研合作图、引文网、
人类性接触网、语言学网） 生物网络（细胞网络、生态网络、蛋白质折叠）
复杂网Байду номын сангаас的统计特征
最短路径（Shortest path）:两个节点之间边数最少 的路径，最短路径的长度称为两点间的距离.
平均路径长度（特征路径长度）L：
所有节点对之间的距离的平均值.
★ 研究发现：尽管许多实际复杂网络的节点数巨 大，网络的平均路径长度却小的惊人。（小世界效应）
18
复杂网络的统计特征
复杂网络概述
不同领域的真实网络
社会网：演员合作网，友谊网，姻亲关系 网，科研合作网，Email网
生物网：食物链网，神经网，新陈代谢网， 蛋白质网，基因网络
信息网络：WWW，专利使用，论文引用， 计算机共享
技术网络：电力网，Internet，电话线路 网
交通运输网：航线网，铁路网，公路网， 自然河流网
★ 网络介数说明了网络的什么性质？
核数
★ 一个图的k-核：反复去掉图中度小于k 的节点后，所剩余的 子图
★ 若一个节点存在于k-核，而在(k+1)-核中被去掉，则此节点核 数为k
★节点核数中的最大值称为网络图的核数 ★节点核数可以表明节点在核中的深度；即便一个节点的度数 很高，它的核数也可能很小。例如：包含N个节点的星型网络的 中心节点的度数为N-1，但它的核数为1
小世界模型
为了描述从一个局部有序系统到一个随 机网络的转移过程，Watts和 Strogatz （WS）提出了一个新模型，通常称为小 世界网络模型。
WS模型始于一具有N个节点的一维网络， 网络的节点与其最近的邻接点和次邻接 点相连接，然后每条边以概率p重新连接。 约束条件为节点间无重边，无自环。 （一）很小的最短路径长度平均值 （二）很大的群聚系数的小世界网络
3）复杂网络性质与结构的关系 同步性、鲁棒性和稳定性与网络结构的关系。
4）复杂网络的动力学 信息传播动力学、网络演化动力学、网络混沌动力学。
5）复杂网络的复杂结构 社团结构、层次结构、节点分类结构等。
6）网络控制 关键节点控制、主参数控制和控制的稳定性和有效性。
22
7）复杂网络建模 机理建模、数据建模和实际系统的复杂网络正向与逆向建模。
规则图和随机图
规则图
系统中节点及其与边的关系是固定的， 每个节点都有相同的度数。
随机图
平均说来系统中节点及其与边的关系 不确定。
规则图的特征
平均度为3。
随机图的特征
节点确定，但边以概率 p任意连接。
节点不确定，点边关系也不确定。
随机图——节点19，边43
平均度为2.42，集聚系数为0.13。
六度分离: 平均只要通过5个人，你就能与世界任何一个角落的 任何一个人发生联系。这个结论定量地说明了我们世界的”大 小”，或者说人与人关系的紧密程度。
30多年来，六度分离理论一直被作为社会心理学的经典范例之 一。
尽管如此，实际上这个理论并没有得到严格的证实。美国心理 学教授朱迪斯•克兰菲尔德(Judith Kleinfeld)对米尔格伦最初 的实验提出不同意见，因为她发现实验的完成率极低。
3）连接多样性：节点之间的连接权重存在诧异，且有可能存在方向性。
4）动力学复杂性：节点集可能属于非线性动力学系统，例如节点状态随时间发 生复杂变化。 5）节点多样性：复杂网络中的节点可以代表任何事物，例如，人际关系构成的 复杂网络节点代表单独个体，万维网组成的复杂网络节点可以表示不同网页。
6）多重复杂性融合：即以上多重复杂性相互影响，导致更为 难以预料的结果。例如，设计一个电力供应网络需要考虑此网 络的进化过程，其进化过程决定网络的拓扑结构。当两个节点 之间频繁进行能量传输时，他们之间的连接权重会随之增加， 通过不断的学习与记忆逐步改善网络性能
小世界实验—六度分离
我们或许有过这样的经历：偶尔碰到一个陌生人，同他聊了一 会后发现你认识的某个人居然他也认识，然后一起发出”这个 世界真小”的感叹。那么对于世界上任意两个人来说，借助第 三者、第四者这样的间接关系来建立起他们两人的联系平均来 说最少要通过多少人呢？
美国社会心理学家斯坦利•米尔格伦(Stanley Milgram)在1967 年通过一些实验后得出结论：中间的联系人平均只需要5个。他 把这个结论称为“六度分离”。
无标度(Scale-free)网络
现实世界的网络大部分都不是随机网络， 少数的节点往往拥有大量的连接，而大部 分节点却很少。——无标度网络。
这里的无标度是指网络缺乏一个特征度值 （或平均度值），即节点度值的波动范围 相当大。
无标度网络（Scale - free network）
按生长方式定义：如果网络的每个节点的 连接数与此节点产生新连接的概率成增函 数关系，这个网络就叫无尺度网络。
节点的度分布：平均值为 的泊松分布
P(k) eλλk k!
Poisson distribution
三、复杂网络模型
小世界（small-world) 网络模型
无标度 （scale-free) 网络模型
小世界实验
20世纪60年代美国哈佛大学的社会心理学家 Stanley Milgram通过一些社会调查后给出的推 断是：地球上任意两个人之间的平均距离是6。 这就是著名的“六度分离”（six degrees of separation）推断。
人物关系网
社会网络
食物链网
生物网
神经网络
WWW 网
信息网络
电话网
技术网络
公路网
交通运输网
航空网
河流网
复杂网络简而言之即呈现高度复杂性的网络。
1）结构复杂：表现在节点数目巨大，网络结构呈现多种不同特征。
2）网络进化：表现在节点或连接的产生与消失。例如world-widenetwork，网页 或链接随时可能出现或断开，导致网络结构不断发生变化。
BA模型
增长和择优连接这两种要素激励了Barabási－Albert 模型的提出，该模型首次导出度分布按幂函数规律变
化的网络。 模型的算法如下：
（1）增长：开始于较少的节点数量（m0），在每个时间 间隔增添一个具有m（≤m0）条边的新节点，连接这个 新节点到m个不同的已经存在于系统中的节点上。
20
三、社区结构
整个网络是由若干个“社区"或“组’’构成的。每个社 区内部的结点间的连接相对非常紧密，但是各个社区之间 的连接相对来说却比较稀疏（网络中的顶点可以分成组, 组内连接稠密而组间连接稀疏）。我们将复杂网络的这种 结构特征称之为复杂网络的社团结构或社区结构。
社区结构是复杂网络的一个重要的特性，社区也被称为簇， 大量研究表明网络是由各种不同类型的节点构成的，一般 情况下，在不同类型的节点间存在较少的边，而在相同类 型的节点间会有较多的边。位于一个子图内的节点和边组 成一个社团。 复杂网络社区结构还有一个很重要的特性,即是它的层次特
Scale-free网络的特性
度分布呈幂率分布 中枢节点出现 鲁棒性 脆弱性
无标度（Scale-free）网络
无标度模型由Albert-László Barabási和 Réka Albert在1999年首先提出，现实网 络的无标度特性源于众多网络所共有的两 种生成机制： （ⅰ）网络通过增添新节点而连续扩 张； （ⅱ）新节点择优连接到具有大量连 接的节点上。