复杂网络演化的自组织现象outline◆复杂网络的基本理论1.复杂网络的定义2.复杂网络研究简史3.复杂网络研究现状4.复杂网络的研究对象5.一些实际的复杂网络系统6.复杂网络的拓扑性质7.复杂网络的静态几何量8.复杂网络的特征9.复杂网络的重要特征10.网络拓扑的基本模型及其性质规则网络、随机网络、Small World网络、Scale Free网络（重点）等◆复杂网络演化的自组织理论1.SF网络及其模型构造算法2.无标度网络中的无标度3.为什么无标度网络的度分布满足幂律分布？4.SF网络符合SOC的条件5.复杂网络的网络拓扑熵和标准结构熵6.复杂网络的自组织演化的表现7.复杂系统、复杂网络自相似结构的涌现规律的统一复杂网络（complex network)•定义：复杂网络是指大量具有紧密联系和彼此间相互作用的单元所组成的网络。
•网络化的研究方法将现实复杂系统中的研究对象的元素抽象为节点（vertice)，将元素之间的关系抽象为网络中的边(edge).•复杂网络已经成为一门新兴的交叉学科。
从自然界到人类社会,从物理科学到生命科学, 从自然科学到社会科学,以至技术科学、工程技术等众多领域, 网络科学普遍受到了空前的关注和广泛重视, 具有广泛的应用和发展前景.•复杂网络被称为“网络的新科学”（new science of network）.复杂网络研究简史•从七桥问题谈起（1736年欧拉）•随机图理论（1959年Erdos和Renyi ）•小世界实验（1967年Milgram)•弱连接的强度（1973年Granoveretter)•小世界模型（1998年Watts和Strogatz ）•无标度网络（1999年Barabási 和Albert）复杂网络的研究现状1.复杂网络作为复杂系统研究领域的一个分支，近年来得到科学界前所未有的关注，网络研究的新成果不断地在一些学术刊物上发表。
2.近10 年来迅猛发展起来的复杂网络理论为研究复杂性与复杂系统科学提供了一个重要支撑点, 它高度概括了复杂系统的重要特征, 无论是在理论还是在应用方面都具有很强的生命力, 而且在各个方面都得到了很大发展.3.复杂网络的研究成为了近10 年来全世界不同学科（包括力学、物理、生物、系统控制、工程技术、经济、社会、军事等）科学家研究的热点课题。
统计物理与复杂性研究•非线性科学（孤子、湍流、斑图、混沌应用、混沌同步、量子混沌和其它(混沌计算、耦合振子、低维与高维混沌、时间序列等等)•复杂性研究（复杂性定义、复杂系统性质、元胞自动机、复杂网络）•其他相关研究（统计物理基本方法与问题、随机过程、晶格理论、输运过程、自组织(临界)现象、热力学、金融物理、社会物理、交通流、相变、有机材料、其它）近几年来,大量关于复杂网络的文章发表在Science ,Nature ,PRL , PNAS 等国际一流的刊物上,从一个侧面反映了复杂网络已经成为物理界的一个新兴的研究热点.香港城市大学的陈关荣教授统计了几年来被SCI 收录的关于复杂网络的文章数量，从中可以看出明显的增长趋势。
一些实际的复杂网络系统•Web•Internet 网络,•电影演员合作网络,•科学家合作网络,•论文引用网络•电话呼叫网络•语言学网络,•电力网络•经济网络,•交通网络•疾病传播•神经网络•人类性关系网络,•蛋白质互作用网络,•蛋白质折叠关系网络•……..其他一些复杂网络•电话线路•电影演员合作网络•交通网•供电系统•人际关系网•论文引用网络网络的拓扑性质•数学家和物理学家在考虑网络的时候,往往只关心节点之间有没有边相连,至于节点到底在什么位置,边是长还是短,是弯曲还是平直,有没有相交等等都是他们不在意的.•网络的拓扑性质：在这里,我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质,相应的结构叫做网络的拓扑结构.复杂网络的特征绝大多数实际的复杂网络具有以下5个特征•(1) 网络的大规模性和行为的统计性:网络节点数可以有成百上千万,甚至更多,大规模性的网络行为具有统计特性·•(2) 节点动力学行为的复杂性:各个节点本身可以是个非线性系统(可以有离散的和连续微分方程描述) ,具有分岔和混沌等非线性动力学行为·•(3) 网络连接的稀疏性:一个有N 个节点的具有全局耦合结构的网络的连接数目为O ( N的平方) ,而实际大型网络的连接数目通常为O ( N) ·•4) 连接结构的复杂性:网络连接结构既非完全规则也非完全随机, 但却具有其内在的自组织规律·•(5) 网络时空演化的复杂性:复杂网络具有空间和时间的演化复杂性, 展示出丰富的复杂行为,特别是网络节点之间不同类型的同步化运动,包括出现周期、非周期(混沌) 和阵发行为等运动·•大多数实际的网络系统同时具有3 个主要特征:小世界、无标度和高群聚性·描述网络的拓扑结构的物理量（1）A 度(degree)：与网络点相连的边的条数B 聚集系数(clustering coefficient )：与同一点相连的两点也相连的概率的统计平均。
C 平均路径长度（average path length ）：网络中任意两个节点之间的距离的平均值。
D介数(between)：经过给定边（点）的最短路径的条数（包括边的介数及点的介数）。
A 度分布（degree distribution）• 一个顶点的度是指与此顶点连接的边的数量。
• 在有向网络中，分为：出度，入度• 研究包括：度及其分布特征，度的相关性。
• 度值的分布特征是网络的重要几何性质。
• 规则网络各顶点度值相同，因而符合delta 分布 • 随机网络符合泊松分布•大量实际网络存在幂律(power-law)形式的度分布，即无标度网络（Scale Free Networks ）。
• 在聚集反应中，速率核的表达式也与度有关B 聚类系数(clustering coefficient)• 来源于社会学中的“三倍传递比”(fraction of transitive triples)• 在朋友关系网中，你的两个朋友很可能彼此也是朋友。
这种属性称为网络的聚类特性。
• 用数学化的语言来说，对于某个节点i ，它的聚类系数C i 被定义为它所有相邻节点之间连的数目占可能的最大连边数目的比例。
• 整个网络的聚类系数C 则是所有节点聚类系数的平均值。
• 在随机网络中，C=p, （由于边的分布是随机的）C 平均路径长度(average path length)• 网络中两个顶点i ，j 之间的最短路径定义为所有连通(i,j) 的通路中, 所经过的其他顶点最少的一条或几条路径。
• 两个顶点i ，j 之间的距离d ij 定义为i ，j 之间最短路径上的边数。
• 网络的直径(diameter),定义为网络中任意两个顶点之间距离的最大值。
• 网络的平均路径长度(average path length), 定义为网络中任意两个顶点之间距离的平均值。
即：ν)();|;(11-);|;(lj i Jk j i l k K j i l k j i l k K j i l k vu A A A A =++−−−→−+，，，，2/Nji ij C d L ∑>=描述网络的拓扑结构的物理量（2）•权(weight)：边的重要性的量化•匹配（mixing）性：考察度值大的点倾向于和度值大的点连接,还是倾向于和度值小的点连接。
•连接方向性：连接是否有方向性（有向或无向）[WWW网是有向网络，涉及了IN 度与OUT度及它们的关联]。
复杂网络的重要特征1.小世界效应2.无标度特性•两者之间的关系：无标度网络一定是小世界网络，小世界网络不一定是无标度网络复杂网络的重要特征(1)•小世界效应（Small World Effect）•大的集聚系数和小的平均最短距离•“六度分离”（Six Degrees of Separation）理论[ Milgram, Psychology Today 1: 61-67. (1967) ]2001年哥伦比亚大学社会学系的一个研究小组建立了一个实验网站，终点是分布在不同国家的18个人（包括纽约的一位作家、澳大利亚的一名警察以及巴黎的一位图书管理员等等），志愿者通过这个网站把电子邮件发给最可能实现任务的亲友。
结果一共有384个志愿者的邮件抵达了目的地，电子邮件大约只花了五到七步就传递到了目标。
复杂网络的重要特征(2)•无标度特性(Scale-free)点的度分布服从无标度的幂律分布.其中P(k) 代表与k 条边关联的点的个数小世界现象:小的网络平均距离和大的聚众节点的存在;无标度特性: 网络节点扩张,强者越强的规律“The rich get richer”网络拓扑的基本模型及其性质•规则网络•随机网络•Small World网络•Scale Free网络（亦称BA无标度网络或SF网络）比如美国的公路网是随机网络，但是其航空网却是无标度网络规则网络γ-k kP~)(•规则网络是指平移对称性晶格,任何一个格点的近邻数目都相同。
•各个节点的具有相同的度值•规则网络各顶点度值相同，因而符合delta分布•如图为最近邻耦合网络：每个节点都与它左右的K/2个节点相连。
•对大的N, K, 有：聚类系数C~3/4,平均路径长度L~无穷大•一般地，规则网络具有大的簇系数和大的平均距离。
随机网络•ER随机图模型：顶点的度值服从Poisson distribution，也称Poisson随机图•平均度：k~p*N•平均路径长度L~ln(N)/ln(k)•聚类系数: C=p <<1 (由于极度稀疏)•随机网络具有小的簇系数和小的平均距离Small World模型•一个同时具有高的集聚程度,小的最短路径网络•如果实际网络同时存在宽的广度和大的深度的话,在这样的网络上的传染病传播显然将大大高于规则网络与随机网络。
•1998年Watts和Strogatz为我们找到了这样的网络模型—Small World 网络（发表在Nature上）.•度分布服从Poisson distribution•现在常称为：WS model•一般地，小世界网络具有大的簇系数和小的平均最短距离。
复杂网络演化的自组织现象——以无标度网络为例SF网络及其模型构造算法无标度网络中的无标度为什么无标度网络的度分布满足幂律分布？SF网络符合SOC的条件复杂网络的网络拓扑熵和标准结构熵复杂网络的自组织演化的表现复杂系统、复杂网络自相似结构的涌现规律的统一Scale Free网络•节点度服从幂律分布，就是说具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地表示。