复杂网络模型PPT课件

-,1,复杂网络:模型,Lecture2,幻灯片制作：PanayiotisTsaparas翻译者：武汉大学夏庆琳,-,2,什么是网络?,网络:一个通过链接互相关联的实体的集合.互为朋友的人互相链接的计算机互相指向的网页互相作用的蛋白质,-,3,图,在数学世界,网络被称作图,实体被称作结点,而它们之间的链接被称作边。关于图的理论研究开始于18世纪，由数学家欧拉提出康尼斯堡桥梁问题在那之后图被更广泛深入地研究.,-,4,过去的网络,图在过去被用作为现有网络制作模型(举例来说.有公交网络,社会网络)通常这些网络都很小网络可以通过目视检查进行研究从而可以发现大量信息,-,5,现在的网络,更多的、更大型的网络出现了科技进步的产物例如：互联网，网页我们收集更多、更好、更复杂数据的能力例如：基因调控网络由数以千计、数以万计甚至数以亿计的结点所组成的网络不可能形象化,-,6,因特网地图,-,7,因特网,-,8,网络的类型,社会网络知识(信息)网络科学网络生物网络,-,9,社会网络,链接表示社会中的互动熟人的网络协作网络演员的网络合作作者的网络导演的网络电话呼叫网络e-mail网络IM网络蓝牙网络性网络主页/博客网络,-,10,知识（信息）网络,结点代表信息,链接是信息的联系引文网络(有向无循环的)网络(有向的)点对点网络词网络基于信任的网络图形软件,-,11,科学网络,为商品分配所建的网络互联网路由器标准,AS标准能量格航班网络电话网络交通网络公路，铁路，行人交通,-,12,生物网络,网络代表生物系统蛋白质相互作用网络基因调控网络基因共同表达网络代谢路径食物网神经网络,-,13,理解大型的图,关于现实生活网络的数据有哪些？?我们可以解释网络是怎样产生的吗？,-,14,关于网络性质的研究,1999年左右WattsandStrogatz,Dynamicsandsmall-worldphenomenon（动力学和小世界现象）Faloutsos3,Onpower-lawrelationshipsoftheInternetTopology（基于权利-法律关系的互联网拓扑）Kleinbergetal.,TheWebasagraph（作为一张图的互联网）BarabasiandAlbert,Theemergenceofscalinginrealnetworks（现实网络中标度的出现）,-,15,现实网络的性质,大多数结点只有少数的邻居(度),但也有一些结点有很高的度数(度的幂律分布)无标度网络如果一个结点x连接着y和z,那么y和z就很可能是连接的高聚类系数大多数结点平均只相距几条边的距离小世界网络各个不同领域的网络(从因特网到生物网络)有着相同的性质是否有可能有一个统一的基本生成过程？,-,16,小世界网络,例如：六度分离理论,但是有超过六十亿人口生存在这个世界上！,-,17,小世界网络,(a)蛋白质(b)神经元(c)互联网,-,18,生成随机图,经典图形理论模型(Erds-Renyi)每条边的独立产生概率为P很好的研究模型，但是:大多数顶点的度大致上相同两个结点相连的概率与它们是否共有一个邻居结点无关平均路径短,-,19,现实网络建模,现实生活网络不是随机的我们是否可以定义一个模型，它能够产生与现实生活中相似的具有统计性能的图?一系列关于随机图的模型,-,20,网络的作用过程,理解网络的结构为什么重要?流行病学:病毒在无标度网络中传播地更快随机接种疫苗的结点无法正常工作，但有针对性的疫苗接种是非常有效的,-,21,网络结构,随机网络,无标度网络,-,22,网络结构,随机网络VS无标度网络,-,23,网络,网络结构,-,24,网络搜索,第一代搜索引擎:万维网只是作为一个文件的集合因为垃圾邮件发送者，无实质内容的、非结构化的、以及无人监管的内容，增加了万维网的规模第二代搜索引擎:作为一个网络的万维网应用链接描述文字技术以用来标注好的网页应该被更多的网页指向好的网页应该被更多的好网页指向PageRank算法,Google!,-,25,万维网,万维网是一个文件之间互相指向的网络结点指网页而边指网页间的链接边是有指向的：链接可以从它们出发或者到达它们,-,26,万维网,-,27,网络的未来,网络现在看上去是这样的越来越多系统被网络模型化不同学科的科学家致力于对网络的研究(物理学家,计算机学家,数学家,生物学家,社会学家,经济学家)还有许多问题尚未被理解.,-,28,数学工具,图理论概率论线性代数,-,29,图理论,GraphG=(V,E)V=顶点的集合E=边的集合,1,2,3,4,5,无向图E=(1,2),(1,3),(2,3),(3,4),(4,5),-,30,图理论,GraphG=(V,E)V=顶点的集合E=边的集合,1,2,3,4,5,有向图E=1,2,2,11,3,3,2,3,4,4,5,-,31,无向图,1,2,3,4,5,结点i的度数d-d(i)与结点i相连的边数,度序列d(i),d(2),d(3),d(4),d(5)2,2,2,1,1,度分布(1,2),(2,3),-,32,有向图,1,2,3,4,5,结点i的入度指向结点i的边数,结点i的出度以结点i为起始点的边数,入度序列1,2,1,1,1出度序列2,1,2,1,0,-,33,路径,从结点i到结点j的路径:一段连续的边(有向或无向从结点i到结点j的连接)路径长度:路径上的边数结点i和结点j是相连的循环:一段初始和结束结点是同一个结点的路径,1,2,3,4,5,1,2,3,4,5,-,34,最短路径,从结点i到结点j的最短路径也被称作BFS路径,或短线程路径,1,2,3,4,5,1,2,3,4,5,-,35,直径,途中距离最长的一条最短路径,1,2,3,4,5,1,2,3,4,5,-,36,无向图,1,2,3,4,5,连通图:任意两个结点都存在连接的图非连通图:一个无连接的图连通区域:包含相连顶点的子图,-,37,完全连通图,CliqueKn一个最多有n(n-1)/2条边的图（n为顶点数）,1,2,3,4,5,-,38,连通图,1,2,3,4,5,强连通图:任意两个顶点之间存在一条路径,弱连通图:边没有指向时图就是连通的,-,39,子图,1,2,3,4,5,子图:给定VV,EE,图G=(V,E)就是G的一个子图.生成子图:给定VV,EE是V中结点连成的边的集合.则图G=(V,E),是G的一个生成子图,-,40,树,没有循环的无向连通图,1,2,3,4,5,-,41,二分图,集合V可以被分割成两个集合L和R的图,而所有的边由L和R的结点连接而成，在集合L和R内部不存在边。,-,42,线性代数,邻接矩阵对称矩阵的无向图,1,2,3,4,5,-,43,线性代数,邻接矩阵非对称矩阵的无向图,1,2,3,4,5,-,44,特征值与特征向量,若值是矩阵A的特征值，且存在不为零向量的向量X，使得,Ax=x.向量x是矩阵A的一个特征向量最大的特征向量被称为主特征值对应的特征向量被称为主特征向量对应最大值方向的变动,-,45,特征值,-,46,随机游动,从一个结点开始,它的连接结点一律是随机的。平稳分布:你访问结点i次数的分数,随着随机游动经过边数的增逐渐加接近无穷大如果一个图是强连通图,它的平稳分布收敛与一个唯一的一个向量。,-,47,随机游动,平稳分布:标准邻接矩阵左边的主特征向量x=xP无向图的度分布,1,2,3,4,5,-,48,概率论,概率空间:给定一对,P:样本空间P:的子集的测量概率随机变量X:R概率分布函数PX=x数学期望,-,49,随机图的类,随机图的类被定义为一对Gn,P，Gn是所有大小为n的图的集合,P是集合Gn的概率分布Erds-Renyi图:每条边出现的概率为p当p=1/2时,我们得到一个统一的分布,-,50,渐近符号,对于两个函数f(n)和g(n)若存在正数c和N,使得f(n)cg(n),则对于所有的nN，有f(n)=O(g(n)若存在正数c和N,使得f(n)cg(n),则对于所有的nN，有f(n)=(g(n)若f(n)=O(g(n)并且f(n)=(g(n)，则有f(n)=(g(n)若limf(n)/g(n)=0,则随着n，有f(n)=o(g(n)若limf(n)/g(n)=,则随着n，有f(n)=(g(n),-,51,P与NP,P:在多项式时间内可以得到解决的一类问题NP:在多项式时间内可以得到验证的一类问题NP-hard:至少与NP中任何问题一样困难的问题,-,52,近似算法,NP-优化问题:给定一个问题的实例,找到一个能将目标函数最小化或最大化的解决方法。算法A是一个问题的系数c的近似值,若对于每一个输入值xA(x)cOPT(x)(最小化问题)A(x)cOPT(x)(最大化问题),-,53,复杂网络的实际应用-维基百科,F.Colaiori,V.Servedio,G.Caldarelli,交流物理学部.,“LaSapienza”,罗马(意大利)D.Donato,S.Leonardi计算机科学学部.,“LaSapienza”,罗马(意大利)L.SaleteBuriol计算机科学学部.,UniversityofPortoAlegre,RioGrandedoSul(巴西),-,54,维基百科的复杂网络,网络描述维基百科的统计分析模型与解释,-,55,-,56,-,57,-,58,维基百科是怎样工作的？,多亏了维基科技,一个用户可以增加新的条目到百科全书中修改已存在条目的内容修改其链接在万维网中，每个用户只对从他的网页发出的指令负责,-,59,维基百科中的结点与边,网络的边是百科全书的条目边是条目间的引用,-,60,统计特性,条目的数目在时间内成倍增长,-,61,度分布,-,62,优先连接,为了研究优先连接,我们采用了由纽曼(2001)提出的方法，建立一个直方图，顶点的度的(k)，每次获得新的边的阶数t，通过一个系数n(k,t)/N(t)衡量它的贡献,其中:N(t)是第t次结点的数量n(k,t)是第t次度为k的结点的数量若(k)有一个approximatedly线性行为,则我们可能因此可以得出存在优先连接的结论,-,63,优先连接,圆:英语三角:葡萄牙语填充:入度白色:出度,-,64,维基百科的一个模型,在每一步中我们增加一个结点与M条边.边的方向是一个随机变量1.概率为R1的边从新结点出发并指向一个已存在的结点，而这个结点被选择的概率与它的入度成比例,-,65,维基百科的一个模型,在每一步中我们增加一个结点与M条边.边的方向是一个随机变量：2.概率为R2的边指向一个新的结点并从一个已存在的结点出发，这个结点被选择的概率与它的出度成比例,-,66,维基百科的一个模型,在每一步中我们增加一个结点与M条边.边的方向是一个随机变量:3.概率为R3=1R1-R2的边指向一个已存在概率与它的入度成比例的结点并从一个已存在的概率与它的出度成比例的结点出发。,-,67,相关性,速率方程允许我们也计算入度-入度相关性,-,68,缺乏相关性,模型,模型“0.5%”,-,69,Naf解释,假定:入度=人气出度=质量若入度增长的概率由入度本身决定，这就意味着在维基百科中人气压倒了质量。就像在万维网中一样吗？,-,70,群落结构,维基百科显示了一个强有力的群落结构,-,71,结论,维基百科条目组成了一个拥有优先连接、入度与出度成幂律分布和缺乏相关性的的复杂网络。优先连接解释了主要的统计特性Naf解释揭示出维基科技还不足以提供一个能出于对互联网的尊