复杂网络模型

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