复杂网络研究现状_狄增如
4781 Swedes; 18-74; 59% response rate. Liljeros et al. Nature 2001
Metabolic network
Archaea
Bacteria
Eukaryotes
Organisms from all three domains of life are scale-free networks!
相互作用与复杂性
晶格 全局相互作用 Internet
扩散
平均场
?
为什么研究复杂网络?
• 复杂系统不能够用分析的方法去研究, 必须考虑个体之间的关联和作用; • 理解复杂系统的行为应该从理解系统相互 作用网络的拓扑结构开始; • 网络拓扑结构的信息是构建系统模型、研 究系统性质和功能的基础。
为什么研究复杂网络?
复杂网络是构成复杂系统的基本框架( backbone ), 每一个复杂系统都可以看作是单元或个体之间的相互作 用网络; 复杂网络在刻画复杂性方面的重要性是由于结构和功能 之间是相互影响的。
复杂网络是研究复杂系统的一种角度和 方法,它关注系统中个体相互关联的作用的 拓扑结构,是理解复杂系统性质和功能的基 础。
P(k) ≈ e
− pN
10000个顶点
p=0.0015
度分布
幂律分布——Power 幂律分布——Power Law
−γ
P(k ) ∝ k
ln P (k ) ∝ −γ ln k
γ=-3
World Wide Web
Nodes: WWW documents Links: URL links 800 million documents (S. Lawrence, 1999)
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.
Scale-free networks
其形成机制是什么? 结构与功能?
BA偏好连接模型 BA偏好连接模型
——PREFERENTIAL ATTACHMENT (1) The number of nodes (N) is NOT fixed.
Networks continuously expand by the addition of new nodes Examples:
Palla et al. Nature 435, 9 (2005)
Santa Fe研究所的科学家合作网 Fe研究所的科学家合作网
Rhesus猴子网 Rhesus猴子网
Rhesus m onkey network(W EO)
经济物理学科学家合作网
A C
B
m ale fem ale D
066
065
AC DL 004
复杂网络
A food web
A Unified Approach towards the
Connection Topology
of various Complex Systems
网络研究的历史
1736,欧拉:哥尼斯堡七桥 1736,欧拉:哥尼斯堡七桥 1950, 1950,Erdos, Renyi: 随机图论 1998, 1998,Strogatz, Barabasi: 小世界和无 标度网络
Scale-free model
(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 :
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
无标度网络对于顶点的随机移除非常稳健!
Percolation and Network Resilience
Callyway et al:
占据某个顶点的概率可以是该 顶点度值 k 的任意函数: qk. 的任意函数:
取 qk=θ(k-kmax), Heaviside step function
只需移除掉很少比例的顶点就可以完全摧毁网络中的最 大连通集团!
<k > Crand = p = N
Small World Network
C(p) : 平均聚集系数 L(p) : 平均最短路径
度分布
分布函数f(k):
– 网络中度值为k的顶点占总点数的比例 网络中度值为k – 随机网络的度分布——Poisson分布 随机网络的度分布——Poisson分布
k ( pN)k −<k > < k > =e k! k!
技术网络
WWW 因特网 电力网
社会网络
朋友关系网 科学引文网
演员网 性关系网 科学家合著网
交通运输网络
航空网 城市公共交通网
道路交通网
生物网络
生态网络 蛋白质相互作用网络
神经网络 基因网络 新陈代谢网络
生命金字塔
不同领域的复杂网络
社会网:演员合作网,友谊网,姻亲关系网, 科研合作网,Email网 科研合作网,Email网 生物网:食物链网,神经网,新陈代谢网, 蛋白质网,基因网络 信息网络:WWW,专利使用,论文引用,计 信息网络:WWW,专利使用,论文引用,计 算机共享 技术网络:电力网,Internet,电话线路网, 技术网络:电力网,Internet,电话线路网, 交通运输网:航线网,铁路网,公路网,自 然河流网
复杂网络研究 ——现状与前瞻 ——现状与前瞻
狄增如 北京师范大学管理学院系统科学系 北京师范大学复杂性研究中心
北京大学---2007.11 北京大学---2007.11
关于复杂性
关于复杂性
我们所关心的问题:
– 大量个体(更典型的是具有适应性的主体) 所组成的复杂系统,在没有中心控制、非 完全信息、仅仅存在局域相互作用的条件 下,通过个体之间的非线性相互作用,可 以在宏观层次上涌现出一定的结构和功能。
P(k=500) ~ 10-6 10-
NWWW ~ 109 ⇒ N(k=500) ~ 103
INTERNET BACKBONE
Nodes: computers, routers Links: physical lines
(Faloutsos, Faloutsos and Faloutsos, 1999)
ACTOR CONNECTIVITIES
Nodes: actors Links: cast jointly
N = 212,250 actors 〈k〉 = 28.78 〉
γ P(k) ~k-γ
γ=2.3
SCIENCE CITATION INDEX
Nodes: papers Links: citations
一个简单的例子
K●=5 C●=0
K●=5 C●=1
规则网络
一般情况下, 聚集系数较大, 平均最短路径较长。
ER随机网络 ER随机网络
当p不太小时, 聚集系数较小, 平均最短路径较短。
随机网络的平均最短路径 及其与实证数据的比较
ln N lrand ≈ ln < k >
随机网络的平均聚集系数 及其与实证数据的比较
SCIENCE COAUTHORSHIP
Nodes: scientist (authors) Links: write paper together
பைடு நூலகம்
1736 PRL papers (1988)
(Newman, 2000, H. Jeong et al 2001)
Sex-web
Nodes: people (Females; Males) Links: sexual relationships
无标度网络对有目的的最大度攻击非常脆弱!
Error and Attack Tolerance
网络上的动力系统
– 例如:社会网络
如果网络中度值高的顶点倾向于与度值低的顶点相互连 接,则称网络具有反向匹配性质;
– 例如:大部分生物、技术网络
同向匹配 无标度网络
反向匹配 无标度网络
复杂网络中的社团结构 Community Structures
社团内部连接紧密,社团之间连接相对稀疏
Physics collaboration network
EC
EK
(b)
KE 022 R006
CY
076
ER EZ CN KD
网络模体--网络模体---Network Motifs
模体——在网络中密度明显较高的子
图(基本结构单元)
复杂网络演化模型
BA模型 BA模型
– 网络增长、偏好连接
基于蛋白质相互作用的演化模型
– 复制、分化、变异
优化演化模型
Most real world networks have the same internal structure:
网络的结构与功能
网络上的动力学行为和过程 动力系统:自旋、振子或混沌的同步、可激
发系统
传播过程:信息传播与拥堵、网络搜寻、运
输过程、疾病传播、谣言的传播、舆论形成