复杂网络研究现状狄增如.ppt

《复杂网络研究现状狄增如.ppt》由会员分享，可在线阅读，更多相关《复杂网络研究现状狄增如.ppt（89页珍藏版）》请在三一办公上搜索。

1、复杂网络研究 现状与前瞻,狄增如北京师范大学管理学院系统科学系北京师范大学复杂性研究中心 北京大学-2007.11,关于复杂性,关于复杂性,我们所关心的问题：大量个体（更典型的是具有适应性的主体）所组成的复杂系统，在没有中心控制、非完全信息、仅仅存在局域相互作用的条件下，通过个体之间的非线性相互作用，可以在宏观层次上涌现出一定的结构和功能。,Internet,全局相互作用,晶格,相互作用与复杂性,扩散,平均场,?,复杂系统不能够用分析的方法去研究，必须考虑个体之间的关联和作用；理解复杂系统的行为应该从理解系统相互作用网络的拓扑结构开始；网络拓扑结构的信息是构建系统模型、研究系统性质和功能的基础

2、。,为什么研究复杂网络？,复杂网络是构成复杂系统的基本框架（backbone），每一个复杂系统都可以看作是单元或个体之间的相互作用网络；复杂网络在刻画复杂性方面的重要性是由于结构和功能之间是相互影响的。,复杂网络是研究复杂系统的一种角度和方法，它关注系统中个体相互关联的作用的拓扑结构，是理解复杂系统性质和功能的基础。,为什么研究复杂网络？,技术网络,WWW,电力网,因特网,社会网络,朋友关系网,性关系网,科学引文网,演员网,科学家合著网,交通运输网络,航空网,道路交通网,城市公共交通网,生物网络,神经网络,基因网络,蛋白质相互作用网络,生态网络,新陈代谢网络,生命金字塔,不同领域的复杂网络,社

3、会网：演员合作网，友谊网，姻亲关系网，科研合作网，Email网生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络信息网络：WWW，专利使用，论文引用，计算机共享技术网络：电力网，Internet，电话线路网，交通运输网：航线网，铁路网，公路网，自然河流网,A food web,A Unified Approachtowards the Connection Topology of various Complex Systems,复杂网络,网络研究的历史,1736，欧拉：哥尼斯堡七桥1950，Erdos,Renyi:随机图论1998，Strogatz,Barabasi:小世界和无标度网络,

4、为什么现在才开始研究复杂网络？,计算机技术的发展：使我们拥有各种网络的数据库，并有可能对大规模的网络进行实证研究普适性的发现：许多实际网络具有相同的定性性质且已有的理论不能描述和解释理论研究的发展小世界网络(Small World Network),无标度网络(Scale-free Network)统计物理学的研究手段,复杂网络研究所关心的问题,如何定量刻画复杂网络？网络结构的描述及其性质网络是如何发展成现在这种结构的？网络演化模型网络特定结构的后果是什么？网络结构的鲁棒性网络上的动力学行为和过程,复杂网络的结构,四种结构模型：规则网络随机网络小世界网络无标度网络,对网络结构的描述,几何量及其

5、分布度（Degree）：朋友的个数集聚系数（群系数）（Clustering coefficient）：朋友的朋友还是不是朋友的情况最短路径（Shortest path）：两个顶点之间边数最少的路径介数（Betweenness）：经过我的最短路径的条数,一个简单的例子,K=5C=0,K=5C=1,规则网络,一般情况下，聚集系数较大，平均最短路径较长。,ER随机网络,当p不太小时，聚集系数较小，平均最短路径较短。,随机网络的平均最短路径及其与实证数据的比较,随机网络的平均聚集系数及其与实证数据的比较,Small World Network,C(p):平均聚集系数 L(p):平均最短路径,度分布,分

6、布函数f(k)：网络中度值为k的顶点占总点数的比例随机网络的度分布Poisson分布,10000个顶点p=0.0015,度分布,幂律分布Power Law,g=-3,World Wide Web,800 million documents(S.Lawrence,1999),Nodes:WWW documents Links:URL links,NWWW 109 N(k=500)103,P(k=500)10-6,INTERNET BACKBONE,(Faloutsos,Faloutsos and Faloutsos,1999),Nodes:computers,routers Links:phys

