复杂网络 —— 李怡 胡金晓 姜思伽 朱敏 —— 李怡 胡金晓 姜思伽 朱敏

小组分工

of14 —— 开发框架的使用和推广 1 引入 复杂网络的研究 首先，神马是复杂网络 nia ？ 百度是这样告诉我们的： 复杂网络（ Complex Network ），具有自组织、自 相似、吸引子、小世界、无标 度中部分或全部性质的网络称 为复杂网络。

of14 —— 开发框架的使用和推广 1 引入 复杂网络的研究

of14 —— 开发框架的使用和推广 生活中的复杂网络 1 引入 1 ）社会网络 – 人际关系网， 通讯网，企事业关系网，金融关系网，论文引用， 科研合作网 2 ）信息网络 –WWW ， Internet ，计算机共享，专利使用网 3 ） 交通运输网 – 航线网，铁路网，公路网，自然河流网 4 ）生物网 – 食物链网，生物神经网，新陈代谢网，蛋白质网，基因网络， 细胞网 复杂网络的研究

of14 —— 开发框架的使用和推广 1736 欧拉 哥尼斯堡七桥 2 History01 Euler （ 1707~1783 ），瑞 士数学家 ，图论之 父 复杂网络的研究 1736 年，七 桥游戏 复杂网络的研究

of14 —— 开发框架的使用和推广 1736 欧拉 哥尼斯堡七桥 2 History01 一笔画问题 复杂网络的研究

of14 —— 开发框架的使用和推广 ER 随机图理论 3 History01 复杂网络的研究 20 世纪 60 年代，由两位匈牙利数学家 Erdǒs 和 Rényi 建立的随机图理论（ random graph theory ）被公认为是在数学上开创了复杂网 络理论的系统性研究。 Erdǒs 和 Rényi 的最重要的发现是： ER 随机 图的许多重要性质都是突然涌现的。也就是说， 对于任一给定的概率 p ，要么几乎每一个图都具 有某个性质 Q （比如说，连通性），要么几乎每 一个图都不具有该性质。 在 20 世纪的后 40 年中，随机图理论一直是研 究复杂网络的基本理论。 Erdǒs 和 Rényi 的最重要的发现是： ER 随机 图的许多重要性质都是突然涌现的。也就是说， 对于任一给定的概率 p ，要么几乎每一个图都具 有某个性质 Q （比如说，连通性），要么几乎每 一个图都不具有该性质。 在 20 世纪的后 40 年中，随机图理论一直是研 究复杂网络的基本理论。 复杂网络的研究

of14 —— 开发框架的使用和推广 小世界的实验 4 History01 复杂网络的研究 20 世纪 60 年代美国哈佛大学的社会心理学家 Stanley Milgram 通过一些社会调查后给出的推断 是：地球上任意两个人之间的平均距离是 6 。这 就是著名的 “ 六度分离 ” （ six degrees of separation ）推断。 六度分离 复杂网络的研究

of14 —— 开发框架的使用和推广 小世界的实验 Bacon 数 5 复杂网络的研究 History01 为了检验 “ 六度分离 ” 的正确性，小世界实 验 —Bacon 数。美国 Virginia 大学计算机系的 科学家建立了一个电影演员的数据库，放在 网上供人们随意查询。网站的数据库里目前 总共存有近 60 万个世界各地的演员的信息以 及近 30 万部电影信息。通过简单地输入演员 名字就可以知道这个演员的 Bacon 数。 截止到实验前，世界电影史上共产生了大约 23 万部电影， 78 多万名电影演员。 Kavin Bacon 在许多部电影中饰演小角色。 几年前,Virginia 大学的计算机专家 Brett Tjaden 设计了一个 游戏，他声称电影演员 Kevin Bacon 是电影界的中心。 在游戏里定义了一个所谓的 Bacon 数：随便想一个演员， 如果他（她）和 Kavin Bacon 一起演过电影，那么他（她） 的 Bacon 数就为 1 ；如果他（她）没有和 Bacon 演过电影， 但是和 Bacon 数为 1 的演员一起演过电影，那么他的 Bacon 数就为 2 ；依此类推。 发现 : 在曾经参演的美国电影演员 中，没有一个人的 Bacon 数超过 4 。 复杂网络的研究

of14 —— 开发框架的使用和推广 小世界的实验 5 复杂网络的研究 History01 通过简单地输入演员名字就可以知道这个演员的 bacon 数。 这样周星驰的 Bacon 数为 3 。 对 78 万个演员所做的统计：演员的最大 Bacon 数仅仅为 8 ，平均 Bacon 数仅为 Bacon 数 周星驰 豪门夜宴 洪金宝 死亡游戏 Colleen Camp Trapped Kevin Bacon 复杂网络的研究

