复杂网络研究-2011最新版-狄增如

复杂网络研究——现状与前瞻狄增如北京师范大学管理学院系统科学系北京师范大学复杂性研究中心北京大学---2011.4SimpleComplicatedComplexSystemComplexSystemsComplexSystemsComplexsystemsareallaroundus:–􀂅economies–􀂅nature:ant,bee,birdcolonies–􀂅littlerobotsComplexsystemsOften-citedexamplesofcomplexsystemsinnatureandsocietyinclude大脑、免疫系统、细胞、新陈代谢网络、昆虫社会、万维网、市场、社会网络.Thereisnogenerallyacceptedformaldefinitionof“complexsystem”.Informally,acomplexsystemisalargenetworkofrelativelysimplecomponentswithnocentralcontrol,inwhichemergentcomplexbehaviorisexhibited.生物系统社会经济系统ComplexityResearch——UnderstandingandEngineeringEmergenceComplexsystemshavemanyautonomousunitswithadaptivecapabilities,andshowimportantemergentphenomena.Oneofthegreatestchallengesinbuildingascienceofsuchsystemsispreciselytounderstand–howitisthatmicrolevelpropertiesdetermineoratleastinfluencethoseonthemacrolevel.Ourcurrentlackofunderstandingpresentsahugeobstacleindesigningsystemswithspecifiedbehavior–todesigntheunitsofasystem,theirinteractionsandadaptivefeatures,soastoachieveatargetedbehaviorfromthewhole.系统科学《1999科学发展报告》系统科学是自然科学与社会科学的基础学科。它关心涉及复杂系统性质和演化规律的基本科学问题，试图通过对生命、生态、信息技术、资源环境、社会经济等具体系统演化过程中关键问题的研究，揭示复杂系统所具有的一般性规律，研究复杂系统宏观层次上的涌现性行为、系统性质和功能的智能控制等科学问题，并促进对具体系统的认识。SystemsScienceToProvideaSystematic(Unified,Universal)ViewforVariesComplexSystemsbyaSystematicApproach.SystemsScience——Fromcomponentstoglobalpropertiesbridgesthegap–betweentheindividualandthecollective–frompsychologytosociology–fromorganismtoecosystems–fromgenestoproteinnetworks–fromatomstomaterials–fromthePCtotheWorldWideWeb–fromcitizenstosocieties.FundamentalQuestionsofSystemsScience认识系统–reconstructingandpredictingmultilevelbehavior–fromlocaltoglobal设计与控制系统–thedesign,controlandmanagementofcomplexsystemsComplexSystems——BeyoundReductionism,SCIENCEVOL79,2Apirl1999ExploringtheSystemsofLifeBuildingWorkingCells“inSilico”ComplexityandtheEconomyComplexityandClimateComplexityandtheNervousSystemComplexityinBiologicalSignalingSystemSimpleLessonsfromComplexityComplexSystemsandNetworks,SCIENCEVOL32524JULY2009RevisitingtheFoundationsofNetworkAnalysisDisentanglingtheWebofLifeAnalyzingSustainabilityofSocial-EcologicalSystemsEconomicNetworksPredictingtheBehavorofTechno-SocialSystems–Underlyingconnectivityhassuchastrongimpactonasystem’sbehaviorthatnoapproachtocomplexsystemscansucceedunlessitexploitsthenetworktopology.LivingRoadmapforComplexSystems复杂系统研究路线图toguideEuropeanResearchoncomplexsystemsfrom2007-2013GroundChallenges–onNaturalComplexSystems–intheunderstandingandmanagementoftheEarthSystem–ofSocietyinanEpochofGlobalization–inDesignandtheSciencesoftheArtificial–InformationCommunicationTechnologies关于复杂性我们所关心的问题：–大量个体（更典型的是具有适应性的主体）所组成的复杂系统，在没有中心控制、非完全信息、仅仅存在局域相互作用的条件下，通过个体之间的非线性相互作用，可以在宏观层次上涌现出一定的结构和功能。Internet全局相互作用晶格相互作用与复杂性扩散平均场?•复杂系统不能够用分析的方法去研究，必须考虑个体之间的关联和作用；•理解复杂系统的行为应该从理解系统相互作用网络的拓扑结构开始；•网络拓扑结构的信息是构建系统模型、研究系统性质和功能的基础。为什么研究复杂网络？复杂网络是研究复杂系统的一种角度和方法，它关注系统中个体相互关联的作用的拓扑结构，是理解复杂系统性质和功能的基础。为什么研究复杂网络？技术网络电力网因特网社会网络朋友关系网性关系网科学引文网演员网科学家合著网交通运输网络航空网道路交通网城市公共交通网生物网络神经网络基因网络蛋白质相互作用网络生态网络新陈代谢网络生命金字塔不同领域的复杂网络社会网：演员合作网，友谊网，姻亲关系网，科研合作网，Email网生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络信息网络：，专利使用，论文引用，计算机共享技术网络：电力网，Internet，电话线路网，交通运输网：航线网，铁路网，公路网，自然河流网网络研究的历史1736，欧拉：哥尼斯堡七桥1950，Erdos,Renyi:随机图论1998，Strogatz,Barabasi:小世界和无标度网络为什么现在才开始研究复杂网络？计算机技术的发展：–使我们拥有各种网络的数据库，并有可能对大规模的网络进行实证研究普适性的发现：–许多实际网络具有相同的定性性质–且已有的理论不能描述和解释理论研究的发展–小世界网络(SmallWorldNetwork),无标度网络(Scale-freeNetwork)–统计物理学的研究手段复杂网络研究所关心的问题–如何定量刻画复杂网络？网络结构的描述及其性质–网络是如何发展成现在这种结构的？网络演化模型–网络特定结构的后果是什么？网络结构的鲁棒性网络上的动力学行为和过程复杂网络的结构四种结构模型：–规则网络–随机网络–小世界网络–无标度网络对网络结构的描述几何量及其分布度（Degree）：朋友的个数集聚系数（群系数）（Clusteringcoefficient）：朋友的朋友还是不是朋友的情况最短路径（Shortestpath）：两个顶点之间边数最少的路径介数（Betweenness）：经过我的最短路径的条数一个简单的例子K●=5C●=0K●=5C●=1规则网络一般情况下，聚集系数较大，平均最短路径较长。ER随机网络当p不太小时，聚集系数较小，平均最短路径较短。随机网络的平均最短路径及其与实证数据的比较kNllnlnrand随机网络的平均聚集系数及其与实证数据的比较NkpCrandSmallWorldNetworkC(p):平均聚集系数L(p):平均最短路径度分布!!)()(kkekpNekPkkkpN分布函数f(k)：–网络中度值为k的顶点占总点数的比例–随机网络的度分布——Poisson分布10000个顶点p=0.0015度分布幂律分布——PowerLawkkP)(kkPln)(ln=-3WorldWideWeb800milliondocuments(S.Lawrence,1999)Nodes:~109N(k=500)~103P(k=500)~10-6INTERNETBACKBONE(Faloutsos,FaloutsosandFaloutsos,1999)Nodes:computers,routersLinks:physicallinesNodes:actorsLinks:castjointlyN=212,250actorsk=28.78P(k)~k-=2.3ACTORCONNECTIVITIESSCIENCECITATIONINDEXNodes:papersLinks:citations1736PRLpapers(1988)Nodes:scientist(authors)Links:writepapertogether(Newman,2000,H.Jeongetal2001)SCIENCECOAUTHORSHIPSex-webNodes:people(Females;Males)Links:sexualrelationshipsLiljerosetal.Nature20014781Swedes;18-74;59%responserate.MetabolicnetworkOrganismsfromallthreedomainsoflifearescale-freenetworks!H.Jeong,B.Tombor,R.Albert,Z.N.Oltvai,andA.L.Barabasi,Nature,407651(2000)ArchaeaBacteriaEukaryotesScaleFree网络的基本特征PowerLawDegreeDistribution（幂律度分布）1、自相似结构：2、两极分化，高度弥散kkP)(kkPln)(ln)()()(kPkkkP复杂网络中顶点度的匹配关系AssortativeMixingbyDegree如果网络中度值高的顶点倾向于与其他高度值的顶点相互连接，则称网络具有同向匹配性质；–例如：社会网络如果网络中度值高的顶点倾向于与度值低的顶点相互连接，则称网络具有反向匹配性质；–例如：大部分生物、技术网络同