7、ical lines,Nodes:actors Links:cast jointly,N=212,250 actors k=28.78,P(k)k-,=2.3,ACTOR CONNECTIVITIES,SCIENCE CITATION INDEX,Nodes:papers Links:citations,1736 PRL papers(1988),Nodes:scientist(authors)Links:write paper together,(Newman,2000,H.Jeong et al 2001),SCIENCE COAUTHORSHIP,Sex-web,Nodes:people

8、(Females;Males)Links:sexual relationships,Liljeros et al.Nature 2001,4781 Swedes;18-74;59%response rate.,Metabolic network,Organisms from all three domains of life are scale-free networks!,H.Jeong,B.Tombor,R.Albert,Z.N.Oltvai,and A.L.Barabasi,Nature,407 651(2000),Archaea,Bacteria,Eukaryotes,Scale Fr

9、ee网络的基本特征,Power Law Degree Distribution（幂律度分布）1、自相似结构：2、两极分化，高度弥散,复杂网络中顶点度的匹配关系Assortative Mixing by Degree,如果网络中度值高的顶点倾向于与其他高度值的顶点相互连接，则称网络具有同向匹配性质；例如：社会网络如果网络中度值高的顶点倾向于与度值低的顶点相互连接，则称网络具有反向匹配性质；例如：大部分生物、技术网络,同向匹配无标度网络,反向匹配无标度网络,Physics collaboration network,Palla et al.Nature 435,9(2005),复杂网络中的社团结构

10、Community Structures,社团内部连接紧密，社团之间连接相对稀疏,Santa Fe研究所的科学家合作网,Rhesus猴子网,经济物理学科学家合作网,网络模体-Network Motifs,模体在网络中密度明显较高的子图（基本结构单元）,复杂网络演化模型,BA模型网络增长、偏好连接基于蛋白质相互作用的演化模型复制、分化、变异优化演化模型,其形成机制是什么？结构与功能？,Most real world networks have the same internal structure:,Scale-free networks,BA偏好连接模型PREFERENTIAL ATTACHM

11、ENT,(1)The number of nodes(N)is NOT fixed.,Networks continuously expand by the addition of new nodes,(2)The attachment is NOT uniform.,A node is linked with higher probability to a node that already has a large number of links.,Examples:WWW:new documents link to well known sites(CNN,YAHOO,NewYork Ti

12、mes,etc)Citation:well cited papers are more likely to be cited again,Examples:WWW:addition of new documents Citation:publication of new papers,Scale-free model,(1)GROWTH:At every timestep we add a new node with m edges(connected to the nodes already present in the system).(2)PREFERENTIAL ATTACHMENT:

13、The probability that a new node will be connected to node i depends on the connectivity ki of that node,A.-L.Barabsi,R.Albert,Science 286,509(1999),P(k)k-3,网络的结构与功能,网络上的动力学行为和过程动力系统：自旋、振子或混沌的同步、可激发系统传播过程：信息传播与拥堵、网络搜寻、运输过程、疾病传播、谣言的传播、舆论形成博弈与其他社会行为：囚徒困境、少数者博弈其他过程：电力网的级联失效等,复杂网络上的渗流和网络鲁棒性,给定度分布P(k)的复杂网

14、络上的点缺陷：顶点以概率q被随机的占据（工作状态良好）或以概率1-q被空置(被破坏)然后考察系统存在无限大连通集团的临界概率qc,对无标度网络当=3,临界概率 qc 是0或负值.无标度网络对于顶点的随机移除非常稳健!,Percolation and Network Resilience,Callyway et al:占据某个顶点的概率可以是该顶点度值 k 的任意函数:qk.取 qk=(k-kmax),Heaviside step function只需移除掉很少比例的顶点就可以完全摧毁网络中的最大连通集团！,无标度网络对有目的的最大度攻击非常脆弱！,Error and Attack Tolera

15、nce,网络上的动力系统,网络同步,全局耦合下萤火虫的同步,小世界网络上混沌映象的同步,SW:,随着短边重连概率的增加，同步得到加强,影响同步的结构因素：平均最短距离、度分布最大度值、最大点介数值,可激发系统,复杂网络上的疾病传播,网络上的动力学疾病传播,Epidemic Dynamics in Complex Networks,Reachability in Colorado Springs(Sexual contact only),High-risk actors over 4 years695 people representedLongest path is 17 stepsAvera

16、ge distance is about 5 stepsAverage person is within 3 steps of 75 other people137 people connected through 2 independent paths,core of 30 people connected through 4 independent paths,(Node size=log of degree),Drug sharing network,传染病动力学：SI 模型,接触数目 I S,固定人口总数的疾病传播模型:,I(t),:易受感染者人数,:总人数,:传染者人数,:传染比例,

