Download presentation
Presentation is loading. Please wait.
1
狄增如 北京师范大学管理学院系统科学系 北京师范大学复杂性研究中心 北京大学---2007.11
复杂网络研究 ——现状与前瞻 狄增如 北京师范大学管理学院系统科学系 北京师范大学复杂性研究中心 北京大学
2
关于复杂性
3
关于复杂性 我们所关心的问题： 大量个体（更典型的是具有适应性的主体）所组成的复杂系统，在没有中心控制、非完全信息、仅仅存在局域相互作用的条件下，通过个体之间的非线性相互作用，可以在宏观层次上涌现出一定的结构和功能。
4
相互作用与复杂性 ? Internet 晶格 全局相互作用 扩散 平均场
1) In another cases, like the simulation of a cluster of stars shown here, all elements of the system do interact to all the rest, what also allows large mathematical simplification. 2) these two types of connections are the common ones found in the classical reductionist approximation of science because they allow great simplifications to be done and thus easier analitical mathematics is possible. 3) But, many real systems show a very different pattern of connectivity which does not allow us to do such an easy reductionist simplification. For example (show computer) the internet ... (explain the figure) ... and if we now want to represent the structure of its connectivity, we find a very complex structure as the following one (show structure). 扩散 平均场 ?
5
为什么研究复杂网络？ • 复杂系统不能够用分析的方法去研究， 必须考虑个体之间的关联和作用；
• 复杂系统不能够用分析的方法去研究， 必须考虑个体之间的关联和作用； • 理解复杂系统的行为应该从理解系统相互作用网络的拓扑结构开始； • 网络拓扑结构的信息是构建系统模型、研究系统性质和功能的基础。
6
为什么研究复杂网络？ 复杂网络是研究复杂系统的一种角度和方法，它关注系统中个体相互关联的作用的拓扑结构，是理解复杂系统性质和功能的基础。
复杂网络是构成复杂系统的基本框架（ backbone ），每一个复杂系统都可以看作是单元或个体之间的相互作用网络； 复杂网络在刻画复杂性方面的重要性是由于结构和功能之间是相互影响的。 复杂网络是研究复杂系统的一种角度和方法，它关注系统中个体相互关联的作用的拓扑结构，是理解复杂系统性质和功能的基础。
7
技术网络 WWW 因特网 电力网 1) internet is not the only case, of course, complex networks can be found almost in all areas of nature. 2) Compare the structure of the WWW network with a cristal lattice for example.
8
社会网络 朋友关系网 科学引文网 演员网 性关系网 科学家合著网
9
交通运输网络 航空网 城市公共交通网 道路交通网
10
生物网络 生态网络 蛋白质相互作用网络 神经网络 基因网络 新陈代谢网络
1) It is evident that network structure brings a whole new dimension... so how to study properties of network structure?! 基因网络 新陈代谢网络
11
生命金字塔
12
不同领域的复杂网络 社会网：演员合作网，友谊网，姻亲关系网，科研合作网，Email网
生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络 信息网络：WWW，专利使用，论文引用，计算机共享 技术网络：电力网，Internet，电话线路网， 交通运输网：航线网，铁路网，公路网，自然河流网
13
复杂网络 A food web Connection Topology A Unified Approach towards the
of various Complex Systems 1) the methodology and measures we are going to present are universal, they can be applied to any system representable by a graph. Anyway, for clarification we will use an example: a food web.
14
网络研究的历史 1736，欧拉：哥尼斯堡七桥 1950，Erdos, Renyi: 随机图论
1998，Strogatz, Barabasi: 小世界和无标度网络
15
为什么现在才开始研究复杂网络？ 计算机技术的发展： 普适性的发现： 理论研究的发展
使我们拥有各种网络的数据库，并有可能对大规模的网络进行实证研究 普适性的发现： 许多实际网络具有相同的定性性质 且已有的理论不能描述和解释 理论研究的发展 小世界网络 (Small World Network), 无标度网络 (Scale-free Network) 统计物理学的研究手段
16
复杂网络研究所关心的问题 如何定量刻画复杂网络？ 网络是如何发展成现在这种结构的？ 网络特定结构的后果是什么？ 网络结构的描述及其性质
网络演化模型 网络特定结构的后果是什么？ 网络结构的鲁棒性 网络上的动力学行为和过程
17
复杂网络的结构 四种结构模型： 规则网络 随机网络 小世界网络 无标度网络
18
对网络结构的描述 几何量及其分布 度（Degree）：朋友的个数 集聚系数（群系数）（Clustering coefficient）：
朋友的朋友还是不是朋友的情况 最短路径（Shortest path）： 两个顶点之间边数最少的路径 介数（Betweenness）： 经过我的最短路径的条数
19
一个简单的例子 K●=5 C●=0 K●=5 C●=1
20
规则网络 一般情况下， 聚集系数较大， 平均最短路径较长。
21
ER随机网络 当p不太小时， 聚集系数较小， 平均最短路径较短。
22
随机网络的平均最短路径 及其与实证数据的比较
随机网络的平均最短路径 及其与实证数据的比较
23
随机网络的平均聚集系数 及其与实证数据的比较
随机网络的平均聚集系数 及其与实证数据的比较
24
Small World Network C(p) : 平均聚集系数 L(p) : 平均最短路径
25
度分布 分布函数f(k)： 网络中度值为k的顶点占总点数的比例 随机网络的度分布——Poisson分布 10000个顶点 p=0.0015
26
度分布 幂律分布——Power Law g=-3
27
World Wide Web P(k=500) ~ 10-6 Nodes: WWW documents Links: URL links
800 million documents (S. Lawrence, 1999) P(k=500) ~ 10-6 NWWW ~ 109 N(k=500) ~ 103
28
(Faloutsos, Faloutsos and Faloutsos, 1999)
INTERNET BACKBONE Nodes: computers, routers Links: physical lines (Faloutsos, Faloutsos and Faloutsos, 1999)
29
ACTOR CONNECTIVITIES =2.3 P(k) ~k- Nodes: actors Links: cast jointly
N = 212,250 actors k = 28.78 P(k) ~k- =2.3
30
SCIENCE COAUTHORSHIP SCIENCE CITATION INDEX
Nodes: papers Links: citations Nodes: scientist (authors) Links: write paper together 1736 PRL papers (1988) (Newman, 2000, H. Jeong et al 2001)
31
Sex-web Nodes: people (Females; Males) Links: sexual relationships
4781 Swedes; 18-74; 59% response rate. Liljeros et al. Nature 2001
32
Organisms from all three domains of life are scale-free networks!
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, (2000)
34
Scale Free网络的基本特征 Power Law Degree Distribution（幂律度分布） 1、自相似结构：
2、两极分化，高度弥散
35
复杂网络中顶点度的匹配关系Assortative Mixing by Degree
如果网络中度值高的顶点倾向于与其他高度值的顶点相互连接，则称网络具有同向匹配性质； 例如：社会网络 如果网络中度值高的顶点倾向于与度值低的顶点相互连接，则称网络具有反向匹配性质； 例如：大部分生物、技术网络 同向匹配 无标度网络 反向匹配 无标度网络
36
复杂网络中的社团结构 Community Structures 社团内部连接紧密，社团之间连接相对稀疏
Physics collaboration network Palla et al. Nature 435, 9 (2005)
37
Santa Fe研究所的科学家合作网
38
Rhesus猴子网 经济物理学科学家合作网
39
网络模体---Network Motifs
模体——在网络中密度明显较高的子图（基本结构单元）
41
复杂网络演化模型 BA模型 网络增长、偏好连接 基于蛋白质相互作用的演化模型 复制、分化、变异 优化演化模型
42
Most real world networks have the same internal structure:
Scale-free networks 其形成机制是什么？ 结构与功能？
43
BA偏好连接模型 ——PREFERENTIAL ATTACHMENT
(1) The number of nodes (N) is NOT fixed. Networks continuously expand by the addition of new nodes Examples: WWW : addition of new documents Citation : publication of new papers (2) The attachment is NOT uniform. A node is linked with higher probability to a node that already has a large number of links. Examples : WWW : new documents link to well known sites (CNN, YAHOO, NewYork Times, etc) Citation : well cited papers are more likely to be cited again
44
Scale-free model P(k) ~k-3
(1) GROWTH : At every timestep we add a new node with m edges (connected to the nodes already present in the system). (2) PREFERENTIAL ATTACHMENT : The probability Π that a new node will be connected to node i depends on the connectivity ki of that node P(k) ~k-3 A.-L.Barabási, R. Albert, Science 286, 509 (1999)
45
网络的结构与功能 网络上的动力学行为和过程 动力系统：自旋、振子或混沌的同步、可激发系统
传播过程：信息传播与拥堵、网络搜寻、运输过程、疾病传播、谣言的传播、舆论形成 博弈与其他社会行为：囚徒困境、少数者博弈 其他过程：电力网的级联失效等
46
复杂网络上的渗流和网络鲁棒性 无标度网络对于顶点的随机移除非常稳健! 给定度分布P(k)的复杂网络上的点缺陷：
顶点以概率q被随机的占据（工作状态良好） 或以概率1-q被空置 (被破坏) 然后考察系统存在无限大连通集团的临界概率qc 对无标度网络 当 λ<=3, 临界概率 qc 是0或负值. 无标度网络对于顶点的随机移除非常稳健!
47
Percolation and Network Resilience
Callyway et al: 占据某个顶点的概率可以是该顶点度值 k 的任意函数: qk. 取 qk=θ(k-kmax), Heaviside step function 只需移除掉很少比例的顶点就可以完全摧毁网络中的最大连通集团！ 无标度网络对有目的的最大度攻击非常脆弱！
48
Error and Attack Tolerance
50
网络上的动力系统
51
网络同步
52
全局耦合下萤火虫的同步
53
小世界网络上混沌映象的同步 SW: 影响同步的结构因素： 平均最短距离、度分布 最大度值、最大点介数 值 随着短边重连概率的
增加，同步得到加强
54
可激发系统
56
复杂网络上的疾病传播
57
网络上的动力学—疾病传播 Epidemic Dynamics in Complex Networks
High-risk actors over 4 years 695 people represented Longest path is 17 steps Average distance is about 5 steps Average person is within 3 steps of 75 other people 137 people connected through 2 independent paths, core of 30 people connected through 4 independent paths Reachability in Colorado Springs (Sexual contact only) Epidemic Dynamics in Complex Networks (Node size = log of degree)
58
Drug sharing network
59
传染病动力学：SI 模型 接触数目 I S 固定人口总数的疾病传播模型: 易受感染者 传染者 I(t) t : 易受感染者人数
: 总人数 : 传染比例 :传染者人数 固定人口总数的疾病传播模型: I(t) t
60
Epidemic Dynamics：SI Model
61
传染病动力学：SIS 模型 有效扩散速率：
62
传染病动力学：SIR模型 疾病扩散条件： OR
63
网络上的疾病传播 完全混合 网络拓扑结构的影响 规则网格 复杂网络
64
SIS model on Networks
65
网络上的疾病传播 小世界网上的SIS 模型 有效扩散速率 And Let g=1 利用平均场理论计算被感染顶点密度随时间的变化： 稳态解:
传播阈值:
66
小世界网上的SIS 模型 计算机数值模拟 N=103_---- N=3* 106, <k>=6, 10 个不同的网络, 100 个不同的初始分布
67
BA无标度网络上的SIS 模型 利用平均场理论计算被感染顶点密度随时间的变化： SW BA 稳态解: BA无标度网度分布
68
BA无标度网络上的SIS 模型 Evolution
69
SIR Model on Complex Networks
Disease spreading Percolation
70
复杂网络上的SIR模型 Disease spreading Percolation! 无标度网络上的SIR模型
71
复杂网络上的疾病传播
72
网络结构上的少数者博弈模型 少数者博弈 数值模拟结果 网络结构的影响？
73
关于复杂网络研究现状 复杂网络研究是否已经形成并仍处于热潮之中？ 在复杂网络研究中有什么应该注意的问题？ 我们还应该继续做些什么？
74
复杂网络研究的综述与著作 S.H.Strogatz, Nature, 410,(2001)268
R.Albert, A.-L.Barabasi, Rev.Mod.Phys. 51 (2002)1079 M.E.J.Newman, SIAM Rev. 45(2003) 167 S.N.Dorogovtesev, J.Mendes, Evolving of Networks, Oxford Un. Press, 2003 E.Ben-Naim, et al, Complex Networks, Springer, 2004 S.Boccaletti, et al, Complex Networks: Structure and dynamics, Phys. Rep. 424 (2006) Newman, Barabasi, Watts, The Structure and Dynamics of Networks, Princeton University Press, 2006
75
部分由物理学推动的科研热潮 混沌和分形 Chaos and Fractals 自旋玻璃 Spin Glasses
自组织临界性 Self-organized criticality 统计物理学在生物进化中的应用 经济物理学 Econophysics 复杂网络 Complex networks?
76
毫无疑问，这些工作对科学的发展做出 了贡献，但有些研究的意义被夸大了。 例如 Per Bak’s 关于自组织临界性的著作冠名为：How Nature Works 中译本：《大自然是如何工作的》
77
波及面也各有不同 尽管自组织临界性被认为有广泛的应用价值，但研究工作事实上仅仅局限在物理学领域中。
对于经济物理学，我们很少能够在经济学杂志上见到相关工作，经济物理学的文章只发表在物理学以及专门的经济物理学杂志上。
78
而复杂网络研究已经波及到众多科学领域，确实可以称之为形成了研究热潮
但还没有做到与其他学科领域的有机结合
79
发挥复杂网络研究的意义和价值应该注意以下几点：
具备你所研究的系统的相关知识； 存在一个确实需要网络基础的科学问题，而复杂网络有助于你解决它。 清楚了解系统相互作用的拓扑结构仅仅是万里长征走完了第一步，它不可能魔术般地解决系统的根本问题。
80
同时应该注意复杂网络研究中所可能出现的问题
在实证研究中，样本太少或取样的偏差 会导致对网络结构的错误认识。 把系统的某些特性仅仅归结为网络结 构的作用往往是片面的。
81
例如，对Intenet的容错性和鲁棒性的研究
82
identical power-law degrees
10 1 2 3 高度值的中枢节点核心 低度值的网状核心 identical power-law degrees 度分布相同的网络的细致结构未必相同
83
我们接下来该做什么？ 发现和刻画实际系统的网络结构 模拟网络的演化 探讨结构与功能之间的相互关系 利用网络结构控制和优化系统功能
84
我们接下来该做什么？ 是否有更多的统计分布帮助我们深入理解复杂网络的结构和分类？ 对于不同的网络结构是否存在规范的分类方法？
为什么许多网络是组合式的？ 影响生物网络的演化机制是什么？ 如何量化不同性质网络间的相互作用（网络的网络）？
85
我们接下来该做什么？ 为什么社会网络都是相配的，而所有的生物和科技网都是不相配的？ 网络动力学是否有普遍性质？
在网络中发生的动力学过程怎样影响网络的拓扑结构？ 如何研究与网络功能相关的网络容错性与鲁棒性？
86
谢谢大家！
Similar presentations
