复杂网络的自组织演化.doc

复杂网络演化的自组织现象outlineu 复杂网络的基本理论1. 复杂网络的定义2. 复杂网络研究简史3. 复杂网络研究现状4. 复杂网络的研究对象5. 一些实际的复杂网络系统6. 复杂网络的拓扑性质7. 复杂网络的静态几何量8. 复杂网络的特征9. 复杂网络的重要特征10. 网络拓扑的基本模型及其性质 规则网络、随机网络、Small World网络、Scale Free网络（重点）等u 复杂网络演化的自组织理论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年Barabsi 和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，它的聚类系数Ci被定义为它所有相邻节点之间连的数目占可能的最大连边数目的比例。 整个网络的聚类系数C则是所有节点聚类系数的平均值。 在随机网络中，C=p, （由于边的分布是随机的）C 平均路径长度(average path length) 网络中两个顶点i，j之间的最短路径定义为所有连通(i,j) 的通路中, 所经过的其他顶点最少的一条或几条路径。 两个顶点i，j之间的距离dij定义为i，j之间最短路径上的边数。 网络的直径(diameter),定义为网络中任意两个顶点之间距离的最大值。 网络的平均路径长度(average path length), 定义为网络中任意两个顶点之间距离的平均值。即：描述网络的拓扑结构的物理量（2） 权(weight)： 边的重要性的量化 匹配（mixing）性：考察度值大的点倾向于和度值大的点连接,还是倾向于和度值小的点连接。 连接方向性：连接是否有方向性（有向或无向）WWW网是有向网络，涉及了IN度与OUT度及它们的关联。复杂网络的重要特征1. 小世界效应2. 无标度特性 两者之间的关系：无标度网络一定是小世界网络，小世界网络不一定是无标度网络复杂网络的重要特征(1) 小世界效应（Small World Effect） 大的集聚系数和小的平均最短距离 “六度分离”（Six Degrees of Separation）理论 Milgram,PsychologyToday1:61-67.(1967) 2001年哥伦比亚大学社会学系的一个研究小组建立了一个实验网站，终点是分布在不同国家的18个人（包括纽约的一位作家、澳大利亚的一名警察以及巴黎的一位图书管理员等等），志愿者通过这个网站把电子邮件发给最可能实现任务的亲友。结果一共有384个志愿者的邮件抵达了目的地，电子邮件大约只花了五到七步就传递到了目标。复杂网络的重要特征(2) 无标度特性 (Scale-free) 点的度分布服从无标度的幂律分布. 其中 P(k) 代表与 k 条边关联的点的个数小世界现象:小的网络平均距离和大的聚众节点的存在; 无标度特性: 网络节点扩张,强者越强的规律“The rich get richer”网络拓扑的基本模型及其性质 规则网络 随机网络 Small World网络 Scale Free网络（亦称BA无标度网络或SF网络） 比如美国的公路网是随机网络，但是其航空网却是无标度网络规则网络 规则网络是指平移对称性晶格,任何一个格点的近邻数目都相同。 各个节点的具有相同的度值 规则网络各顶点度值相同，因而符合delta分布 如图为最近邻耦合网络：每个节点都与它左右的K/2个节点相连。 对大的N, K, 有：聚类系数C3/4, 平均路径长度L无穷大 一般地，规则网络具有大的簇系数和大的平均距离。随机网络 ER随机图模型：顶点的度值服从 Poisson distribution，也称Poisson随机图 平均度：kp*N 平均路径长度Lln(N)/ln(k) 聚类系数: C=p 1 (由于极度稀疏) 随机网络具有小的簇系数和小的平均距离Small World模型 一个同时具有高的集聚程度,小的最短路径网络 如果实际网络同时存在宽的广度和大的深度的话,在这样的网络上的传染病传播显然将大大高于规则网络与随机网络。 1998年Watts和Strogatz为我们找到了这样的网络模型Small World 网络（发表在Nature上）. 度分布服从Poisson distribution 现在常称为：WS model 一般地，小世界网络具有大的簇系数和小的平均最短距离。复杂网络演化的自组织现象以无标度网络为例SF网络及其模型构造算法无标度网络中的无标度为什么无标度网络的度分布满足幂律分布？SF网络符合SOC的条件复杂网络的网络拓扑熵和标准结构熵复杂网络的自组织演化的表现复杂系统、复杂网络自相似结构的涌现规律的统一Scale Free网络 节点度服从幂律分布，就是说具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地表示。 幂函数曲线是一条下降相对缓慢的曲线，这使得度很大的节点可以在网络中存在。 对于随机网络和规则网络，度分布区间非常狭窄，几乎找不到偏离节点度均值较大的点，故其平均度可以被看作其节点度的一个特征标度。在这个意义上，我们把节点度服从幂律分布的网络叫做无标度网络（scale-free networks），并称这种节点度的幂律分布为网络的无标度特性。 无标度网络中的无标度（1）钟形曲线该图形在网络平均度数 Np 处有一个峰值. 网络中大多数结点连通度都集中在其附近,而远离它的结点数所占比例衰减很快,说明结点有同质性,人们称 为特征标度.（2）幂律曲线从上图可知,现在大多数结点仅有少量连线,而少数结点拥有大量连线,因为结点的异质性,于是特征标度消失了.为此,有人提议将scale-free networks 翻译成无标度网.BA无标度模型的构造算法 1999年，Barabsi 和Albert给出了构造无标度网络的演化模型。 形成机制：生长和择优连接 随机选取。重复以上新加点的过程足够多步所形成的网络的各顶点的度满足幂律分布p ( k) 。而且,指数= 3 与模型的参数 m0, m 无关。 现在常称为： BA Model 对于BA网络，它具有小的平均路径长度，至于聚类系数可大可小。 优先连接机制是SF网络演化的基本动力 SF网络中节点的加入是一个动态的过程，在每个新节点加入时都会在原有的节点中选择连线较多的作为连接对象，即择优增长，也就造成了类似经济学中的“富者更富”的现象。而这些“富者”就在整个网络中扮演着非同寻常的角色，主宰着整个网络，这样在针对无标度网的破坏中，只要针对网络的核心节点做选择性攻击，网络就很快陷入瘫痪。 无标度网络对随意攻击具有鲁棒性，对蓄意攻击具有脆弱性。其根源在于无标度网络中的度分布不均匀性。（robust yet fragile)为什么无标度网络的度分布满足幂律分布？BA模型描述的是一个生长的开放系统。BA模型中有两个非常重要的假设：生长和择优连接。下面我们用连续统方法来求解BA 模型. 设ki ( i) 为第i 步时添加的结点i 的度.而且初始条件这样我们就得到这就是节点的演化规律，根据这个演化规律，我们就得到于是 这就意味着，尽管网络在不断增长，但是最后都达到一个稳定的无标度状态。 BA无标度模型的精彩之处在于它把实际复杂网络的无标度特性归结为增长和优先连接这两个非常简单的机制。这很好体现了科学研究中的从复杂现象提取简单本质的特点 幂律是自组织形成的临界状态，复杂寓于简单，简单形式的幂律蕴含了自组织演化发展的必然结果。SF网络符合SOC的条件 复杂网络的网络拓扑熵 热力学理论指出，只有开放系统才能具有发展潜力，才能自发组织起来向更有序的状态发展。大多数现实世界中的系统是开放的,对应的网络也是开放的,通过不断地增加新元素到系统中而构成大型复杂网络,系统元素的增加贯穿于系统的整个生命周期. 例如,从万维网的发展历程可以看到新的网页增加随时间而呈指数增长,演员合作网络是通过不断添加新的演员来实现系统的增长,科研引文网络是通过不断地发表新论文而不断增长的. 可见这些系统通过获得新节点而不断地增长,系统具有开放性,并且是不断地发展的.按照系统科学理论，系统的开放性可从系统的熵S 的变化来分析。一个开放系统的熵值变化可分为和两部分 式中由于系统内部原因使系统的熵值发生变化，恒有 由于环境与系统的相互作用导致系统的熵值发生变化开放系统要从无序状态向有序状态转变，也就是要使整个系统的熵变小，即 式中，且， 由此可见系统要形成稳定有序的自组织结构，必须在与环境的物质、能量以及信息的交换中，让外界输入的负熵流大于系统内部自发产生的熵，使系统的熵减少，系统向有序方向转化。复杂网络系统满足自组织的条件 系统是开放的。 系统内粒子之间的相互作用是非线性的。 系统有涨落存在，并要控制参数达到某一临界值，使系统远离平衡态。网络拓扑熵 在无标度网络中存在极少数具有大量连接的中枢节点和大多数具有少量连接的节点，这样的网络是不均匀的表现在节点连通度分布上,就是度分布的曲线呈递减形态. 熵是系统的一种无序的度量. 如果网络是随机连接的,各个节点的重要度大致相当,则认为网络是无序的. 反之,如果网络是无标度的,网络中有少量的具有高连通度的中枢节点和大量的具有低连通度的节点,节点的重要性程度存在差异,可以认为这种网络是有序的. 网络拓扑熵是由连通度分布确定的,但是,拓扑熵可以更简洁地度量复杂网络的序状态. 我们称Ii 为第i节点的重要度 （1）其中n为网络中节点数目, k i 为第i 个节点的连接度它满足条件 （2） 其中 根据熵的基本定义给出网络的拓扑熵（香农公式） （3）由（2）式知 （4）若令 即式中网络规模,即节点数解得 此时，可得熵的最大值为当网络中所有节点都与某一个中枢节点相连时,网络最不均匀,网络结构熵最小,即 代入香农公式可以得到网络结构熵最小值为：为了排出节点数目n 对H的影响, 我们将网络结构熵进行归一化.我们称为网络的标准结构熵.显然 我们提出用网络结构熵研究复杂网络的非同质性, 并不是说用网络结构熵取代连接度分布，网络结构熵与连接度分布的关系, 就如同随机变量的数字特征与其概率分布函数的关系, 两者是互为补充的，网络结构熵是由连接度分布确定的, 网络结构熵可以更加精确简洁的度量复杂网络的非同质性。 把系统描述成网络拓扑后,系统与环境的物质、能量及信息交换转化为网络中节点按照某种简单的机制与新节点连接、网络内节点之间的边的断开或重联,使网络中节点的度分布发生变化,也就是系统中的新元素与系统中的原有元素发生相互作用,使系统远离平衡态,向有序方向发展. 可以对现实网络进行观察,对于演员合作网络,一名新演员最有可能与一名比较有名的演员合作而扮演配角,从另外一个角度来看,出名的演员由于片约多,因而与新演员合作的概率大. 同样对于万维网来说,一个新的网站往往包含了许多内容相关的流行网站的链接,一个新建网页包含知名的网页的超链接. 对引文网,一篇新论文引用相关领域的知名论文的概率要比引用不知名的论文的概率大. 以上的例子可以说明新节点连接到网络中现有节点的概率是有差异的,对新节点来说,它具有择优连接的本质特性,对网络中的节点来说,具有竞争获得连接的特性,也就是连通度越大的节点获得新节点连接的概率越大,类似于社会网中富者愈富的现象. 网络中节点不断增长和择优连接的内在机制还原到现实世界系统中,可体现为能量、物质以及信息在外部环境与系统之间的流动,并不断地促使系统远离平衡态. 从以上分析可以发现,这些网络演化规则不仅包括了随机性,而且具有适应性,是促使系统远离平衡态,不断地向有序的方向发展的内在机制. 组成系统的系统元素之间存在着相互作用,一般而言,这些相互作用不满足叠加性,因而根据系统元素相互作用而构成的大型网络是非线