复杂网络入门必读

LOGO复杂网络—2010年度讨论班王淑栋山东科技大学办公室：J13-409电话：88032786（H），15269283087Email：[e-mail]2020/3/3LOGO2报告内容第一讲.引言王淑栋第二讲.复杂网络的基本模型李凯凯第三讲.复杂网络中的搜索杨梅茜第四讲.网络同步许秀竹第五讲.复杂网络的相继故障孙龙霄第六讲.复杂网络控制张玉林第七讲.网络演化动力学王淑栋第八讲.加权网络李凯凯第九讲.复杂网络的社团结构杨梅茜第十讲.网络传播动力学张玉林LOGO复杂网络研究的著作与综述汪小帆,李翔,陈关荣.复杂网络理论及其应用.清华大学出版社,2006年.许晓鸣,郭雷.复杂网络.上海科技教育出版社,2006年11月.S.H.Strogatz.Nature,410,(2001)268.R.Albert,A.-L.Barabasi.Rev.Mod.Phys.,51(2002)1079.M.E.J.Newman.SIAMRev.,45(2003),167.S.N.Dorogovtesev,J.Mendes.EvolvingofNetworks,OxfordUn.Press,2003.E.Ben-Naim,etal.ComplexNetworks,Springer,2004.S.Boccaletti,etal.ComplexNetworks:Structureanddynamics,Phys.Rep.424(2006)175-308.Newman,Barabasi,Watts.TheStructureandDynamicsofNetworks.PrincetonUniversityPress,2006.3LOGO4第一讲、引言LOGO51.二十一世纪涌现的新现象万维网万维网是怎样“链”接的？从一个页面到另一个页面平均需要点击多少次鼠标？一、为什么研究复杂网络？LOGO6美国航空网城市公共交通网为什么两者结构差异如此之大？这种差异是必然还是偶然的？城市交通涌堵的原因是什么？LOGO7非典发现在广州，为什么却在北京爆发呢？传染病是怎样扩散和消失的？计算机病毒是怎样传播的？为什么“好事不出门，坏事行千里”呢？……互联网LOGO82.二十一世纪科学研究的特点二十世纪，科学研究的特点是分析的方法，还原论的方法：物理学（牛顿力学、量子力学、电子论、半导体），化学（量子分子论），生物（双螺旋结构）；建筑工程（应力应变分析），……。二十一世纪（二十世纪末），系统成为主要的研究对象，整合成为主要方法。普列高津的耗散结构理论，哈肯的协同学，混沌和复杂系统理论，系统生物学……。LOGO9美国《Science》周刊：“如果对当前流行的、时髦的关键词进行一番分析，那么人们会发现，“系统”高居在排行榜上。”当分析为主要的研究方法时，人类关注如何将系统“分析”、“分解”，揭开系统的细部，了解是什么元素或部件组成了系统，却忽视或破坏了这些元素是如何组合成系统的。而整合的方法在于了解细部以后，研究“如何组合”的问题。这种方法导致复杂网络结构的研究。LOGO二、复杂系统与复杂网络101.复杂系统与复杂网络的概念（1）什么是系统？系统：集合（具体元素）+结构+功能。（例：不同角度分析系统，人）（2）系统的结构是什么？一切系统的基础结构都是网络；一切系统的核心结构都是逻辑网络；复杂系统的结构就是复杂网络。LOGO11复杂网络是构成复杂系统的基本结构，每个复杂系统都可以看作是单元或个体之间的相互作用网络；复杂网络在刻画复杂性方面的重要性是由于结构决定功能的。复杂网络是研究复杂系统的一种角度和方法，它关注系统中因子相互关联作用的拓扑结构，是理解复杂系统性质和功能的基础。LOGO我认为，下个世纪将是复杂性的世纪(Ithinkthenextcenturywillbethecenturyofcomplexity)——斯蒂芬.霍金(StephenHaking)（2000）英国剑桥大学应用数学及理论物理学系教授，当代最重要的广义相对论和宇宙论家，是当今享有国际盛誉的伟人之一，被称为在世的最伟大的科学家，还被称为“宇宙之王”。网络与复杂网络成为二十一世纪的新科学领域！LOGO1)开放性。即与环境和其它系统进行相互作用，交换物质、能量、信息，保持和发展系统内部的有序性与结构稳定性。在这种交换中，系统经历着从低级向高级、从简单到复杂、从无序向有序的不断优化的动态发展过程。虽然开放性是所有真实系统的基本属性，但这里的开放非指一般意义上的相互作用与交流，而开放的度量、性质、强度对复杂系统的性态、演化具有决定性的意义。例子，人，城市网络簇。２)涌现性。即内部元素通过非线性相互作用，在宏观层次上产生出新的、元素不具有的整体属性，表现为整体斑图、模式等。虽然涌现同样是所有系统都具有的，但这里涌现意味着新的整体属性的产生。例子，“整体大于部分之和”，大脑的神经网络系统132.复杂系统与复杂网络的主要特性：LOGO14３）演化性（不可逆性）。即通过与所在环境中的其它系统的相互作用和内部的自组织，使系统发展到新的阶段，表现出阶段性、临界性，完成系统演化的生命周期。例:社会网络中的人，生物群体的自组织系统（鸟群）４）复杂性。包括系统的结构、行为、功能等多个方面同时具有的复杂性。结构复杂性表现为多元性，非对称性，非均匀性，非线性（分岔(Bifurcation),混沌(Chaos),分形Fractal）；行为复杂性表现为学习，自适应性，混沌同步，混沌边沿，随机性等等；认识复杂性又称为主观复杂性，它表现为不确定性，描述复杂性与计算复杂性等等。例:神经网络中的突触有强有弱，可抑制也可兴奋LOGO５）网络结构。即系统内部和系统之间的相互作用可以看成由节点、边（连接）构成的体系，出现网络复杂性、小世界特征与无标度特征等。15一切系统都具有网络结构，复杂系统具有复杂的网络结构。LOGO163.网络系统的复杂性（1）结构复杂性网络连接结构错综复杂、极其混乱，同时又蕴含着丰富的结构：社区、基序、聚集性、生成规律性等等，而且网络连接结构可能是随时间变化的，例如，上每天都不停地有页面和链接的产生和删除。静态结构的复杂性和结构动态演化的复杂性。例：神经系统由神经元互连形成，连接以“突触连接结构”实现，突触有强弱、兴奋与抑制、不同的神经递质；连接不断改变，形成连接结构变化。（重边，加权等）LOGO17（2）节点复杂性A）节点的独立或固有特性网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统。例如，基因网络中每个节点都具有复杂的时间演化行为。而且，一个网络中可能存在多种不同类型的节点。例如，控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。B)关联引发的节点特性当关联失去时这类特性会在节点处消失或改变。例如，耦合神经元重复地被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。LOGO18（3）复杂网络之间相互影响的复杂性实际的复杂网络会受到各种各样因素的影响和作用。例如，电力网络故障会导致Internet网速变慢，运输系统失控等一系列不同网络间的连锁反应。（4）网络分层结构的复杂性例如，行政管理网络是具有层结构的，多数网络都有节点的分层结构，只是在许多网络中没有意识到是一种造成复杂性的重要结构。LOGO19复杂网络也是研究复杂系统的一种技术和方法，它关注系统中个体相互作用的拓扑结构，是理解复杂系统性质和功能的基本方法。复杂网络是二十一世纪科学研究的思想和理念，它启发我们用什么观点理解这个世界：整个世界以及组成世界的任何细部都是由网络及其变化形成的。LOGO20三、复杂网络研究简史①格尼斯堡七桥问题Euler（1707~1783），瑞士数学家，图论之父一笔画问题1736年，七桥游戏LOGO21②随机图理论20世纪60年代，由两位匈牙利数学家Erdǒs和Rényi建立的随机图理论（randomgraphtheory）被公认为是在数学上开创了复杂网络理论的系统性研究。Erdǒs和Rényi的最重要的发现是：ER随机图的许多重要性质都是突然涌现的。也就是说，对于任一给定的概率p，要么几乎每一个图都具有某个性质Q（比如说，连通性），要么几乎每一个图都不具有该性质。在20世纪的后40年中，随机图理论一直是研究复杂网络的基本理论。LOGO22③小世界实验20世纪60年代美国哈佛大学的社会心理学家StanleyMilgram通过一些社会调查后给出的推断是：地球上任意两个人之间的平均距离是6。这就是著名的“六度分离”（sixdegreesofseparation）推断。为了检验“六度分离”的正确性，小世界实验—Bacon数。美国Virginia大学计算机系的科学家建立了一个电影演员的数据库，放在网上供人们随意查询。网站的数据库里目前总共存有近60万个世界各地的演员的信息以及近30万部电影信息。通过简单地输入演员名字就可以知道这个演员的Bacon数。一个有趣的数学家故事：Erdǒs数证明小世界实验。LOGO23③小世界实验20世纪60年代美国哈佛大学的社会心理学家StanleyMilgram通过一些社会调查后给出的推断是：地球上任意两个人之间的平均距离是6。这就是著名的“六度分离”（sixdegreesofseparation）推断。为了检验“六度分离”的正确性，小世界实验—Bacon数。美国Virginia大学计算机系的科学家建立了一个电影演员的数据库，放在网上供人们随意查询。网站的数据库里目前总共存有近60万个世界各地的演员的信息以及近30万部电影信息。通过简单地输入演员名字就可以知道这个演员的Bacon数。一个有趣的数学家故事：Erdǒs数证明小世界实验。LOGO24有两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志：一篇是美国康奈尔（Cornell）大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的题为《“小世界”网络的集体动力学》（CollectiveDynamicsof‘Small-World’Networks）的文章；另一篇是美国NotreDame大学物理系的Barabāsi教授及其博士生Albert于1999年10月在Science杂志上发表的题为《随机网络中标度的涌现》（EmergenceofScalinginRandomNetworks）的文章。这两篇文章分别揭示了复杂网络的小世界特征和无标度性质，并建立了相应的模型以阐述这些特性的产生机理。LOGO251998，Watts和Strogatz：WS小世界网络D.J.Watts,andS.H.Strogatz,Nature,393,440-442(1998).LOGO26A.-L.BarabasiandR.Albert,Science,286,509(1999).1999，Barabasi和Albert：BA无标度网络kkP)(LOGO27复杂网络研究的简史列表时间（年）人物事件173619591967197319981999EülerErdǒs和RényiMilgramGranovetterWatts和StrogatzBarabási和Albert七桥问题随机图理论小世界实验弱连接的强度小世界模型无标度网络LOGO技术网络28不同领域的复杂网络社会网：演员合作网，友谊网，姻亲关系网，科研合作网，Email网生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络信息网络：，专利使用，论文引用，计算机共享技术网络：电力网，Inter