复杂网络complex-networks.pptVIP

复杂网络 樊瑛 北京师范大学管理学院系统科学系 2011.07.18 Complex Systems Complex systems are all around us: ?? economies ?? nature: ant, bee, bird colonies ?? little robots 相互作用与复杂性 Complex Networks complex networks are the backbone of complex systems every complex system is a network of interaction among numerous smaller elements understanding a complex system = break down into parts + reassemble network anatomy is important to characterize because structure affects function (and vice-versa) 复杂网络研究所关心的问题 如何建立复杂网络？网络研究中的反问题 如何定量刻画复杂网络？ 网络结构的描述及其性质 网络是如何发展成现在这种结构的？ 网络演化模型 网络特定结构的后果是什么？正问题 网络结构的鲁棒性 网络上的动力学行为和过程 复杂网络的数学描述 网络G=（V, E），由点集V（G）和边集E（G）组成的一个图，可分为无向、有向和加权网络 令ei∈ E（G），每条边ei有V（G）中的一对点(u,v)与之对应； 如果任意(u,v)与(v,u)对应同一条边，则称为无向网络，否则为有向网络； 如果任意∣ei ∣ =1，则称为无权网络，否则为加权网络。 连接矩阵及拉普拉斯矩阵 技术网络 社会网络 交通运输网络 生态、生物网络 不同领域的复杂网络 社会网：演员合作网，朋友网，姻亲关系网，科研合作网，Email网，短信网… 生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络… 信息网络：WWW，专利使用，论文引用，… 技术网络：电力网，Internet，电话线路网， 交通运输网：航线网，铁路网，公路网，自然河流网 经济系统：投入产出网，国际贸易，… 网络研究的历史 1736，欧拉：哥尼斯堡七桥 1950，Erdos, Renyi: 随机图论 1998，Strogatz； 1999，Barabasi: 小世界和无标度网络 复杂网络的兴起 计算机技术的发展： 使我们拥有各种网络的数据库，并有可能对大规模的网络进行实证研究 普适性的发现： 许多实际网络具有相同的定性性质 且已有的理论不能描述和解释 理论研究的发展 小世界网络 (Small World Network), 无标度网络 (Scale-free Network) 统计物理学的研究手段 复杂网络研究所关心的问题 网络的拓扑结构——静态几何量及其统计性质 度、聚集系数、最短路径、介数、权、相关性 网络上的聚类分析 网络的演化性质和机制模型 时间演化性质，偏好性的检验 Small World Network ，Scale Free Network-BA 模型 网络的结构与功能 网络的容错与抗攻击能力 网络上的动力学性质 对网络结构的描述 几何量及其分布 度（Degree）：朋友的个数 集聚系数（群系数）（Clustering coefficient）： 朋友的朋友还是不是朋友的情况 最短路径（Shortest path）： 两个顶点之间边数最少的路径 介数（Betweenness）： 经过我的最短路径的条数 一个简单的例子 复杂网络的统计分析 度及其分布（Degree） 集聚系数及其分布（Clustering Coefficient） 统计性质的描述方法： Zipf Plot（顺序、出现频次) 频数统计 复杂网络的结构 规则网络 (a) 完全连接; (b) 最近邻居连接; (c) 星形连接 基本网络模型 随机图论 - Erd?s and Rényi (1960) ER 随机图模型统治四十余年…… 直到今天 …… 当今大量可获取的数据＋高级计算工具，促使人们重新考虑随机图模型及其方法 近年来的重大发现: