专题4-复杂性网络资料
- 格式：ppt
- 大小：2.90 MB
- 文档页数：58
下载文档原格式
合集下载
复杂网络的基础知识
第二章复杂网络的基础知识2.1 网络的概念所谓“网络”（networks），实际上就是节点（node）和连边（edge）的集合。
如果节点对（i，j）与（j，i）对应为同一条边，那么该网络为无向网络（undirected networks），否则为有向网络（directed networks）。
如果给每条边都赋予相应的权值，那么该网络就为加权网络（weighted networks），否则为无权网络（unweighted networks），如图2-1所示。
图2-1 网络类型示例(a) 无权无向网络(b) 加权网络(c) 无权有向网络如果节点按照确定的规则连边，所得到的网络就称为“规则网络”（regular networks），如图2-2所示。
如果节点按照完全随机的方式连边，所得到的网络就称为“随机网络”（random networks）。
如果节点按照某种（自）组织原则的方式连边，将演化成各种不同的网络，称为“复杂网络”（complex networks）。
图2-2 规则网络示例(a) 一维有限规则网络(b) 二维无限规则网络2.2 复杂网络的基本特征量描述复杂网络的基本特征量主要有：平均路径长度（average path length ）、簇系数（clustering efficient ）、度分布（degree distribution ）、介数（betweenness ）等，下面介绍它们的定义。
2.2.1 平均路径长度（average path length ）定义网络中任何两个节点i 和j 之间的距离l ij 为从其中一个节点出发到达另一个节点所要经过的连边的最少数目。
定义网络的直径（diameter ）为网络中任意两个节点之间距离的最大值。
即}{max ,ij ji l D = （2-1） 定义网络的平均路径长度L 为网络中所有节点对之间距离的平均值。
即∑∑-=+=-=111)1(2N i N i j ij lN N L （2-2）其中N 为网络节点数，不考虑节点自身的距离。
复杂网络概述
大家好
14
一、复杂网络的定义
社团结构特性：
人以类聚，物以群分。复杂网络 中的节点往往也呈现出集群特性。 例如，社会网络中总是存在熟人 圈或朋友圈，其中每个成员都认 识其他成员。集群程度的意义是 网络集团化的程度；这是一种网 络的内聚倾向。连通集团概念反 映的是一个大网络中各集聚的小 网络分布和相互联系的状况。例 如，它可以反映这个朋友圈与另 一个朋友圈的相互关系。
小世界特性： 小世界特性又被称之为是六度 空间理论或者是六度分割理论。 小世界特性指出：社交网络中 的任何一个成员和任何一个陌 生人之间所间隔的人不会超过 六个。
大家好
13
一、复杂网络的定义
无标度特性：
现实世界的网络大部分都不是随 机网络，少数的节点往往拥有大 量的连接，而大部分节点却很少， 节点的度数分布符合幂率分布， 而这就被称为是网络的无标度特 性。将度分布符合幂律分布的复 杂网络称为无标度网络。
大家好
15
二、复杂网络中的基本概念
度(degree)：节点i的度 ki 定义为与该节点连接的其他节点的
数目,对于有向网络分为出度和入度。 ★ 直观上看，一个节点的度越大就意味着这个节点在
某种意义上越“重要”（“能力大”）。
网络的平均度：网络中所有节点的度和的平均值,记作<k>，并且 <k>=2M/N，M为网络中的边数，N为节点数。
最近杂网络的结构模型
随机网络
（1）初始化：给定N个节点以及连边概率p （2）随机连边：
①选择一对没有边相连的不同的节点。 ②生成一个随机数r ③如果r<p,那么在这对节点之间添加一条边；否则就不 添加边。 ④重复步骤①—③，直到所有的节点对都被选择过一次。
复杂网络
复杂网络的应用
在现实生活中复杂网络的应用很广。
比如：
1.城市交通网络计算机网络更是 最适宜的研究对象系统； 2.在制造业运用复杂网络技术在 企业合作、产品供应链、客户关系网 络、产品结构网络及产品制造过程网， 如零部件通透性分析、零部件用量预 测等应用。
谢谢观看！
P=1
小世界网络：节点不增加，且每个节点有
大约相同的连接数，满足泊 松分布。
无标网络：由初始给定的一个具有m个节点的 网络开始，增加新节点，增加新 连接（偏好性）。
无 标 网 络
复杂网络具有：平均路径长度（The average pathlength）、
聚类系数（The clustering coefficient）、 度分布（The degree distribution） 等基础特性。 其他 特性：
复杂网络的免疫策略
无标网络很容易受到病毒攻击而导致病毒流行，因此选择合适的免疫策略 就更加重要。
三种无标网络的免疫策略： 1.随机免疫（random immunization）， 也称均匀免疫（uniform immunization）; 2.目标免疫（targeted immunization）, 选择免疫（selected immunization ）; 3.熟人免疫（acquaintance immunization）.
复杂网络
钱学森给出了复杂网络（Complex Network）的一个比较严格的定义： 具有自组织、自相似、吸引子、小世 界、无标度中部分或全部性质的网络 称为复杂网络。
钱学森
不要 失去 信心， 只要 坚持 不懈， 就终 会有 成果 钱伟长、钱学森、钱三强 的。 “中国三钱”
格Байду номын сангаас斯堡七桥问题
PPT—复杂网络.ppt
20
三、社区结构
整个网络是由若干个“社区"或“组’’构成的。每个社 区内部的结点间的连接相对非常紧密，但是各个社区之间 的连接相对来说却比较稀疏（网络中的顶点可以分成组, 组内连接稠密而组间连接稀疏）。我们将复杂网络的这种 结构特征称之为复杂网络的社团结构或社区结构。
社区结构是复杂网络的一个重要的特性，社区也被称为簇， 大量研究表明网络是由各种不同类型的节点构成的，一般 情况下，在不同类型的节点间存在较少的边，而在相同类 型的节点间会有较多的边。位于一个子图内的节点和边组 成一个社团。 复杂网络社区结构还有一个很重要的特性,即是它的层次特
复杂网络的统计特征
网络的聚类系数C：所有节点i的聚类系数Ci的平均值。
（0C1） C=0网络中所有节点都是孤立点 C=1网络中任意节点间都有边相连
★ 网络节点间联系的密切程度, 体现网络的凝聚力
★ 许多大规模的实际网络都具有明显的聚类效应。事实 上，在很多类型的网络(如社会关系网络)中，你的朋友同 时也是朋友的概率会随着网络规模的增加而趋向于某个非 零常数，即当N→∞时，C=O(1)。这意味着这些实际的复杂 网络并不是完全随机的，而是在某种程度上具有类似于社 会关系网络中“物以类聚，人以群分”的特性。
性现实中的网络是由一个个较小的社团组成,而这些社团又可 以包括更小的社团。发现网络中的社团结构,对于了解网络结 构，分析网络特性都具有很重要的意义。
复杂网络研究内容
1）复杂网络模型 典型的复杂网络：随机网、小世界网、无标度网等； 实际网络及其分类。
2）网络的统计量及与网络结构的相关性 度分布的定义和意义，聚集性、连通性的统计量及其实际 意义等。
节点的数目。
★ 直观上看，一个节点的度越大就意味着这个节点在
三、社区结构
整个网络是由若干个“社区"或“组’’构成的。每个社 区内部的结点间的连接相对非常紧密，但是各个社区之间 的连接相对来说却比较稀疏（网络中的顶点可以分成组, 组内连接稠密而组间连接稀疏）。我们将复杂网络的这种 结构特征称之为复杂网络的社团结构或社区结构。
社区结构是复杂网络的一个重要的特性，社区也被称为簇， 大量研究表明网络是由各种不同类型的节点构成的，一般 情况下，在不同类型的节点间存在较少的边，而在相同类 型的节点间会有较多的边。位于一个子图内的节点和边组 成一个社团。 复杂网络社区结构还有一个很重要的特性,即是它的层次特
复杂网络的统计特征
网络的聚类系数C：所有节点i的聚类系数Ci的平均值。
（0C1） C=0网络中所有节点都是孤立点 C=1网络中任意节点间都有边相连
★ 网络节点间联系的密切程度, 体现网络的凝聚力
★ 许多大规模的实际网络都具有明显的聚类效应。事实 上，在很多类型的网络(如社会关系网络)中，你的朋友同 时也是朋友的概率会随着网络规模的增加而趋向于某个非 零常数，即当N→∞时，C=O(1)。这意味着这些实际的复杂 网络并不是完全随机的，而是在某种程度上具有类似于社 会关系网络中“物以类聚，人以群分”的特性。
性现实中的网络是由一个个较小的社团组成,而这些社团又可 以包括更小的社团。发现网络中的社团结构,对于了解网络结 构，分析网络特性都具有很重要的意义。
复杂网络研究内容
1）复杂网络模型 典型的复杂网络：随机网、小世界网、无标度网等； 实际网络及其分类。
2）网络的统计量及与网络结构的相关性 度分布的定义和意义，聚集性、连通性的统计量及其实际 意义等。
节点的数目。
★ 直观上看，一个节点的度越大就意味着这个节点在
PPT—复杂网络
随机图——节点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的概率
复杂网络概述
大家好
26
三、复杂网络的结构模型
小世界网络
大家好
27
三、复杂网络的结构模型
小世界网络
C(p) : 平均聚集系数 L(p) : 平均最短路径
大家好
28
• 算法来源
PageRank算法
通过人工进行网页 分类并整理出高质 量的网站
计算用户查询关键 词与网页内容的相 关程度来返回搜索 结果
大家好
29
大家好
34
作战体系节点重要性分析
机械化战争时代, 在通信手段和 指挥控制手段受限的情况下, 作 战体系, 形成了一种树状结构。
随着指挥信息系统的功能越来越
强，作战体系任何两个节点之间
均可以根据需要建立联系，逐步
形成网络化结构。
大家好
35
作战体系节点重要性分析
•作战体系结构的网络描述
依据复杂网络理论, 可以定义作战 体系由节点集合 V 和 边 集 合 E 组 成 的 图 G = (V , E) 。其中, V = {v1,v2 ,…,vn}, 代表组成作 战体系的指挥控制节点、预警侦察 节点（包括战场态势信息源节点和 目标信息源节点）、攻防交战节点 等； E ={e1,e2 ,…,em}, 代表节点之间信息传递关系。
） 目
（3 K 4(K
2） 1)
Lnc（ N1/2） Nm /122m/k2 Nk
一般情况下, 聚集系数较大, 平均最短路径较长。
最近邻耦合网络
大家好
24
三、复杂网络的结构模型
随机网络
（1）初始化: 给定N个节点以及连边概 率p
（2）随机连边:
①选择一对没有边相连的不同的节点。
②生成一个随机数r
复杂网络
上一个复杂网络模型 ， 即 “ 小世界网络模 型”。
Figure 14.SW模型(1)
34
3.3 影响复杂网络拓扑结构的性能的因素是什么
• SW: SW:
Figure 15.SW模型(2)
35
3.3 影响复杂网络拓扑结构的性能的因素是什么
• CAVE:与SW模型类似，只不过CAVE模型首先会将拥有N个节 CAVE: SW模型类似 只不过CAVE模型首先会将拥有N 模型类似， CAVE模型首先会将拥有
MF（Most Frequent Contacts）方法： Contacts）方法： MF（
• 任意一对节点（u和v）都保存有一个计数器c｛u,v｝，该 任意一对节点（ 都保存有一个计数器c u,v｝
计数器记录着这个相遇在过去发生的次数。 计数器记录着这个相遇在过去发生的次数。
• c｛least,n｝记录着网络中具有最少次数的相遇的ID和次 least,n｝记录着网络中具有最少次数的相遇的ID ID和次
Figure 7.药物复杂网络带权图
18
1.3 复杂网络的主要表现方面
Figure 8.社会关系网
19
1.3 复杂网络的主要表现方面
• 动力学复杂性： 节点集可能属于非线性动力学系统， 例 动力学复杂性： 节点集可能属于非线性动力学系统，
如节点状态随时间发生复杂变化。 如节点状态随时间发生复杂变化。
如果不存在外部指令，系统按照相互默契的某种规则， 织 ； 如果不存在外部指令 ， 系统按照相互默契的某种规则 ， 各尽其责而又协调地自动地形成有序结构，就是自组织。 各尽其责而又协调地自动地形成有序结构，就是自组织。
Figure 1.网络自组织
5
1.1 复杂网络的概念
Figure 14.SW模型(1)
34
3.3 影响复杂网络拓扑结构的性能的因素是什么
• SW: SW:
Figure 15.SW模型(2)
35
3.3 影响复杂网络拓扑结构的性能的因素是什么
• CAVE:与SW模型类似，只不过CAVE模型首先会将拥有N个节 CAVE: SW模型类似 只不过CAVE模型首先会将拥有N 模型类似， CAVE模型首先会将拥有
MF（Most Frequent Contacts）方法： Contacts）方法： MF（
• 任意一对节点（u和v）都保存有一个计数器c｛u,v｝，该 任意一对节点（ 都保存有一个计数器c u,v｝
计数器记录着这个相遇在过去发生的次数。 计数器记录着这个相遇在过去发生的次数。
• c｛least,n｝记录着网络中具有最少次数的相遇的ID和次 least,n｝记录着网络中具有最少次数的相遇的ID ID和次
Figure 7.药物复杂网络带权图
18
1.3 复杂网络的主要表现方面
Figure 8.社会关系网
19
1.3 复杂网络的主要表现方面
• 动力学复杂性： 节点集可能属于非线性动力学系统， 例 动力学复杂性： 节点集可能属于非线性动力学系统，
如节点状态随时间发生复杂变化。 如节点状态随时间发生复杂变化。
如果不存在外部指令，系统按照相互默契的某种规则， 织 ； 如果不存在外部指令 ， 系统按照相互默契的某种规则 ， 各尽其责而又协调地自动地形成有序结构，就是自组织。 各尽其责而又协调地自动地形成有序结构，就是自组织。
Figure 1.网络自组织
5
1.1 复杂网络的概念
复杂网络概述ppt课件
.
二、复杂网络中的基本概念
度(degree)：节点i的度 ki 定义为与该节点连接的其他节点的
数目,对于有向网络分为出度和入度。 ★ 直观上看，一个节点的度越大就意味着这个节点在
某种意义上越“重要”（“能力大”）。
网络的平均度：网络中所有节点的度和的平均值,记作<k>，并且 <k>=2M/N，M为网络中的边数，N为节点数。
二、复杂网络中的基本概念
最短路径（Shortest path）:两个节点之间边数最少
的路径，最短路径的长度称为两点间的距离，用dij 平均路径长度（特征路径长度）L：
所有节点对之间的距离的平均值。
★ 研究发现：尽管许多实际复杂网络的节点数巨大， 网络的平均路径长度却小的惊人。（小世界效应）
.
三、复杂网络的结构模型
.
一、复杂网络的定义
钱学森给出了复杂网 络的一个较严格的定义： 具有自组织、自相似、吸 引子、小世界、无标度中 部分或全部性质的网络称 为复杂网络。
.
一、复杂网络的定义
小世界特性： 小世界特性又被称之为是六度 空间理论或者是六度分割理论。 小世界特性指出：社交网络中 的任何一个成员和任何一个陌 生人之间所间隔的人不会超过 六个。
边的介数： Bij N lm eij / N lm 所l,有m l,mi;,ljm 式中，Nlm表示节点vl和vm之间的最短路径条数，Nlm （eij）表示节点vl和vm之间的最短路径经过边eij的条数
.
二、复杂网络中的基本概念
★ 许多大规模的实际网络都具有
明显的聚类效应。事实上，在很多类 型的网络(如社会关系网络)中，你的 朋友同时也是朋友的概率会随着网络 规模的增加而趋向于某个非零常数， 即当N→∞时，C=O(1)。这意味着这 些实际的复杂网络并不是完全随机的， 而是在某种程度上具有类似于社会关 系网络中“物以类聚，人以群分”的 特. 性。
二、复杂网络中的基本概念
度(degree)：节点i的度 ki 定义为与该节点连接的其他节点的
数目,对于有向网络分为出度和入度。 ★ 直观上看，一个节点的度越大就意味着这个节点在
某种意义上越“重要”（“能力大”）。
网络的平均度：网络中所有节点的度和的平均值,记作<k>，并且 <k>=2M/N，M为网络中的边数，N为节点数。
二、复杂网络中的基本概念
最短路径（Shortest path）:两个节点之间边数最少
的路径，最短路径的长度称为两点间的距离，用dij 平均路径长度（特征路径长度）L：
所有节点对之间的距离的平均值。
★ 研究发现：尽管许多实际复杂网络的节点数巨大， 网络的平均路径长度却小的惊人。（小世界效应）
.
三、复杂网络的结构模型
.
一、复杂网络的定义
钱学森给出了复杂网 络的一个较严格的定义： 具有自组织、自相似、吸 引子、小世界、无标度中 部分或全部性质的网络称 为复杂网络。
.
一、复杂网络的定义
小世界特性： 小世界特性又被称之为是六度 空间理论或者是六度分割理论。 小世界特性指出：社交网络中 的任何一个成员和任何一个陌 生人之间所间隔的人不会超过 六个。
边的介数： Bij N lm eij / N lm 所l,有m l,mi;,ljm 式中，Nlm表示节点vl和vm之间的最短路径条数，Nlm （eij）表示节点vl和vm之间的最短路径经过边eij的条数
.
二、复杂网络中的基本概念
★ 许多大规模的实际网络都具有
明显的聚类效应。事实上，在很多类 型的网络(如社会关系网络)中，你的 朋友同时也是朋友的概率会随着网络 规模的增加而趋向于某个非零常数， 即当N→∞时，C=O(1)。这意味着这 些实际的复杂网络并不是完全随机的， 而是在某种程度上具有类似于社会关 系网络中“物以类聚，人以群分”的 特. 性。
复杂网络现象研究及分析方法
复杂网络现象研究及分析方法复杂网络是由大量节点和相互连接的边构成的网络系统，其结构和行为具有复杂性和非线性特征。
在各个领域中，复杂网络都广泛存在，并包含着丰富的信息和规律。
研究复杂网络现象和分析其特征可以帮助我们更好地理解和解释现实世界中的复杂系统，如社交网络、生物网络、物流网络等。
本文将介绍复杂网络现象的研究内容和分析方法。
一、复杂网络现象的研究内容1. 结构特征分析复杂网络的结构特征是指网络中节点之间连接的方式和模式。
研究网络的结构特征可以揭示网络的整体性质和发展规律。
其中最基本的结构特征是度分布，即节点连接的数量分布情况。
例如，某些网络中存在少数节点连接数非常高，而大多数节点连接数较低的现象，被称为幂律分布。
其他常见的结构特征还包括聚类系数、平均路径长度等。
2. 动力学分析复杂网络的动力学特征是指网络系统随时间演化和变化的行为。
动力学分析可以研究网络中节点的演化规律、信息传播模式和系统的稳定性等。
例如，研究在网络中引入节点或删除节点的效果，可以探究网络系统的鲁棒性和脆弱性。
此外，通过分析网络中信息传播的路径和速度，可以预测疾病传播、舆论演化等现象。
3. 同步现象研究复杂网络中的同步现象是指网络节点之间在时间上出现一致演化的现象。
同步现象广泛存在于自然界和社会系统中，如心脏的跳动、脑区的激活等。
研究同步现象可以揭示网络系统中节点之间的相互作用和调控机制。
例如，通过构建耦合节点的模型，可以发现节点之间的同步阈值和同步模式。
二、复杂网络分析方法1. 大数据处理复杂网络研究中常常涉及到大规模数据集的处理和分析。
大数据处理方法可以帮助整理和提取网络中的信息，并准确计算各种指标和特征。
例如，常用的大数据处理技术包括图算法、机器学习、数据挖掘等。
这些方法能够快速处理大量数据，并发现隐藏的规律和模式。
2. 网络建模与仿真复杂网络的建模和仿真是研究网络现象和分析方法的重要手段。
通过构建合适的数学模型和复杂网络的拓扑结构，可以模拟网络中的行为和动态过程。
《复杂网络简介》课件
100%
小世界网络
指网络中节点间的平均距离很短 ，即信息在网络中传播的速度很 快。
80%
随机网络
节点和边的出现是随机过程的结 果，网络结构相对均匀。
03
复杂网络的演化
网络演化的基本规律
自相似性
复杂网络在演化过程中表现出 自相似性，即在不同尺度上网 络的结构和性质具有相似性。
无标度性
复杂网络中节点的度分布遵循 幂律分布，即少数节点拥有大 量连接，而大多数节点只有少 数连接。
小世界效应
复杂网络中的节点平均距离较 小，信息在网络中传播迅速。
网络演化的机制
01
02
03
增长
随着时间的推移，网络中 的节点数量不断增加，新 的节点通过与已有节点建 立连接加入网络。
优先连接
新加入的节点更倾向于与 已有节点中连接数较多的 节点建立连接，从而形成 层次结构。
自组织
网络中的节点通过局部规 则和相互作用，在演化过 程中形成复杂的结构和模 式。
复杂网络的重要性
揭示现实世界中复杂系统的内在规律和机制
复杂网络是描述现实世界中复杂系统的重要工具，可以帮助我们 揭示系统内在的规律和机制。
促进跨学科研究
复杂网络涉及多个学科领域，如数学、物理、计算机科学、社会 学等，通过复杂网络的研究可以促进跨学科的合作与交流。
复杂网络的应用领域
01
02
03
04
网络控制的基本概念
1 2
状态反馈控制
通过测量节点的状态，并利用状态反馈控制方法 调整节点的输入，实现网络的控制。
输出反馈控制
通过测量节点的输出，并利用输出反馈控制方法 调整节点的输入，实现网络的控制。
3
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
其它相关因素
局域世界内的偏好连接 节点和链接的随机或优先消亡 节点间非线性优先连接 新节点所带来的外部链接及网络内新增的 内部链接
网络的可靠性分析
命题：如果大部分节点发生瘫痪，将不可 避免地导致网络的分裂。 分析：
随机的意外故障 恶意的集散节点攻击
随机网络可靠性分析
无尺度网络可靠性-意外故障
小世界模型关于生理病毒传播的研究
运用小世界模型研究SARS病毒的传播
构造小世界网络的方法
引入少量长程的“断键重连”或建立少量 重要结点间的捷径
无尺度网络现象
1998年，Albert-Laszlo Barabasi和Eric Bonabeau 开展一个描绘万维网的项目时，预测会发现一个随 机网络。
根据Scale-free定律再利 用CNNIC提供的下列数据，
经计算最后得出
由此得知中国互联网的幂数 大约为2.124。 依此模型推算，当99.5以上 的网站连接数均低于100次 时，却有万分之四的网站大 于1000次，十万分之三的网 站超出100000次。 因此，只要整合2至3千个网 站作为主流资源，就可以在 很大的程度上满足老百姓的 日常需求。
网络结构特征与复杂性网络
主要内容
复杂性网络研究 规则网络与随机网络 无标度网络与小世界网络
概况
自然界中存在的大量复杂系统都可以通过 形形色色的网络加以描述。例如，神经系 统网络、计算机网络、电力网络、社会关 系网络、交通网络等等。 网络由许多节点与连接两个节点之间的一 些边组成的，节点代表真实系统中不同的 个体，而边则用来表示个体间的关系。
小世界网络的可靠性分析
小世界应用_小世界特性对级联故障的影响
小世界网络所特有的较小特征路径长度和较高聚 类系数等特性，对故障的传播起到推波助澜的作 用。这是由于，一般地，聚类系数对应着故障传 播的广度，特征路径长度代表着故障传播的深度， 而特征路径越小，故障在网络中传播的深度越大。 小世界网络兼具大的深度和宽的广度，所以传播 的速度和影响范围大大高于相应的规则网络和随 机网络。
然而，实测结果却推翻了这个预测。
Internet
World Wide Web
HTTP ( Hypertext Transfer Protocol )
无尺度网络节点度的分布
"幂次定律":任何节点与其他 k个节点相连结的概率，与 l/k成正比。幂次定律不像钟 形曲线那样具有一个峰值， 而是由连续递减的函数来描 述。如果用双对数坐标系来 描述幂次定律，得到的是一 条直线。与随机网络中连结 的民主分布不同，幂次定律 所描述的，是由少数集散节 点(如Yahoo和Google)所主 控的系统。
无尺度网络可靠性-恶意攻击
无尺度网络可靠性—CERNet
无尺度网络可靠性—CERNet
无尺度网络的社会问题
传统传播扩散理论局限性（临界值问题）
生理病毒--随机接种疫苗VS普遍接种疫苗 网络病毒--所有病毒都可在网络中传播和长期存在 选举机制
社会网络中集散节点确定方法
无尺度网络与小世界特性的统一
P(k) e λ λ k k!
复杂性网络
复杂性网络区别于人们已经熟悉的规则网 络和随机网络的拓扑几何特征，对于复杂 性网络的研究有助于科学家揭示现实复杂 世界更多的未知内在联系。
小世界(Small world)网络特征 无尺度(Scale-free)网络特征
小世界网络效应
1967年，美国哈佛大学的社会心理学家 Milgram “六度分离”实验发现，人际网络 具有“小世界”的特性，即平均经过六个 人便可以建立人际关系。研究人员后续发 现，其他网络也具有这种 “小世界”的特 性。例如，万维网要经过19个连结，就可 以从一个网页到达另一个网页。
如何整合资源？
Байду номын сангаас
最近，中国工程院组织“信息基础设施和 资源共享”的发展战略研究。 李国杰院士指出：“信息取精是关键”。 李德毅院士说，当前的迫切目标是让“适 当的人在适当的时候享用适当的信息”。 无尺度现象告诉我们，要求所有的人享用 所有信息，既不可能，也没有必要。
李幼平院士提议，互联网在保留 TCP/IP的主结构的基础 上，增添一种“卫星广播和分布存储”的“播存结构”作 为次级结构。通过次级结构广泛复制数千种网站的内容， 让每一栋大楼与每一个自然村都拥有主流文化资源，营造 “存文化于民间”的全国环境，实现信息共享的历史性跨 跃。 用“透明计算”模式整合互联网的主、次两级结构，用户 只需提出内容需求，网页将自动以最低成本的方式来到用 户身边，用户无需感知网页是来自何种网络。创造一种类 似于水电服务那样简便的信息共享服务。
海内存知已，天涯若比邻
小世界网络效应
小世界网络效应
从局部看具有高度的集团化特征 从整体看任意两点间的平均路径长度较短 当网络大小变化时，任意两点间最短平均 距离变化相对缓慢
小世界模型
Watts 和Strogatz 在《Nature》杂志上发表文 章，引入了小世界（small-world）网络模型 (WS)，以描述从完全规则网络到完全随机网络 的转变，刻画庞大的网络中大多数节点间有较 短的连结（路径）的性质. WS模型始于一具有N个节点的一维网络，网络 的节点与其最近的邻接点和次邻接点相连接， 然后每条边以概率p重新连接。约束条件为节 点间无重边，无自环。
人们会根据自己的兴趣，来决定将网络文件连结到哪些 网站，而个人兴趣是多种多样的，可选择的网页数量也 极其庞大，因而最终的连结模式将呈现出相当随机的结 果。 令人惊异的事实:基本上，万维网是由少数高连结性的页 面串连起来的，80%以上页面的连结数不到4个。然而只 占节点总数不到万分之一的极少数节点，却有1000个以 上的连结(网络调查显示，有一份文件已经被超过200万 的其他网页所连结!)。
美国电网雪崩式级联故障 网络拥塞故障
电网拓扑结构统计特征参数
小世界应用_防范网络计算机病毒传播
保护关键结点
关键结点安装防火墙 严密的访问控制规则 实时监控 对在一定集团化系数范围内的集团进行隔离
对局部集团化网络进行隔离
监视“断键重连”和捷径
少量的“断键重连”和捷径往往是病毒向外传播的捷 径。因此，对这些随机产生的捷径进行监视，并及时 切断病毒传播的捷径，将大大增加病毒传播的网络平 均距离，从而能降低病毒蔓延的速度。
如果紧密连结的小型节 点集群彼此相连，形成 较大且较不紧密的大集 团，那这样的网络就能 既是高度集群的又是无 尺度的 。这类结构在很 多系统中都有出现· 比如 万维网，它的集群就是 具有相同主题的网页群。
中国互联网是什么结构？
中国互联网信息资源连接数，服从什么样 的幂次分布？ 中国互联网共有66万个网站，被访问量差 异极大，社会地位（Google称为rank）差 异极大。 中国互联网中心CNNIC发表的实测数据表明： 中国互联网是无尺度网络。
网站链接情况（2003年中国互联网络信息资源数量调查报告 ）
没有连接：占41% 连接1-5家：占29.9% 连接5-10家：占15.0% 连接11-20家：占7.4% 连接21-50家：占3.6% 连接51家以上：占2.7% 绝大多数网站，连接数很少（97%网站少于50 家），只有极少数网站才拥有极大的连接数
什么样的拓扑结构比较适合用来描 述真实的系统呢？
规则网络 随机网络 复杂网络
规则网络
规则网络是指平 移对称性晶格， 任何一个格点的 近邻数目都相同。 规则网络具有大 的簇系数和大的 平均距离。
随机网络
1959年，为了描述通信和生命科学中的网络， 匈牙利数学家Erdos和Renyi提出，通过在网络 节点间随机地布置连结，就可以有效地模拟出 这类系统。在这种方法下，两个节点之间连边 与否不再是确定的事情，而是根据一个概率决 定，研究人员把这样生成的网络叫做随机网络。 在过去40多年里，科学家惯于将所有复杂系统 的内部关系通过随机网络描述。 随机网络具有小的簇系数和小的平均距离。
Cregular C Crandom Lregular L Lrandom
小世界模型的分类
W-S模型
W-S转化模型
S-W模型
小世界应用_Internet的小世界特性
网络平均距离L随网络大小N对数增长.
结点和信息量以指数速度增长，但并没有感觉 到网络速度变慢、检索信息的难度加大。 明确的网站主题信息 相关网站的超级链接
BA模型(Barabá si－Albert)
模型的算法如下：
（1）增长：开始于较少的节点数量（m0），在每个时间 间隔增添一个具有m（≤m0）条边的新节点，连接这个 新节点到m个不同的已经存在于系统中的节点上。 （ 2 ）择优连接：新节点连接到节点 i 的概率 π 取决于节 点i的度数.
经过t时间间隔后，该算法程序产生一具 有N=t+m0个节点，mt条边的网络。 数量模拟表明具有k条边的节点的概率服 从指数为r=3的幂指数分布。
两百多年来，研究人员习惯借助图论理论， 通过网络的拓扑几何性质讨论系统的关系 特征。 网络拓扑典型几何性质包括度分布，平均 集聚程度与平均最短距离 .
网络的几何性质
节点的度分布是指网络（图）中度为K
的节点的概率P(K) 随节点度K 的变化 k 规律。
网络的几何性质