复杂网络建模与控制

《复杂网络建模与控制》由会员分享，可在线阅读，更多相关《复杂网络建模与控制（57页珍藏版）》请在金锄头文库上搜索。

1、厦门大学 信息科学与技术学院厦门大学 信息科学与技术学院 Email xiangly Tel 13720898017 项林英项林英 复杂网络建模与控制复杂网络建模与控制 Modelling and Control of Complex Networks 2012 3 282 复杂网络模型复杂网络模型 1959年年Erd s 和和R nyi引入 随机图论 引入 随机图论 1736年欧拉 解决哥尼斯 堡七桥问题 创立图论 年欧拉 解决哥尼斯 堡七桥问题 创立图论 规则网络随机网络规则网络随机网络 2012 3 28复杂网络模型3 三种规则网络和三种规则网络和ER随机网络的基本拓扑性质比较随机网络的

2、基本拓扑性质比较 网络边数平均路径长 度 聚类系数度分布网络边数平均路径长 度 聚类系数度分布 全耦合网络全耦合网络N N 1 211delta 最近邻网络最近邻网络NK 2 N 2 2K 3 K 2 4 K 1 delta 星形网络星形网络N 1 2 2 N0 ER随机网络随机网络pN N 1 2 lnN lnp N 1 Poission 4 最近邻网络与最近邻网络与ER随机网络的拓扑性质比较随机网络的拓扑性质比较 网络边数平均路径长度聚类系数度分布网络边数平均路径长度聚类系数度分布 最近邻网络最近邻网络NK 2 N 2 2K 3 K 2 4 K 1 delta ER随机网络随机网络pN N

3、 1 2 lnN lnp N 1 Poission 5 最近邻网络与最近邻网络与ER随机网络的拓扑性质比较随机网络的拓扑性质比较 网络边数网络边数平均路径长度平均路径长度聚类系数度分布聚类系数度分布 最近邻网络最近邻网络NK 2 N 2 2K 3 K 2 4 K 1 delta ER随机网络随机网络pN N 1 2 lnN lnp N 1 Poission 6 最近邻网络与最近邻网络与ER随机网络的拓扑性质比较随机网络的拓扑性质比较 网络边数网络边数平均路径长度平均路径长度聚类系数度分布聚类系数度分布 最近邻网络最近邻网络NK 2 N 2 2K 3 K 2 4 K 1 delta ER随机网络

4、随机网络pN N 1 2 lnN lnp N 1 Poission 最近邻网络 最近邻网络 较大的平均路径长度较大的平均路径长度 ER随机网络 随机网络 较小的平均路径长度较小的平均路径长度 7 最近邻网络与最近邻网络与ER随机网络的拓扑性质比较随机网络的拓扑性质比较 最近邻网络 最近邻网络 较大的平均路径长度较大的平均路径长度 ER随机网络 随机网络 较小的平均路径长度较小的平均路径长度 网络边数平均路径长度网络边数平均路径长度聚类系数聚类系数度分布度分布 最近邻网络最近邻网络NK 2 N 2 2K 3 K 2 4 K 1 delta ER随机网络随机网络pN N 1 2 lnN lnp N

5、 1 Poission 8 最近邻网络与最近邻网络与ER随机网络的拓扑性质比较随机网络的拓扑性质比较 最近邻网络 最近邻网络 较大的平均路径长度较大的平均路径长度和和较大的聚类系数较大的聚类系数 ER随机网络 随机网络 较小的平均路径长度较小的平均路径长度和和较小的聚类系数较小的聚类系数 网络边数平均路径长度网络边数平均路径长度聚类系数聚类系数度分布度分布 最近邻网络最近邻网络NK 2 N 2 2K 3 K 2 4 K 1 delta ER随机网络随机网络pN N 1 2 lnN lnp N 1 Poission 9 最近邻网络与最近邻网络与ER随机网络的拓扑性质比较随机网络的拓扑性质比较 最

