∑d
i> j
ij
d12 = 1
d13 = 1 d 23 = 1
d14 = 2 d 24 = 1 d 34 = 2
d15 = 1 d 25 = 2 d 35 = 2 d 45 = 3
Total = 16 Average:
L = 16 / 10 = 1.6
聚类系数
• 一个网络的聚类系数 C满足:
0<C<1
规则网络
(a) 完全连接;
(b) 最近邻居连接;
(c) 星形连接
规则网络
... ...
(d) Lattice
(z) Layers
随机图理论
• 随机图论 - Erdös and Rényi (1960) • ER 随机图模型统治四十余年…… 直到今天 …… • 当今大量可获取的数据＋高级计算工具，促使人们 重新考虑随机图模型及其方法
“图论之父”
看作4个节点，7条边的 图
路必须有起点和终点。 一次走完所有的桥，不重复，除起点与终点外，其余点必须有偶数 条边，所以七桥问题无解。 1875年, B 与 C 之间新建了一条桥解决了该问题！☺
Euler 对复杂网络的贡献
Euler 开启了数学图论，抽象为顶点与边的集 合 图论是网络研究的基础 网络结构是理解复杂世界的关键
电信网络
(Stephen G. Eick)
美国航空网
世界性的新闻组网络
(Naveen Jamal)
生物网络
人际关系网络
复杂网络概念
• • • • • • 结构复杂：节点数目巨大，网络结构呈现多种不同特征。 节点多样性：同一网络中可能有多种不同的节点。 连接多样性：节点之间的连接权重存在差异，且有可能存在方向性。 网络进化：表现在节点或连接的产生与消失。例如WWW，网页或链 接随时可能出现或断开，导致网络结构不断发生变化。 动力学复杂性：节点集可能属于非线性动力学系统，例如节点状态随 时间发生复杂变化。 多重复杂性融合：即以上多重复杂性相互影响，导致更为难以预料的 结果。例如，设计一个电力供应网络需要考虑此网络的进化过程，其 进化过程决定网络的拓扑结构。当两个节点之间频繁进行能量传输时， 他们之间的连接权重会随之增加，通过不断的学习与记忆逐步改善网 络性能。 复杂网络简而言之即呈现高度复杂性的网络。
Node-1 has 1 complete triangle and 3 triangular graphs, so C(1) = 1/3 Node-2 has 1 complete triangle and 3 triangular graphs, so C(2) = 1/3 Node-3 has 1 complete triangle and 1 triangular graph, so C(3) = 1 Node-4 has 0 complete triangles, so C(4) = 0 Node-5 has 0 complete triangles, so C(5) = 0
Konigsberg 七桥问题
Can one walk across the seven bridges and never across the same one twice? --- No! (Proved by Euler in 1736)
Leonhard Euler (1707-1783)
小世界网络是描述 Internet 的较好模型
3. 科研合作网
• Pál Erdös (1913-1996)
• Oliver Sacks: "A mathematical genius of the first order, Paul Erdös was totally obsessed with his subject - he thought and wrote mathematics for nineteen hours a day until the day he died. He traveled constantly, living out of a plastic bag, and had no interest in food, sex, companionship, art - all that is usually indispensable to a human life." (Paul Hoffman, 1998)
2. Internet
• 平均距离
– L = 4.0 – ER 随机图模型: L = 10 (太大) – Internet 是小世界网络
• 度分布
– 幂指数分布: P(k) ~ k^{-γ}, γ = 2.2 – Internet 是一个 scale-free 网络
• 聚类系数
– C = 0.3 – ER 随机图模型: C = 0.001 (太小)
N=20
K=4
p=0.075
BA无标度网络模型 Barabasi-Albert(B-A)模型
无尺度网络形成的两个基本机制： (1)增长。 ki (2)优先连接。 Π ( k i ) = ∑ k
j j
B-A 模型的构建
ki Π (ki ) = ∑ k
j
j
(1) 增长：在初始时刻，假定系统中已有m0个点，在 以后的每一个时间步长中，我们新增一个度为m的点 (m<=m0)，这m条边连向网络中已经存在的m个不同的点。 (2)优先连接：当我们在原来网络中选择一些点被新 增加的边连结时，这些点被连结的概率与这些点自身的 度的大小成正比。比如度为Ki的点i 被新增点连结的概 4 4 率为： 2 2 2 2
p , a new node is added into the network
(ii) 增加新连接 (偏好性): The new node has m ( m ≤ m0 ) new links to the already
existing nodes in the network with probability
小世界网络
特征:
(Similar to ER Random Graphs)
» 齐次性: 每个节点有大约相同 的连接数 » 节点不增加
Scale-Free 网络
(isi-Albert, Science, 1999)
由初始给定的一个具 m0个节点的网络开始
最短路径
• 节点 n 与 m的 距离 d(n,m) = 连接他们的最短路径的长度 • 直径 D = max{d(n,m)} • 平均距离 L = 所有 d(n,m)的平均数 • 大部分复杂网络有小的平均距离 L 小世界特征
例子:
一个具5个节点5个连接的网络:
.
L=
1 1 N ( N − 1) 2
• Kevin Bacon游戏
– – – – Kevin Bacon美国著名演员 任意一个演员与Bacon一起演过电影则其Bacon数为1. 平均Bacon数为2.944. 周星驰的Bacon数是3.
• Erdös数
Granovetter弱连接的强度
• 人们在寻找工作时，关系紧密的朋友(强连 接)反倒没有那些关系一般甚至只是偶尔见 面的朋友(弱连接)更能发挥作用 • 《Strength of Weak Ties》发表在《美国社 会学》，有史以来最有影响的社会学论文 之一
•
复杂网络研究简史
• • • • • • 1736 Euler 七桥问题 1959 Erdos, Renyi 随机图理论 1967 Milgram 小世界实验 1973 Granovetter 弱连接的强度 1998 Watts, Strogatz 小世界模型 1999 Barabasi, Albert 无标度网络
复杂网络研究简介
童超 tongchao@ 北航计算机学院
内容
• • • • • 复杂网络概念 复杂网络研究简史 复杂网络结构统计特性 网络拓扑模型构建 复杂网络应用
Internet
(K. C. Claffy)
万维网World Wide Web（WWW）
(William R. Cheswick)
ki + 1 ∏ ( ki ) = ∑ (k j + 1)
j
Scale-Free 网络
特征:
» 连通性: 幂指数分布 » 非齐次性: 很少的节点有很多连 接，很多节点只有很 少的连接 » 节点数增加
(Hawoong Jeong)
复杂网络结构统计特性
• 最短路径长度 • 聚类系数 • 度与度分布
(Stephen G. Eick)
近年来的重大发现
• 小世界效应 (Watts and Strogatz,
Nature, 1998)《Collective Dynamics of ‘Small-World’ Networks》
Scale-Free 特征 (Barabási and Albert,
Science, 1999)《Emergence of Scaling in Random Networks》
– Our Erdös Number is ？: • Erdös had a (scale-free) small-world network of mathematical research collaboration
网络拓扑模型构建
• • • • WS小世界模型 BA无标度网络模型 适应度模型 局域世界演化模型构造
• 完全随机网络: P(k) ~ Poisson 分布
无标度网络度分布
• 大部分网络: P(k) ~ k^{-γ} (幂指数率) – scale-free 特征
P(k) ~k-3
几个简单例子
•
World Wide Web Internet Scientific Collaboration Network