网络动力学课件.ppt

1、复杂系统与复杂网络网络动力学6.1复杂网络上的物理传输过程动力学6.2网络的同步6.1 网络上的物理传输过程动力学复杂网络上的传播动力学问题是复杂网络研究的一个重要方向。主要研究社会和自然界中各种复杂网络的传播机理与动力学行为以及对这些行为高效可行的控制方法。复杂网络上的传播过程可以分为两类：不符合物质或能量守恒的过程以及符合物质或能量守恒的过程。首先介绍复杂网络上的流行病传播机理，接着介绍复杂网络的免疫策略，然后介绍复杂网络上的舆论传播，最后介绍复杂网络上的数据包传递机理和拥塞控制。6.1.1复杂网络上的流行病传播流行病传播的速度很快，对社会的影响非常大，引起全社会的极大关注，如网络病毒、人

2、类社会中的SARS、性病、艾滋病和谣言等等。在复杂网络上，最近的理论和实验都表明流行病的传播阈值与网络系统的尺寸(节点数)有着紧密联系。在复杂网络传播动力学的研究中，传播阈值c是理论和实验研究工作者特别关注的一个重要参量。对于尺寸非常大的网络系统而言，如果流行病的传播概率大于该传播阈值，那么受感染人数将占一个有限大小的比例，即传染病会爆发且持续地存在；否则，受感染人数会呈指数衰减，其占总人数的比例将接近于0，即传染病将会自然消失。流行病传播的基本模型需要采用不同的数学模型来表征不同的传播规律，它们是复杂网络传播动力学研究的基础。传播模型中的每一类个体都处于同一种状态。基本状态包括：易感状态(S

3、)，即健康的状态，但有可能被感染；感染状态(I)，即染病的状态，具有传染性；移除状态(R)，即感染后被治愈并获得了免疫力或感染后死亡的状态。处于移除状态的个体不具有传染性，也不会再次被感染，即不再对相应动力学行为产生任何影响，可以看作已经从系统中移除。 在真实系统中不同种类的传染病具有不同的传播方式， 研究它们的传播行为通常采用不同的传播模型SIS模型描述像感冒这类治愈后患者不能获得免疫力的疾病。此外计算机病毒也属于这一类型。个体分为两类：易感人群(S)和染病人群(I)。染病人群为传染的源头，它通过一定的概率把传染病传给易感人群。染病人群本身也有一定的概率u可以被治愈；易感人群一旦被感染，就又