17、t,Epidemic Dynamics：SI Model,传染病动力学：SIS 模型,有效扩散速率：,传染病动力学：SIR模型,疾病扩散条件：,OR,网络上的疾病传播,完全混合 网络拓扑结构的影响规则网格复杂网络,SIS model on Networks,网络上的疾病传播,小世界网上的SIS 模型,利用平均场理论计算被感染顶点密度随时间的变化：,稳态解:,传播阈值:,有效扩散速率,And Let g=1,小世界网上的SIS 模型,计算机数值模拟N=103_-N=3*106,=6,10 个不同的网络,100 个不同的初始分布,BA无标度网络上的SIS 模型,利用平均场理论计算被感染顶点密度随时

18、间的变化：,SW,BA,稳态解:,BA无标度网度分布,Evolution,BA无标度网络上的SIS 模型,SIR Model on Complex Networks,Disease spreading,Percolation,复杂网络上的SIR模型,Disease spreading,Percolation!,无标度网络上的SIR模型,复杂网络上的疾病传播,网络结构上的少数者博弈模型,少数者博弈,网络结构的影响？,数值模拟结果,关于复杂网络研究现状,复杂网络研究是否已经形成并仍处于热潮之中？在复杂网络研究中有什么应该注意的问题？我们还应该继续做些什么？,复杂网络研究的综述与著作,S.H.Str

19、ogatz,Nature,410,(2001)268R.Albert,A.-L.Barabasi,Rev.Mod.Phys.51(2002)1079M.E.J.Newman,SIAM Rev.45(2003)167S.N.Dorogovtesev,J.Mendes,Evolving of Networks,Oxford Un.Press,2003E.Ben-Naim,et al,Complex Networks,Springer,2004S.Boccaletti,et al,Complex Networks:Structure and dynamics,Phys.Rep.424(2006)17

20、5-308 Newman,Barabasi,Watts,The Structure and Dynamics of Networks,Princeton University Press,2006,部分由物理学推动的科研热潮,混沌和分形 Chaos and Fractals自旋玻璃 Spin Glasses自组织临界性 Self-organized criticality 统计物理学在生物进化中的应用经济物理学 Econophysics复杂网络 Complex networks?,例如 Per Baks 关于自组织临界性的著作冠名为：How Nature Works中译本：大自然是如何工作的,

21、毫无疑问，这些工作对科学的发展做出了贡献，但有些研究的意义被夸大了。,波及面也各有不同,尽管自组织临界性被认为有广泛的应用价值，但研究工作事实上仅仅局限在物理学领域中。对于经济物理学，我们很少能够在经济学杂志上见到相关工作，经济物理学的文章只发表在物理学以及专门的经济物理学杂志上。,而复杂网络研究已经波及到众多科学领域，确实可以称之为形成了研究热潮,但还没有做到与其他学科领域的有机结合,发挥复杂网络研究的意义和价值应该注意以下几点：,具备你所研究的系统的相关知识；存在一个确实需要网络基础的科学问题，而复杂网络有助于你解决它。清楚了解系统相互作用的拓扑结构仅仅是万里长征走完了第一步，它不可能魔术

22、般地解决系统的根本问题。,同时应该注意复杂网络研究中所可能出现的问题,在实证研究中，样本太少或取样的偏差会导致对网络结构的错误认识。,把系统的某些特性仅仅归结为网络结构的作用往往是片面的。,例如，对Intenet的容错性和鲁棒性的研究,identical power-law degrees,高度值的中枢节点核心,低度值的网状核心,度分布相同的网络的细致结构未必相同,发现和刻画实际系统的网络结构模拟网络的演化探讨结构与功能之间的相互关系利用网络结构控制和优化系统功能,我们接下来该做什么？,我们接下来该做什么？,是否有更多的统计分布帮助我们深入理解复杂网络的结构和分类？对于不同的网络结构是否存在规范的分类方法？为什么许多网络是组合式的？影响生物网络的演化机制是什么？如何量化不同性质网络间的相互作用（网络的网络）？,为什么社会网络都是相配的，而所有的生物和科技网都是不相配的？网络动力学是否有普遍性质？在网络中发生的动力学过程怎样影响网络的拓扑结构？如何研究与网络功能相关的网络容错性与鲁棒性？,我们接下来该做什么？,谢谢大家！,