6、近邻网络 最近邻网络 较大的平均路径长度较大的平均路径长度和和较大的聚类系数较大的聚类系数 ER随机网络 随机网络 较小的平均路径长度较小的平均路径长度和和较小的聚类系数较小的聚类系数 网络边数平均路径长度聚类系数网络边数平均路径长度聚类系数度分布度分布 最近邻网络最近邻网络NK 2 N 2 2K 3 K 2 4 K 1 delta ER随机网络随机网络pN N 1 2 lnN lnp N 1 Poission 10 最近邻网络与最近邻网络与ER随机网络的拓扑性质比较随机网络的拓扑性质比较 最近邻网络 最近邻网络 较大的平均路径长度较大的平均路径长度和和较大的聚类系数较大的聚类系数 ER随机网

7、络 随机网络 较小的平均路径长度较小的平均路径长度和和较小的聚类系数较小的聚类系数 节点度服从节点度服从Poisson分布 图像是一条钟形的曲 线 因而比较 分布 图像是一条钟形的曲 线 因而比较 均匀均匀 即大部分的节点度相 差不多 即大部分的节点度相 差不多 网络边数平均路径长度聚类系数网络边数平均路径长度聚类系数度分布度分布 最近邻网络最近邻网络NK 2 N 2 2K 3 K 2 4 K 1 delta ER随机网络随机网络pN N 1 2 lnN lnp N 1 Poission 11 最近邻网络与最近邻网络与ER随机网络的拓扑性质比较随机网络的拓扑性质比较 最近邻网络 最近邻网络 较

8、大的平均路径长度较大的平均路径长度和和较大的聚类系数较大的聚类系数 ER随机网络 随机网络 较小的平均路径长度较小的平均路径长度和和较小的聚类系数较小的聚类系数 节点度服从节点度服从Poisson分布 图像是一条钟形的曲 线 因而比较 分布 图像是一条钟形的曲 线 因而比较 均匀均匀 即大部分的节点度相 差不多 实际网络 即大部分的节点度相 差不多 实际网络 较小较小的平均路径长度和的平均路径长度和较大较大的聚类系数的聚类系数 网络边数网络边数平均路径长度聚类系数平均路径长度聚类系数度分布度分布 最近邻网络最近邻网络NK 2 N 2 2K 3 K 2 4 K 1 delta ER随机网络随机网

9、络pN N 1 2 lnN lnp N 1 Poission 小世界特性小世界特性 12 完全规则网络和完全随机网络之间可能的联系完全规则网络和完全随机网络之间可能的联系 13 第四章 复杂网络模型第四章 复杂网络模型 4 1 规则网络模型规则网络模型 4 2 随机网络模型随机网络模型 4 3 小世界网络模型小世界网络模型 4 4 无标度网络模型无标度网络模型 14 小世界现象小世界现象 在一千多年前 我国唐朝诗人王勃在 送杜少府之任蜀州 中的名句 在一千多年前 我国唐朝诗人王勃在 送杜少府之任蜀州 中的名句 海内存知己 天涯若比邻海内存知己 天涯若比邻 已经涵盖了小世界现象 已经涵盖了小世界

10、现象 中国人从人文和哲学上最先认识到了小世界现象中国人从人文和哲学上最先认识到了小世界现象 1967年美国社会学家年美国社会学家Milgram提出的提出的 六度分离六度分离 假设假设 作了一定的社会调查和实验证实作了一定的社会调查和实验证实 复杂网络模型15 16 小世界网络小世界网络 Collective Dynamics of small world networks Nature 1998 393 440 442 S H Strogatz D J Watts Cornell University 复杂网络模型17 复杂网络模型18 19 WS小世界模型的构造算法小世界模型的构造算法 首先

11、开始于规则图形首先开始于规则图形 初 始有数目固定的 初 始有数目固定的 N个节 点 每个节点有 个节 点 每个节点有K个最近 邻 构成一个规则的一维 圆环 个最近 邻 构成一个规则的一维 圆环 随机化重连随机化重连 以概率 以概率P对 圆环中的每一条边进行重 新连接 对 圆环中的每一条边进行重 新连接 这个过程不能自 身连接和重复连接 这个过程不能自 身连接和重复连接 20 P 0 0 P 1 P 1 2012 3 28复杂网络模型21 P 0 0 P 1 P 1 a 规则网络 规则网络 b 小世界网络 小世界网络 c 随机网络随机网络 22 WS小世界模型的基本性质小世界模型的基本性质 平