of14 —— 开发框架的使用和推广 小世界的实验 Erdos 数 6 History01 Paul Erdos(( ) ：是出生于匈牙利的犹太籍 数学家，被公认为 20 世纪最伟大的天才之一。 Erdos 毕生发表的论文超过 1500 篇（在数学史上仅次 于欧拉 (Euler ， )) ，超长的合作者名单, 合 作者超过 450 位。但若加上别人所做但曾获他关键性 提示之论文，则他的论文应有数万篇。 "Mathematical Reviews" 曾把数学划分为大约六十个 分支， Erdos 的论文涉及到了其中的 40%. 复杂网络的研究

of14 —— 开发框架的使用和推广 Erdos Andrew Odlyzko Chris M.Skinner Andrew Wiles 小世界的实验 Erdos 数 6 History01 数学家以下述方式来定义 Erdos 数 : Erdos 本人之 Erdos 数为 0 ，任何人若曾与 Erdos 合 写过论文， 则其 Erdos 数为 1 。任何人若曾与一位 Erdos 数为 l( 且不曾与有更少的 Erdos 数 ) 的人合写过论文，则 他的 Erdos 数为 2… 证明 Fermat 大定理的 Andrew Wiles ，他的研究方 向与 Erdos 相去甚远，但他的 Erdos 数只有 3 。 数学家以下述方式来定义 Erdos 数 : Erdos 本人之 Erdos 数为 0 ，任何人若曾与 Erdos 合 写过论文， 则其 Erdos 数为 1 。任何人若曾与一位 Erdos 数为 l( 且不曾与有更少的 Erdos 数 ) 的人合写过论文，则 他的 Erdos 数为 2… 证明 Fermat 大定理的 Andrew Wiles ，他的研究方 向与 Erdos 相去甚远，但他的 Erdos 数只有 3 。 复杂网络的研究

of14 —— 开发框架的使用和推广 WS 小世界模型 7 History02 复杂网络的研究 Watts 和 Strogatz 小世界网络模型 (Small World Networks) 《 “ 小世界 ” 网络的集体动力学》 Nature Collective Dynamics of ‘Small-World’ Networks Barabási 和 Albert 无标度网络模型 (Scale Free Networks) 《随机网络中标度的涌现》 Science Emergence of Scaling in Random Networks BA 无标度模型 复杂网络的研究

of14 —— 开发框架的使用和推广 7 History02 复杂网络的研究 基本概念  平均路径长度 L  聚类系数 C ：在简单图中，设节点 v 的邻集为 N(v), |N(v)|=k i ，则节点 v 的聚类系数定义为这 k i 个节点之间存在边数 E i 与总的可能边数 k i (k i - 1)/2 之比，即： C i =2E i /k i (k i -1)  平均度  度分布函数 p(k): 随机选定节点的度恰好为 k 的概率 复杂网络的研究

of14 —— 开发框架的使用和推广 7 History02 复杂网络的研究 For Example K=5 C=0 K=5 C=1 复杂网络的研究

of14 —— 开发框架的使用和推广 7 History02 复杂网络的研究 规则网络 一般情况下， 聚集系数较大， 平均最短路径较长。 复杂网络的研究

of14 —— 开发框架的使用和推广 7 History02 复杂网络的研究 ER 随机图 = 完全随机图 一般情况下， 聚集系数较小， 平均最短路径较短。 复杂网络的研究

of14 —— 开发框架的使用和推广 BA 无标度： 网络增长 偏好链接 实际网络度分布具有幂律形式 自相似结构： 8 History02 复杂网络的研究 ER 随机图：完全随机图 Possion 分布 WS 小世界 规则网络较大的聚集系数 随机图较小的平均路径长度 复杂网络的研究

of14 —— 开发框架的使用和推广 8 History02 复杂网络的研究 BA 无标度模型的度分布 幂律分布 ——Power Law  =-3 复杂网络的研究

of14 —— 开发框架的使用和推广 9 History02 复杂网络的研究 复杂网络的鲁棒性和脆弱性 复杂网络的研究

of14 —— 开发框架的使用和推广 9 History02 复杂网络的研究 Error and Attack Tolerance (a)(c) 对应 ER 随机图； (b)(d) 对应无标度网络；方块对应随机故障；圆点对应蓄意攻击 复杂网络的研究

of14 —— 开发框架的使用和推广 复杂网络的研究 疾病传播的 SIS 模型 I. 传染病 II. 基本状态 S 易感状态 I 感染状态 R 免疫状态 复杂网络的研究 定义

of14 —— 开发框架的使用和推广 10 复杂网络的研究 疾病传播的 SIS 模型 Ⅲ. 传染病模型 SIS 模型 SIR 模型 SI 模型 SIRS 模型 定义 复杂网络的研究

of14 —— 开发框架的使用和推广 模型的传播规则 11 复杂网络的研究 β γ 易感 S 感染 I 疾病传播模型的描述 疾病传播的 SIS 模型 复杂网络的研究

of14 —— 开发框架的使用和推广 12 复杂网络的研究 SIS 模型的传播方程 疾病传播的 SIS 模型 复杂网络的研究

of14 —— 开发框架的使用和推广 13 复杂网络的研究 三个假设 – 均匀混合假设 – 均匀性假设 – 规模不变假设 疾病传播的 SIS 模型 复杂网络的研究 结论