复杂网络的结构分析与演化模型
周亚东
西安交通大学系统工程研究所
提纲
⏹复杂网络的研究意义
⏹复杂网络的数学描述与度量指标
⏹“小世界”网络的特性及其演化模型⏹无尺度网络的特性及其演化模型
⏹总结
提纲
⏹复杂网络的研究意义
⏹复杂网络的数学描述与度量指标
⏹“小世界”网络的特性及其演化模型⏹无尺度网络的特性及其演化模型
⏹总结
复杂系统
复杂系统在我们周围随处可见：
⏹社会系统
⏹自然系统：蚁群、蜜蜂
⏹技术系统：Internet
Internet
星系结晶体相互作用与复杂性
扩散平均场?
复杂网络
⏹复杂网络是复杂系统的结构表示
⏹每一个复杂系统都是一个海量元素相互作用
组成的网络
⏹理解一个复杂系统=将其分解为部分+再组合⏹由于结构影响功能（反之亦然），网络化的分析对于研究复杂系统非常重要
为什么研究复杂网络？
•理解复杂系统的行为应该从理解系统相互
作用网络的拓扑结构开始；
•网络拓扑结构的信息是构建系统模型、研
究系统性质和功能的基础；
•复杂网络是研究复杂系统的一种角度和方法，它关注系统中个体相互关联的作用的拓扑结构，是理解复杂系统性质和功能的基础。
复杂网络研究所关心的问题
⏹如何建立复杂网络？
⏹如何定量分析复杂网络？
⏹网络结构的描述及其性质
⏹网络是如何发展成现在这种结构的？
⏹网络演化模型
⏹网络特定结构的后果是什么？
⏹网络结构的鲁棒性
⏹网络上的动力学行为和过程
不同领域的复杂网络
⏹社会网：演员合作网，朋友网，姻亲关系网，
科研合作网，Email网，短信网…
⏹生物网：食物链网，神经网，新陈代谢网，蛋
白质网，基因网络…
⏹信息网络：WWW，专利使用，论文引用，…
⏹技术网络：电力网，Internet，电话线路网，⏹交通运输网：航线网，铁路网，公路网，自然
河流网
⏹经济网络：投入产出网，国际贸易，…
技术网络
WWW电力网
Internet
社会、信息网络
朋友关系网
科学引文网
交通运输网络
航空网道路交通网
城市公共交通网
生态、生物网络
神经网络
蛋白质相互作用网络
生态网络
复杂网络研究的历史
⏹1736，欧拉：哥尼斯堡七桥
⏹1950，Erdos, Renyi: 随机图论
⏹1998，Strogatz；1999，Barabasi: 小世界和无尺度网络
复杂网络研究的兴起
⏹计算机技术的发展：
⏹使我们拥有各种网络的数据库，并有可能对大规模的网络进
行实证研究
⏹普适性的发现：
⏹许多实际网络具有相同的定性性质
⏹且已有的理论不能描述和解释
⏹理论研究的发展：
⏹小世界网络(Small World Network),无尺度网络(Scale-free
Network)
⏹统计物理学的研究手段
提纲
⏹复杂网络的研究意义
⏹复杂网络的数学描述与度量指标
⏹“小世界”网络的特性及其演化模型⏹无尺度网络的特性及其演化模型
⏹总结
复杂网络的数学描述
⏹网络G=（V, E），由点集V和边集E组成的一个图，
可分为无向、有向和加权网络
⏹令e i∈E，每条边e i有V中的一对点(u,v)与之对应；
如果任意(u,v)与(v,u)对应同一条边，则称为无向网络，否则为有向网络；
如果任意∣e
i ∣=1，则称为无权网络，否则为加
权网络。
⏹可用邻接矩阵表示一个复杂网络的结构
对网络结构的描述
⏹几种常用的度量指标
度（Degree）：该点的边的数量（无向图）
聚集系数（群系数）（Clustering coefficient）：
与该点连接的点之间相连的情况
最短路径（Shortest path）：
两个点之间经过边数最少的路径
⏹节点度分布函数f(k)：
⏹网络中度值为k的点占总点数的比例
一个简单的例子
K ●=5
C ●
=0K ●=5
C ●=1
复杂网络结构的两种重要特性
⏹“小世界”效应
⏹网络中大部份的节点彼此并不相连，但绝大部分节
点之间经过少数几步就可到达。
⏹“六度分隔”理论
⏹用网络的平均路径长度度量
⏹无尺度特性
⏹网络中的大部分节点只和很少节点连接，而有极少
的节点与非常多的节点连接
⏹以网络中的节点度分布度量——符合降幂率分布
γ-
(
P)
k
∝k
World Wide Web
超链接网络
8亿篇网络页面(S. Lawrence, 1999)
节点：WWW 页面连接边：URL 超链接入度与出度分布指数分别为2.1与2.7
平均路径长度为16
Internet 骨干网络
(Faloutsos,et.al 1999)
节点：核心路由器，11,174个连接边：路由器间的物理连接
度分布指数为2.48平均路径长度为3.62
节点：演员，
212,250个连接边：合作演戏
演员合作网络
度分布指数为2.48平均路径长度为3.65
提纲
⏹复杂网络的研究意义
⏹复杂网络的数学描述与度量指标
⏹“小世界”网络的特性及其演化模型⏹无尺度网络的特性及其演化模型
⏹总结
小世界实验
⏹Milgram小世界实验
⏹上世纪60年代哈佛大学社会心理学家Stanley Milgram
社会调查后推断出: 世界上任意两个人平均距离是6.
⏹Milgram实验: 信件传递.
⏹Kevin Bacon游戏
⏹Kevin Bacon为美国著名演员
⏹任意一个演员与Bacon一起演过电影则其Bacon数为1.
⏹平均Bacon数为2.944.
⏹周星驰的Bacon数是3.
几种典型的网络结构
规则网络
(a)完全连接; (b)最近邻居连接; (c)星形连接
ER 随机图模型
特点:
⏹齐次性:
每个节点大约有相同的
连接数
⏹节点数不增加
⏹具有较小的聚集系数
小世界网络模型
特点:
(与ER 随机图相似)
⏹齐次性:
每个节点有大约相同
的连接数
⏹节点数不增加
⏹具有与实际网络相近
的聚集系数
小世界网络
C(p) : 平均聚集系数
L(p) : 平均最短路径
提纲
⏹复杂网络的研究意义
⏹复杂网络的数学描述与度量指标
⏹“小世界”网络的特性及其演化模型⏹无尺度网络的特性及其演化模型
⏹总结
无尺度网络的度分布
幂律分布——Power Law
γ
-∝k
k P )(k
k P ln )(ln γ-∝
γ=-3
BA偏好连接模型
——PREFERENTIAL ATTACHMENT
(1) 节点数量不固定
网络由不断加入的新节点演变
(2) 连接边建立不均匀选取节点.
节点以较大的概率与具有较大连接度的节点建立新的连
接
例如：
WWW : 新的网页链接向知名站点
引用：被广泛引用的论文更易被再次引用
例如：
WWW : 新网页的创建
引用：新的论文发表
A.-L.Barabási, R. Albert, Science 286,509 (1999)
BA
A.-L.Barabási, R. Albert, Science 286,509 (1999)
无尺度网络
特点:
⏹非齐次性:
很少的节点有很多连
接，很多节点只有很
少的连接
⏹节点数增加
⏹与ER模型、WS模型
相比，具有较小的聚
集系数和较大的平均
路径长度
提纲
⏹复杂网络的研究意义
⏹复杂网络的数学描述与度量指标
⏹“小世界”网络的特性及其演化模型⏹无尺度网络的特性及其演化模型
⏹总结
本节课总结
⏹分析了复杂网络的研究意义
⏹介绍了复杂网络的结构特性
⏹分析了复杂网络的“小世界”效应，并介绍了相应的网络模型
⏹分析了复杂网络的无尺度特性，并介绍了相应的网络模型
谢谢！
对网络结构的描述
!
!)()(k k e k pN e
k P k
k k pN
><=≈><--
随机网络的度分布——Poisson 分布
10000个顶点
p =0.0015
论文引用网络
Metabolic network
Archaea Bacteria Eukaryotes
Organisms from all three domains of life are scale-free networks!
H. Jeong, B. Tombor, R. Albert, Z.N. Oltvai, and A.L. Barabasi, Nature, 407651 (2000)。