12、均路径长度 平均路径长度 聚类系数 聚类系数 度分布 度分布 LWS N K f NKp CWS 3 K 2 4 K 1 1 p 3 Poission分布分布 2012 3 28复杂网络模型23 仿真分析仿真分析 平均路径长度 平均路径长度 LWS N K f NKp 聚类系数 聚类系数 CWS 3 K 2 4 K 1 1 p 3 平均路径长度平均路径长度L和聚类系数和聚类系数C关于重连概率关于重连概率p的关系 给定参数 的关系 给定参数 N 1000 K 10 2012 3 28复杂网络模型24 仿真分析仿真分析 平均路径长度 平均路径长度 LWS N K f NKp 聚类系数 聚类系数 C

13、WS 3 K 2 4 K 1 1 p 3 较较小小的平均路径长度的平均路径长度L 较较大大的聚类系数的聚类系数C 平均路径长度平均路径长度L和聚类系数和聚类系数C关于重连概率关于重连概率p的关系的关系 小世界网络 小世界网络 给定参数给定参数 N 1000 K 10 25 实际验证实际验证 小世界网络的三个实例小世界网络的三个实例 26 Small Word Networks Some examples 27 科学家合作网科学家合作网 节点 科学家 边 合作发表文章或合作研究项目 节点 科学家 边 合作发表文章或合作研究项目 M E J Newman 2001 and A L Barab si

14、 et al 2001 L 4 9 28 电路图电路图 节点 元器件 边 电子线路 节点 元器件 边 电子线路 R F Cancho et al Phys Rev 64 046119 2001 L 4 29 ER随机图模型与随机图模型与WS小世界模型的共同点小世界模型的共同点 30 ER随机图模型与随机图模型与WS小世界模型的共同点小世界模型的共同点 网络连接度分布是网络连接度分布是泊松分布泊松分布 具有 具有同质性同质性 在一个平均值 处达到高峰并按指数形式进行衰减 在一个平均值 处达到高峰并按指数形式进行衰减 31 ER随机图模型与随机图模型与WS小世界模型的共同点小世界模型的共同点 网络

15、连接度分布是网络连接度分布是泊松分布泊松分布 具有 具有同质性同质性 在一个平均值 处达到高峰并按指数形式进行衰减 在一个平均值 处达到高峰并按指数形式进行衰减 网络中节点数目是固定不变的 是一种网络中节点数目是固定不变的 是一种静态静态的网络模型 的网络模型 32 ER随机图模型与随机图模型与WS小世界模型的共同点小世界模型的共同点 网络连接度分布是网络连接度分布是泊松分布泊松分布 具有 具有同质性同质性 在一个平均值 处达到高峰并按指数形式进行衰减 在一个平均值 处达到高峰并按指数形式进行衰减 网络中节点数目是固定不变的 是一种网络中节点数目是固定不变的 是一种静态静态的网络模型 的网络模

16、型 实际网络 实际网络 33 第四章 复杂网络模型第四章 复杂网络模型 4 1 规则网络模型规则网络模型 4 2 随机网络模型随机网络模型 4 3 小世界网络模型小世界网络模型 4 4 无标度网络模型无标度网络模型 34 无标度网络无标度网络 Emergence of scaling in random networks Science 1999 286 509 512 R AlbertA L Barab si Norte Dame University 复杂网络模型35 36 37 BA无标度网络模型的构造算法无标度网络模型的构造算法 38 BA无标度网络模型的构造算法无标度网络模型的构造算法 增长增长 39 BA无标度网络模型的构造算法无标度网络模型的构造算法 增长增长 优先连接优先连接 40 BA无标度网络模型的构造算法无标度网络模型的构造算法 增长增长 从一个具有 从一个具有m0个节点的个节点的连通连通网络开始 在每一个时间 步 加入 网络开始 在每一个时间 步 加入一个一个新的节点 并与新的节点 并与m m m0 个网络中已经存在的 节点建立连接 个网络中已经存在的 节点建立