复杂网络模型

复杂网络:模型Lecture2幻灯片制作：xxx翻译者：武汉大学xxx什么是网络?网络:一个通过链接互相关联的实体的集合.互为朋友的人互相链接的计算机互相指向的网页互相作用的蛋白质图在数学世界,网络被称作图,实体被称作结点,而它们之间的链接被称作边。关于图的理论研究开始于18世纪，由数学家欧拉提出康尼斯堡桥梁问题在那之后图被更广泛深入地研究.过去的网络图在过去被用作为现有网络制作模型(举例来说.有公交网络,社会网络)通常这些网络都很小网络可以通过目视检查进行研究从而可以发现大量信息现在的网络更多的、更大型的网络出现了科技进步的产物•例如：互联网，网页我们收集更多、更好、更复杂数据的能力•例如：基因调控网络由数以千计、数以万计甚至数以亿计的结点所组成的网络不可能形象化因特网地图因特网网络的类型社会网络知识(信息)网络科学网络生物网络社会网络链接表示社会中的互动熟人的网络协作网络•演员的网络•合作作者的网络•导演的网络电话呼叫网络e-mail网络IM网络蓝牙网络性网络主页/博客网络知识（信息）网络结点代表信息,链接是信息的联系引文网络(有向无循环的)网络(有向的)点对点网络词网络基于信任的网络图形软件科学网络为商品分配所建的网络互联网•路由器标准,AS标准能量格航班网络电话网络交通网络•公路，铁路，行人交通生物网络网络代表生物系统蛋白质相互作用网络基因调控网络基因共同表达网络代谢路径食物网神经网络理解大型的图关于现实生活网络的数据有哪些？?我们可以解释网络是怎样产生的吗？关于网络性质的研究1999年左右WattsandStrogatz,Dynamicsandsmall-worldphenomenon（动力学和小世界现象）Faloutsos3,Onpower-lawrelationshipsoftheInternetTopology（基于权利-法律关系的互联网拓扑）Kleinbergetal.,TheWebasagraph（作为一张图的互联网）BarabasiandAlbert,Theemergenceofscalinginrealnetworks（现实网络中标度的出现）现实网络的性质大多数结点只有少数的邻居(度),但也有一些结点有很高的度数(度的幂律分布)无标度网络如果一个结点x连接着y和z,那么y和z就很可能是连接的高聚类系数大多数结点平均只相距几条边的距离小世界网络各个不同领域的网络(从因特网到生物网络)有着相同的性质是否有可能有一个统一的基本生成过程？小世界网络例如：六度分离理论–但是有超过六十亿人口生存在这个世界上！小世界网络(a)蛋白质(b)神经元(c)互联网生成随机图经典图形理论模型(Erdös-Renyi)每条边的独立产生概率为P很好的研究模型，但是:大多数顶点的度大致上相同两个结点相连的概率与它们是否共有一个邻居结点无关平均路径短现实网络建模现实生活网络不是随机的我们是否可以定义一个模型，它能够产生与现实生活中相似的具有统计性能的图?一系列关于随机图的模型网络的作用过程理解网络的结构为什么重要?流行病学:病毒在无标度网络中传播地更快随机接种疫苗的结点无法正常工作，但有针对性的疫苗接种是非常有效的网络结构随机网络无标度网络网络结构随机网络VS无标度网络网络网络结构网络搜索第一代搜索引擎:万维网只是作为一个文件的集合因为垃圾邮件发送者，无实质内容的、非结构化的、以及无人监管的内容，增加了万维网的规模第二代搜索引擎:作为一个网络的万维网应用链接描述文字技术以用来标注好的网页应该被更多的网页指向好的网页应该被更多的好网页指向•PageRank算法,Google!万维网•万维网是一个文件之间互相指向的网络•结点指网页而边指网页间的链接•边是有指向的：链接可以从它们出发或者到达它们万维网网络的未来网络现在看上去是这样的越来越多系统被网络模型化不同学科的科学家致力于对网络的研究(物理学家,计算机学家,数学家,生物学家,社会学家,经济学家)还有许多问题尚未被理解.数学工具图理论概率论线性代数图理论GraphG=(V,E)V=顶点的集合E=边的集合12345无向图E={(1,2),(1,3),(2,3),(3,4),(4,5)}图理论GraphG=(V,E)V=顶点的集合E=边的集合12345有向图E={‹1,2›,‹2,1›‹1,3›,‹3,2›,‹3,4›,‹4,5›}无向图12345结点i的度数d---d(i)与结点i相连的边数度序列[d(i),d(2),d(3),d(4),d(5)][2,2,2,1,1]度分布[(1,2),(2,3)]有向图12345结点i的入度指向结点i的边数结点i的出度以结点i为起始点的边数入度序列[1,2,1,1,1]出度序列[2,1,2,1,0]路径从结点i到结点j的路径:一段连续的边(有向或无向从结点i到结点j的连接)路径长度:路径上的边数结点i和结点j是相连的循环:一段初始和结束结点是同一个结点的路径1234512345最短路径从结点i到结点j的最短路径也被称作BFS路径,或短线程路径1234512345直径途中距离最长的一条最短路径1234512345无向图12345连通图:任意两个结点都存在连接的图非连通图:一个无连接的图连通区域:包含相连顶点的子图完全连通图CliqueKn一个最多有n(n-1)/2条边的图（n为顶点数）12345连通图12345强连通图:任意两个顶点之间存在一条路径弱连通图:边没有指向时图就是连通的子图12345子图:给定V’V,E’E,图G’=(V’,E’)就是G的一个子图.生成子图:给定V’V,E’E是V’中结点连成的边的集合.则图G’=(V’,E’),是G的一个生成子图树没有循环的无向连通图12345二分图集合V可以被分割成两个集合L和R的图,而所有的边由L和R的结点连接而成，在集合L和R内部不存在边。线性代数邻接矩阵对称矩阵的无向图123450100010100010110010100110A线性代数邻接矩阵非对称矩阵的无向图0000010000010100000100110A12345特征值与特征向量若值λ是矩阵A的特征值，且存在不为零向量的向量X，使得,Ax=λx.向量x是矩阵A的一个特征向量最大的特征向量被称为主特征值对应的特征向量被称为主特征向量对应最大值方向的变动特征值随机游动从一个结点开始,它的连接结点一律是随机的。平稳分布:你访问结点i次数的分数,随着随机游动经过边数的增逐渐加接近无穷大如果一个图是强连通图,它的平稳分布收敛与一个唯一的一个向量。随机游动平稳分布:标准邻接矩阵左边的主特征向量x=xP无向图的度分布1234500001100000210210000010021210P概率论概率空间:给定一对‹Ω,P›Ω:样本空间P:Ω的子集的测量概率随机变量X:Ω→R概率分布函数P[X=x]数学期望xx]xP[XXE随机图的类随机图的类被定义为一对‹Gn,P›，Gn是所有大小为n的图的集合,P是集合Gn的概率分布Erdös-Renyi图:每条边出现的概率为p当p=1/2时,我们得到一个统一的分布渐近符号对于两个函数f(n)和g(n)若存在正数c和N,使得f(n)≤cg(n),则对于所有的n≥N，有f(n)=O(g(n))若存在正数c和N,使得f(n)≥cg(n),则对于所有的n≥N，有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))P与NPP:在多项式时间内可以得到解决的一类问题NP:在多项式时间内可以得到验证的一类问题NP-hard:至少与NP中任何问题一样困难的问题近似算法NP-优化问题:给定一个问题的实例,找到一个能将目标函数最小化或最大化的解决方法。算法A是一个问题的系数c的近似值,若对于每一个输入值xA(x)≤cOPT(x)(最小化问题)A(x)≥cOPT(x)(最大化问题)复杂网络的实际应用---维基百科F.Colaiori,V.Servedio,G.Caldarelli,交流物理学部.,“LaSapienza”,罗马(意大利)D.Donato,S.Leonardi计算机科学学部.,“LaSapienza”,罗马(意大利)L.SaleteBuriol计算机科学学部.,UniversityofPortoAlegre,RioGrandedoSul(巴西)维基百科的复杂网络网络描述维基百科的统计分析模型与解释维基百科是怎样工作的？多亏了维基科技,一个用户可以增加新的条目到百科全书中修改已存在条目的内容修改其链接在万维网中，每个用户只对从他的网页发出的指令负责维基百科中的结点与边网络的边是百科全书的条目边是条目间的引用统计特性条目的数目在时间内成倍增长度分布优先连接为了研究优先连接,我们采用了由纽曼(2001)提出的方法，建立一个直方图，顶点的度的(k)，每次获得新的边的阶数t，通过一个系数n(k,t)/N(t)衡量它的贡献,其中:N(t)是第t次结点的数量n(k,t)是第t次度为k的结点的数量若(k)有一个approximatedly线性行为,则我们可能因此可以得出存在优先连接的结论优先连接圆:英语三角:葡萄牙语填充:入度白色:出度维基百科的一个模型在每一步中我们增加一个结点与M条边.边的方向是一个随机变量1.概率为R1的边从新结点出发并指向一个已存在的结点，而这个结点被选择的概率与它的入度成比例维基百科的一个模型在每一步中我们增加一个结点与M条边.边的方向是一个随机变量：2.概率为R2的边指向一个新的结点并从一个已存在的结点出发，这个结点被选择的概率与它的出度成比例维基百科的一个模型在每一步中我们增加一个结点与M条边.边的方向是一个随机变量:3.概率为R3=1–R1-R2的边指向一个已存在概率与它的入度成比例的结点并从一个已存在的概率与它的出度成比例的结点出发。相关性速率方程允许我们也计算入度-入度相关性缺乏相关性模型模型“–0.5%”Naïf解释假定:入度=人气出度=质量若入度增长的概率由入度本身决定，这就意味着在维基百科中人气压倒了质量。就像在万维网中一样吗？群落结构维基百科显示了一个强有力的群落结构结论维基百科条目组成了一个拥有优先连接、入度与出度成幂律分布和缺乏相关性的的复杂网络。优先连接解释了主要的统计特性Naïf解释揭示出维基科技还不足以提供一个能出于对互联网的尊重更好的传播信息的万维网。群落结构还需要更多理解社会网络增长中的优先连接：网络百科全书维基百科A.C.,V.D.P.Servedio,F.Colaiori,L.S.Buriol,D.Donato,S.Leonardi,和G.CaldarelliPhys.Rev.E74,036116(2006)M.E.J.Newman,Thestructureandfunctionofcomplexnetworks（复杂网络的结构与功能）,数学学会评述,45(2):167-256,2003参考文献