复杂网络数学建模概述 南京航空航天大学应用物理系 朱陈平.

Presentation on theme: "复杂网络数学建模概述 南京航空航天大学应用物理系 朱陈平."— Presentation transcript:

1 复杂网络数学建模概述 南京航空航天大学应用物理系 朱陈平

2 一、网络图的基本概念

3 节点、边 关联与邻接 度 k、平均度 <k> 节点的度分布p(k) 最短路径与平均路径长度 （Dijkstra算法） 集聚系数 C

4 a b c e d

5 有向图、无向图、不连通图

6 节点的度分布是指网络（图）中度为 的节点的概率 随节点度 的变化规律。

7 两点之间的最短路径： 　　　从指定始点到指定终点的所有路径中长度最小的一条路径。 网络平均路径长度： 　　　所有点对之间的最短路径的算术平均值。

8 7 2 2 5 5 5 1 3 7 3 1 5

9 节点1到7之间的最短路13，平均路径长度5.47， 平均度为3.4，集聚系数为0.48。

10 二、早期网络模型

11 规则图和随机图 规则图 　　　系统中节点及其与边的关系是固定的，每个节点都有相同的度数。 随机图 　　　平均说来系统中节点及其与边的关系不确定。

12 规则图的特征 平均度为3。

13 随机图的特征 节点确定，但边以概率 任意连接。 节点不确定，点边关系也不确定。

14 随机图——节点19，边43 平均度为2.42，集聚系数为0.13。

15 随机图——节点42，边118 平均度为5.62，集聚系数为0.133。

16 ER模型 Erdös和Rényi （ER）最早提出随机网络模型并进行了深入研究，他们是用概率统计方法研究随机图统计特性的创始人。
给定N个节点，没有边，以概率p用边连接任意一对节点，用这样的方法产生一随机网络。

17

18 ER模型 节点的度分布：平均值为 的泊松分布

19 Connect with probability p
p=1/6 N=10 k ~ 1.5 Poisson distribution

20 三、复杂网络模型 小世界（small-world) 网络模型 无标度 （scale-free)网络模型

21 小世界模型 为了描述从一个局部有序系统到一个随机网络的转移过程，Watts和 Strogatz（WS）提出了一个新模型，通常称为小世界网络模型。 WS模型始于一具有N个节点的一维网络，网络的节点与其最近的邻接点和次邻接点相连接，然后每条边以概率p重新连接。约束条件为节点间无重边，无自环。

22 C(p) : clustering coeff. L(p) : average path length
P(k)= p(k)=0.3

23 当p等于0时，对应于规则图。两个节点间的平均距离<L>线性地随N增长而增长，集聚系数大。
当p等于1时，系统变为随机图。 <L>对数地随N增长而增长，且集聚系数随N减少而减少。 在p等于（0，1）区间任意值时，<L>约等于随机图的值，网络具有高度集聚性---小世界效应。

24 复杂网络都具有分布于平均值两边的度分布曲线吗？

25 无标度(Scale-free)网络 Scale-free网络的发现 Scale-free网络的特性

26 Scale-free)网络的发现 信息交换网（万维网、国际互联网、电话网、电力网）
社会网络（电影演员合作网、科研合作图、引文网、人类性接触网、语言学网） 生物网络（细胞网络、生态网络、蛋白质折叠）

27

28

29 Scale-free网络的特性 度分布呈幂率分布 中枢节点出现 鲁棒性 脆弱性

30

31

32 无标度网络与随机图特性比较

33 无标度（Scale-free）网络 无标度模型由Albert-László Barabási和Réka Albert在1999年首先提出，现实网络的无标度特性源于众多网络所共有的两种生成机制： （ⅰ）网络通过增添新节点而连续扩张； （ⅱ）新节点择优连接到具有大量连接的节点上。

34 BA模型 增长和择优连接这两种要素激励了Barabási－Albert模型的提出，该模型首次导出度分布按幂函数规律变化的网络。 模型的算法如下： （1）增长：开始于较少的节点数量（m0），在每个时间间隔增添一个具有m（≤m0）条边的新节点，连接这个新节点到m个不同的已经存在于系统中的节点上。 （2）择优连接：在选择新节点的连接点时，假设新节点连接到节点i的概率π取决于节点i的度数即

35 经过t时间间隔后，该算法程序产生一具有N=t+m0个节点，mt条边的网络。
数量模拟表明具有k条边的节点的概率服从指数为r=3的幂指数分布。

36 P(k) ~k-3 A.-L.Barabási, R. Albert, Science 286, 509 (1999)

37 BA模型 （a)Barabási-Albert模拟的度分布。 （b）不同系统规模下的 。

38 BA模型 设节点 i 的度 满足动态方程： 分母求和是对系统中除新进入系统的节点外的所有节点进行的 ，则

39 BA模型 当t足够大时，有 解微分方程，有

40 由初始条件得 解为 式中 可给出度小于k的节点的概率

41 设在相同的时间间隔，添加节点到网络 中， 值具有常数概率密度
设在相同的时间间隔，添加节点到网络 中， 值具有常数概率密度 代入前式 t趋于无穷时度分布 式中

42 模型的度分布是与时间无关的渐进分布且与系统规模无关。
幂律度分布的系数与 成正比 。 无标度模型的动态特性可以用各种分析方法给出 ： 平均场理论 主方程法 变化率方程法

43 Baralási-Albert模型的限制条件
保持了网络的增长特性，不考虑择优连接，网络度分布呈指数衰减。 消除了增长过程，只考虑择优连接，络度分布围绕其均值为一高斯分布。 BA认为，这两个条件缺一不可，否则不能出现幂率度分布。

44 Baralási-Albert模型扩展研究
初始吸引度 非线性择优连接 择优连接的更迭机理 增长制约条件及增长方式 局部相互作用 适应度模型

45 其他工作 流驱动的复杂网络模型（科大王文旭等） 具有随机响应的动态有向小世界模型 （南航朱陈平等）

46 六、主要参考文献 Albert, R., H. Jeong, and A.-L. Barabási, Diameter of the World-Wide-Web,1999, Nature (London)401, 130. Barabási, A.-L., and R. Albert, Emergence of scaling in random networks, 1999, Science 286, 509 . Barabási, A.-L., R. Albert, and H. Jeong, Mean-field theory for scale-free random networks, 1999, Physica A 272, 173. Albert, R., and A.-L. Barabási, statistical Mechanics of complex network, 2002, Rev. Mod. Phys. Vol. 74, No.1,

47 谢谢大家！

48 网络图的基本概念 图的基本元素：节点、边 关联，邻接 有限图，无限图 规则图，随机图 有向图，无向图

49 网络图的基本概念 度、平均度 节点的度分布 最短路径与平均路径长度 集聚系数

50