4、变成了新的传染源。SIS模型的感染机制可以用下式表示：)()(),()()()(iSiIjIiIjIiSs(t)，i(t)分布标记群体中个体在时刻t处于S态和I态的密度，当易感人群和感染人群充分混合时，其动力学可以用下列微分方程组描述：此方程中存在一个阈值c=/，当c时其定态解为i(T)0，这里T为达到稳定态的时间。)()()()()()()()(titstidttdititstidttdsSIR模型适合描述那些染病者在治愈后可以获得终生免疫能力的疾病，如麻疹、腮腺炎、水痘、百日咳等，或者几乎不可避免走向死亡的疾病，如艾滋病等。人群分为三类：易感人群(S)、染病人群(I)和免疫人群(R)。不同

5、于SIS模型，这里染病人群将不再变为易感人群而是以概率u变成免疫人群。在每一个给定的时间，个体处于三态之一，其动力学方程如下：)()(),()()()(iRiIjIiIjIiS用s(t)，i(t)，r(t)分布标记群体处于S态、I态、R态的密度。当易感人群和染病人群充分混合时，SIR模型的动力学可以用下列微分方程组描述：随着时间进行，感染人数将逐步增加。经过充分长的时间后，因为易感个体的不足使得感染个体也开始减少，直至感染人数变为0，传染过程结束。因此，SIR模型在稳态时刻t=T的传染密度r(T)和有效传染率存在着一一对应的关系，且r(T)可以用来测量传染的有效率。当c时感染爆发。)()()(

6、)()()()()()(tidttdrtitstidttditstidttds其他模型SI模型用于描述那些染病后不可能治愈的疾病，或对于突然爆发尚缺乏有效控制的流行病，如黑死病及非典型肺炎。也就是说，在SI模型中，个体一旦被感染就会永久处于感染状态。SIRS模型适合于描述免疫期有限或者说免疫能力有限的疾病。与SIR模型不同的是，在SIRS模型中，处于移除状态的个体(治愈后具有免疫力)还会以概率失去免疫力。SEIR模型适合于描述具有潜伏态的疾病，如季节性感冒。与SIR模型不同，易感个体与感染个体接触后先以一定概率变为潜伏态(E)，然后再以一定概率变为感染态。均匀网中的流行病传播按照度分布，复杂网

7、络可以分为均匀网络和非均匀网网络。均匀网的度分布范围不大，在某一平均值附近且度分布指数衰减，如随机网络与小世界网络。对于均匀网络，其传播动力学通常可以由平均场或均匀混合方法给出。本小节介绍均匀网络中的流行病传播规律，分别基于SIS和SIR两种模型加以讨论。1 基于SIS模型的情形均匀网络中每个节点的度近似等于网络的平均度，即kk。对于SIS模型来说，在每一个时间步，如果网络中易感个体至少和一个感染个体相连，则它被感染的概率为；同时，感染个体被治愈变为易感个体的概率为。为了便于研究，这里对SIS模型作了两个假设：(1)均匀混合假设：有效传染率与系统中处于感染状态的个体的密度(t)成正比，即和都是

8、常数。(2)假设病毒的时间尺度远远小于个体的生命周期，从而不考虑个体的出生和自然死亡。令有效传染率(或叫有效传播率)，它是一个非常重要的参量。均匀网络中存在一个传播阈值c。当有效传播率大于c时，感染个体能够将病毒传播扩散，并使得整个网络中感染个体的总数最终稳定于某一平衡状态，网络此时处于激活相态(active phase)；当有效传播率小于c时，感染个体的数量呈指数衰减，无法大范围传播，网络此时处于吸收相态(absorbing phase)。所以在均匀网络中，存在一个正的传播阈值以将激活相态和吸收相态明确地分隔开。不失一般性，令1(这种做法只是改变演化时间的尺度)，利用平均场理论，均匀网络中被

9、感染个体的密度随时间的演化满足如下方程：式中第一项表示感染个体以单位速率减少(因为假设概率1)，第二项表示单个感染个体产生的新感染个体的平均密度，它与有效传播率、节点(个体)的平均度k及感染节点与易感节点连接的概率(t)1-(t)成正比。式中，为感染个体的稳态密度。可以解得，均匀网络流行病传播的阈值为：d( )( )( )1( )dttkttt 1(1)0k 1ck而且满足由此可见，传播阈值与平均度成反比。这很好理解，因为接触的人越多，被感染的几率就越大，故降低平均度是控制传染病传播的一个有效手段。0ccc2.基于SIR模型的情形对于SIR模型来说，处于易感状态、感染状态和移除状态的个体的密度

10、s(t)、i(t)和r(t)满足如下约束条件：同样令，1(这种做法只是改变演化时间的尺度)，在与SIS模型相同的假设条件下，易感个体、感染个体和免疫个体(处于移除状态的个体)的密度满足：不同于SIS模型，这里传染效率是以最终感染人口r(t趋于无穷大时r(t)的值)来衡量的。( )( )( )1s ti tr td ( )( ) ( )dd ( )( ) ( )( )dd ( )( )ds tki t s tti tki t s ti ttr ti tt 当c时，r在非常大的人口极限下为无穷小；而当c时，疾病传播并感染有限比例的人群。在初始条件r(0)0与s(0)1下，由上式容易得到：将此结果与

11、约束条件式相结合，可得到总感染人数满足下列自治方程：为了得到非零解，必须满足下列条件：这个条件等价于限制c，其阈值在这个特殊情形下取ck-1。在c处进行泰勒展开，可得传染效率为：上面两种模型讨论可见：对于均匀网络，有效传染率存在一个大于零的临界值，当有效传染率大于传播阈值时，疾病可以在网络中传播，并可以持久的存在，当有效传染率小于传播阈值，疾病则在网络中消亡。( )( )k r ts te 1k rre 0d(1)1dk rrer ()cr 非均匀网中的流行病传播在无标度网络中，无论流行病的传染性是多么弱，流行病仍然能够爆发并且持续的存在。在无标度网络中，由于度分布满足幂律分布，一个随机选取的

12、节点倾向于连接关键节点或连接度大的节点，因此度大的节点就容易感染，然后作为种子去感染其他人，从而导致比均匀网络上更快的流行病传播。为了刻画网络拓扑对流行病传播的影响，通常将节点按照度来分组，相同度的节点成为一组。本小节分别基于SIS模型和SIR模型两种情形介绍非均匀网络中的流行病传播规律。1 基于SIS模型的情形设k(t)表示t时刻度为k的节点组中感染节点的密度，则它满足如下微分方程：式中第一项为湮灭项，感染群体以单位速率减少(假设概率1)；第二项为产生项，它正比于有效传播率、易感人群的密度1-k(t)、节点的度k以及任意邻居被感染的概率。其中，任意邻居被感染的概率记作(t)，它表示从一个度为

13、k的节点连到度为任意k的节点的联合概率p(k|k)k(t)的平均。从而上式可重新描述为：d( )( )1( )(| )( )dkkkkkttktP kktt d( )( )1( ) ( ( )dkkkttkttt 设k为度为k的节点组中感染个体的稳态密度。显然，k只是的函数，因而稳态时相应地概率也变为的隐函数。利用稳态条件 可得： (*)对于非关联网络，概率P(kk)满足：则()可以写成如下自治方程：利用上式，容易求得()，再代入(*)式可以解得k。最终的感染个体稳态密度则可由下式估算：另外，由自治方程可得： (*)( )0ktt( )1( )kkk( )(| )k P kP kkk21( )

14、 ( )( )(| )1( )kkkk P kP kkkk 21( )( )101( )kk P kkk显然，该式存在一个平凡解()0。如果要使该方程存在一个非平凡解，必须满足：即于是，可求得非均匀网上SIS传播模型的阈值为：对该阈值可理解如下：当c，若(*)式中()0，则由()0可知：故式(*)的第二项肯定大于0，故当c时只有()0才能使( * )式成立。所以，只有当c时，才能由第二项得到不为0的()。20d1( )1d1kk P kkk 2( )1kk P kk2221( )1( )1( )11( )1/( )1/kkkck P kk P kk P kkkkkk对于规模无限大的具有度分布P

15、(k)k-(3)的网络，k2=，对应的c=0。由此可见，在无标度网络中，无论传染概率多么小，流行病都能持久存在，这个结果很好地解释了为什么病毒与舆论可以在Internet与社会网络中传播的如此快。2. 基于SIR模型的情形假设一个度为k的节点组中处于易感状态、感染状态和移除状态的个体的密度分别表示为sk(t)、ik(t)和rk(t)，则它们满足约束关系：与SIS模型分析类似，令 ，可以得到下列动力学演化方程：( )(| ) ( )kktP kk it( )( )( )1kkks ti tr td( )( ) ( )dd ( )( ) ( )( )dd( )( )dkkkkkkks tks tt

16、ti tks tti ttr ti tt 上述方程组初始条件为rk(0)=0、ik(0)=i0和sk(0)=1-i0。在极限i00时，我们可取ik(0)0，sk(0)1。在该近似条件下，由演化方程的第一个方程可得：其中， 为如下的辅助函数(考虑演化方程的第三个方程)：其导数可简化为：由此我们得到了关于 的一个自治方程，它在给定的P(k)条件下可以求解。一旦得到 ，就可以得到 ，从而由 可得：01( )( )d( ) ( )tkktttkP k r tk( )d ( )11( ) ( )( )(1( )( )d11( )( )kkkkkktktkP k i tkP kr ts ttkktkP k

17、 ek lim ( )tt( ) t( )1( )kkrs ( )(1)kkrP ke ( ) t由于 得到 ，从而可以得到关于 的自治方程：为了得到非平凡解(非零解)，必须满足如下条件：于是从而得到阈值为这个结果与SIS模型完全相同。( )0ki d ( )lim0dttt11( )kkP k ek 0d1(1( )1dkkP k ek 21( )()1kkP kkkk2ckk在SIS传播模型下，比较在相同平均度条件下WS小世界网络与BA无标度网络的传播规律(传染率和感染个体的稳态密度的关系)，如下图所示。 WS小世界网络和BA无标度网络的传播规律比较BA无标度网络的参数m=3，其平均度为2

18、m等于6，取WS小世界网络的参数k=6。可见，BA网络的传染率连续而平滑地过渡到0，说明无标度网络不存在正传播阈值。对于BA网络，只要传染率大于0，病毒都能传播并最终维持在一个稳定态，这也反映了BA网络对病毒传播的脆弱性。几种网络传播临界值比较群落网结构对流行病传播的影响社团结构一般都具有群落结构，群落可以由同事、朋友、同学或俱乐部成员等组成。在社会网络中，各群落内部成员联系紧密；相反，在不同群落之间则联系较少。群落网络的结构示意图如图所示。群落结构的存在必然影响流行病的传播。本小节重点探讨群落结构对流行病传播的影响。 含三个社团的社团网络结构示意图(社团内实线连接，社团间虚线连接)社会网络通

19、常具备高的集聚系数，群落内的连线密度高，而群落间的连线密度低。假设我们将产生一个含有N个节点、m个组的群落网模型，提出如下简单方法来构造群落网络： 步骤1：初始化。将N个节点随机分成m个组，每组内的节点数为ni(i=1，2，m)，即 步骤2：群落内连线。每个组内的节点间以概率p连线，从而组i内的连线数为 。步骤3：群落间连线。任意两个组间的节点间以概率q连线，从而组i和组j间的连线数为 。通过上述构造方法，最终得到的网络总边数为 1miiNn0.5 (1)iin npijnn q111(1)2mmmiiijiij iMn npnn q令序参量=pq表示群落化的程度，则对于群落网络应该有。如果=

20、1，则上述方法得到的网络将退化为一般的随机网络。如果给定总边数M、总节点数N及群落划分方案和序参量，则概率p和q可由下式给定：11111(1)21(1)2mmmiiijiij immmiiijiij iMpn nnnMqn nnn社团网络上的流行病传播用SIS模型来讨论流行病在群落网中的传播规律。假定易感个体以概率与每个周围的感染个体接触。若节点vj处于易感状态且有kj个邻居，它们中有kinf个处于感染状态，则在每个时间步，节点vj将以概率 变为感染状态。同时每个感染节点以概率变为易感状态。同前面的讨论一样，为简单起见，这里令=，=1。假定初始时有一粒种子，则它的每个邻居将以的概率被感染，然后

21、再感染它们的邻居。一定时间后，感染达到稳态。对于c，稳态为0；而对于c，稳态为非零。由于群落网络的非均匀结构，最终的状态依赖于选取的种子及网络构型，因此有意义的结果必须为对各种网络构型及各种初始条件的平均。对具有的群落网，当较小时，传播会限制在种子所在的群落内。从统计意义上看，可以认为种子被均匀选取在每个社团。对于每个特定的群落i，其阈值c(i)由其平均连线数决定。当群落间的连线远小于群落内的连线时，有且此关系对所有的种子成立。整个系统的c为不同构型及不同实现的平均，即对不同的种子平均，因此c与p间的定量关系为c1p。( )1/1/ (1)1/iciikp np其中a为一常数。因此c与M成反比

22、。对于给定的M，上式可被写为：这就是c对群落程度的依赖关系。随着群落度的降低，流行病的传播阈值将增加并在随机网时达到极大值。换句话说，流行病在随机网上比在群落网上更不容易爆发。通过前面的讨论，还可以得到一个结论：传染病本身的动力学性质和个体所在的网络结构共同决定了流行病的传染行为和传染过程。1(1)caM1( )( )cc 无标度网络是很容易受到病毒感染而导致病毒流行的，因此选择合适的免疫策略显得非常重要。人们针对免疫策略作了较多的研究，通常根据节点在网络中的地位(例如以节点的度来衡量)来关注节点的选择。下面简要介绍复杂网络的三种免疫策略：随机免疫、目标免疫和熟人免疫。随机免疫完全随机地选取网

23、络中的一部分节点进行免疫。免疫节点不会再被感染，所以它们不会再影响它们的邻居。 针对均匀网络，容易得出随机免疫的免疫临界值为： 对于无标度网络来说，推导，可以得到此时随机免疫的免疫临界值gc为显然，随着网络规模的无限增长，无标度网络的k2，其传播阈值c趋于0，而免疫临界值gc趋于1。这表明，如果对于无标度网络采取随机免疫策略，则需要对网络几乎所有节点都实施免疫才能保证最终消灭病毒传染。1ccg 211ckgk 目标免疫根据无标度网络的不均匀特性，选取少量度最大的节点进行免疫。就BA无标度网络而言，目标免疫对应的免疫临界值为：上式表明，即使传染率在很大的范围内取不同的值，都可以得到很小的免疫临界

24、值。因此，有选择地对无标度网络进行目标免疫，其临界值要比随机免疫小得多。2mcge 对BA无标度网络采取随机免疫和目标免疫的对比上图横坐标为免疫密度g，纵坐标为g/0，0表示网络未加免疫的稳态感染密度，g为网络中加入比例为g的免疫节点后的稳态感染密度。可以看出，随机免疫和目标免疫在无标度网络中存在着明显的临界值差别。在随机免疫情况下，随着免疫密度g的增大，最终的被感染程度下降缓慢，只有当g=1时，才能使被感染数为零。而在目标免疫的情况下，gc0.16，这意味着只要对少量度很大节点进行免疫，就能消除无标度网络中的病毒扩散。熟人免疫:对随机选出的节点的邻居进行免疫，该策略基本思想是：从N个节点中随

25、机选出比例为s的节点，再从每一个被选出的节点中随机选择它的某个邻居节点进行免疫。 无标度网络中免疫临界值随幂律指数的变化情况10.80.60.40.2022.533.5gc复杂网络上的舆论演化动力学 舆论及其特性舆论是由许许多多的社会个体的意见相互作用而形成的，其发展变化受到自然、社会、经济、文化、政治、法律等各种因素的影响，它的演化过程具有：复杂性开放性不确定性非平衡性自组织性等特性。协议是社会群体中非常重要的方面之一，每天的日常生活都需要人们达到共识，而协议使得组织更协调有效并可以扩展在社会上的影响力。舆论传播的动力学行为也服从SIR模型。但是它的三种状态和流行病中的三种状态S、I、R代表

26、：不知道消息的人群，知道消息的并有能力继续传播消息的人群，及知道消息但已经失去传播能力或兴趣的人群。假设网络上有N个节点，每个节点代表一个可传播消息的个人，他们传播消息的行为方式如下：如果得到了一个消息(I态)，那么他就有兴趣把这个消息传播出去，在传播过程中，他将随机地从邻居中选取一人并将消息传给他，如果这个邻居不知道这个消息(S态)，则该邻居就得到此消息(I态)，并进行下一轮的传播。但如果他的邻居已经知道了这个消息，那么传播消息的人会认为该消息失去了继续传播的价值，并失去传播该消息的兴趣(R态)。整个过程可由以下关系简单地表示出来：假设在一个有限网络中所有的节点都处于S态，在某一时刻突然有一

27、个节点得到了一个新的消息，它将成为I态。那么按照上面所定义的规则，这个消息将在网络中传播，直到最终网络中没有I态的节点为止。称这个状态为终态。对于相同平均度的网络，无标度网比随机网络具有更多度大的节点，因此无标度网中的消息可较容易的传递给大节点然后再到其他节点。一旦大节点处于I态或R态，其他节点因为以较大概率连接到它们，从而更容易变成R态；而随机网则没有这个特点。因此，舆论在无标度网络上的传播要比在随机网络上结束得快，从而导致无标度网的总感染密度比随机网的小。( )( )( )( )( )( )( )( )( )( )( )( )I iS jI iI jI iI jR iI jI iR jR

28、iR j网络的同步早在三百多年前，物理学家惠更斯在给父亲的信里提到他卧病在床的几天中惊奇的发现，挂在同一个横梁上的两个钟摆在一段时间以后会出现同步的摆动现象。这种现象发生的原因是它们通过悬挂其上的横粱相互作用。除了这种两个个体相互作用产生的同步现象之外，很多重要的同步现象出现在多体系统中。随着对复杂网络研究的深入，复杂网络上的同步问题开始被广泛关注。考虑一个耦合动力学系统，其拓扑结构是一个复杂网络。系统中的各个节点在与外界孤立时，其演化方式是混沌的。初始时刻，各个点的状态随机分布，各不相同，经过一段时间的过渡之后，各点的状态可能会趋于相同，达到同步态。人们研究的重点是：网络的拓扑结构是如何影响

29、其同步能力的。主要介绍多种不同混沌同步方式的定义，包括完全同步、广义同步、相位同步和滞后同步等。混沌同步的定义通俗的讲，同步是指两个或多个系统，在外部驱动或者相互耦合的作用下。调整它们的某个动态性质以达到具有相同性质的过程。所谓混沌同步，指的是对于从不同的初始条件出发的两个混沌系统，随着时间的推移，它们的轨迹逐渐一致。一组动力单元(全同或者不全同)，通过一定的相互作用或者外界的驱动，使得它们的某种运动性质趋于相同，我们就说这组单元达到了同步。同步广泛存在于自然界和社会生活中，常见的同步的例子有：惠更斯摆、萤火虫的同步发光、蛙的齐鸣、心肌细胞和大脑神网络的同步，以及众人长时间鼓掌导致掌声频率趋于

30、同步。(精确)同步：两个或多个动力学系统，除了自身的演化外，其间还有相互作用（耦合），这种作用既可以是单向的，也可以是双向的。当满足一定条件时，在耦合的影响下，这些系统的状态输出就会逐渐趋同进而完全相等，称为同步（精确同步）。 广义的同步还包括相同步和频率同步等等。复杂系统中的同步主要有两大类：完全同步和广义同步，前者两个相同单元研究得比较多，两个不同单元研究得比较少；后者包括部分同步，如相同步、滞后同步、频率同步等。对于系统其中，X（x1，x2，.，xn）TRn，Y（y1，y2，.，ym）TRm。系统的轨道关于性质gx 和gy 同步，如存在与时间无关映射h：RnRmRk，使得对于上述的统一定

31、义，根据X 和Y 的不同情况可以给出四种不同同步的相应定义：完全同步、相位同步、滞后同步和广义同步。完全同步：两个耦合的相同系统，随着时间的演化，若同步表现为两个系统的状态变量完全相等，我们称之为完全同步。相位同步：混沌运动是被限制在某一局域的振荡运动，对着这种运动，人们可以从相位和振幅两个侧面来描述系统的状态。1996年，Rosenblum等人发现了一种相同步，即耦合的混沌振子在一定的条件下，其相位会达到同步，但其振幅几乎没有关联。若系统（5.18）的解为振荡型的，它们具有相位x 和y，称两个子系统达到相位同步，如果存在两个正整数p、q，使得其中 是一个很小的正数。滞后同步：对于系统，称其两

32、个子系统达到滞后同步（延时同步），需要满足mn，且存在与时间无关的常数，使得广义同步：对于不全同的系统在一定的条件下驱动系统和响应系统间存在的关系，对于系统，称其两个子系统达到关于性质h 广义同步，如果存在连续映射h： 。使得针对线性耦合网络上的同步问题，Pecora和Carroll提出了主稳定函数判据。他们首先假设：(1)所有的耦合振子都是完全相同的，(2)从每个振子提取的用于耦合其它振子的函数也是完全相同的，(3)同步流形是不变流形，(4)节点的耦合方式使在同步流形附近系统可以线性化。假设(1)和(3)是为了保证相空间中同步超平面的存在，假设(2)是为了使动力学系统和网络结构的稳定性图象更

33、加清晰具体，假设(4)是为了更好地应用线性近似这一研究耦合系统最常用的方法。在此基础上，Pecora和Carroll完成了耦合振子系统的同步稳定性分析，提出用主稳定性函数方法确定动力学网络同步的稳定性。下面我们介绍主稳定性函数的定义及其使用方法。考虑一个由N个全同节点构成的复杂网络。令m维矢量Xi代表节点i状态，单个节点(与外界孤立)的动力学为:网络中第i个节点的动力学为：其中，为耦合强度，H：RmRm是一个任意的耦合函数，G为网络的耦合系数矩阵Gij。矩阵G满足 ，保证了假设(3)能够满足，即系统存在不变的同步流形x1=x2=.=xN。我们关心的问题是：系统能否稳定的处于同步态。)(iixF

34、x jjjiiixHGxFx)()(,0ijjG定义1：设f是从集合I 到其自身的一个映射，对任意的xI，记f(0)(x)x，f(n)(x)f(f(n-1)(x)，称f(n)(x)为f(x)的n次迭代。若f是拓扑空间I上的连续自映射，称序列f(n)(x)：nN是由f迭代生成的离散拓扑半动力系统。若f是紧致度量空间I上的连续自映射，则称离散拓扑半动力系统f为紧致系统。在众多的混沌定义中，LiYorke 的混沌定义是比较公认的和影响较大的。1975 年，Li 和Yorke 从区间映射出发给出了混沌的一个数学定义，这也是第一次赋予混沌这个词以严格的科学定义。该定义如下：定义5.2：设I 为R 上的一

35、个闭区间，对于连续自映射f：II，假设存在点xI，使得f(3)（x）xf（x）f(2)（x）或者f(3)（x）xf（x）f(2)（x）。如果：（1）f 的周期点的周期无上界：f 具有任意正整数周期的周期点，即对任意自然数n，有xI，使f(n)（x）x（非不动点的n 周期点）。（2）闭区间I 上存在不可数子集S I，满足：（i）对x，yS，当xy时有（ii）对x，yS有（iii）对xS和f的任一周期点y，有则称f 在S 上为混沌的。LiYorke定义用三个本质特征来刻划混沌：“有界”、“非周期”和“初始条件敏感”。定义中的（1）是Sarkovskii定理的特例，存在所有正整数周期，就足以说明系统是相当复杂的。满足（2）的不可数集S（不可数集是一种无穷集合，它和整数集之间不存在一个双射），称为混沌集，其中的条件（i）和（ii）是本质的，反映了轨道结构的复杂特征。条件（iii）说明了S中无渐进周期点，但这个结论不是独立的，实际上已经蕴涵在（i）和（ii）中