复杂网络模型

复杂网络模型复杂网络模型复杂网络模型什么是网络? 网络:一个通过链接互相关联的实体的集合.互为朋友的人互相链接的计算机互相指向的网页互相作用的蛋白质2书籍能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进复杂网络模型复杂网络模型复杂网络模型什么是网络? 网络:一什么是网络? 网络:一个通过链接互相关联的实体的集合.互为朋友的人互相链接的计算机互相指向的网页互相作用的蛋白质2什么是网络? 网络:一个通过链接互相关联的实体的集合.2图在数学世界,网络被称作图,实体被称作结点,而它们之间的链接被称作边。关于图的理论研究开始于18世纪，由数学家欧拉提出康尼斯堡桥梁问题在那之后图被更广泛深入地研究.

3图在数学世界,网络被称作图,实体被称作结点,而它们之间过去的网络图在过去被用作为现有网络制作模型(举例来说.有公交网络,社会网络)通常这些网络都很小网络可以通过目视检查进行研究从而可以发现大量信息4过去的网络图在过去被用作为现有网络制作模型(举例来说.有现在的网络更多的、更大型的网络出现了科技进步的产物例如：互联网，网页我们收集更多、更好、更复杂数据的能力例如：基因调控网络由数以千计、数以万计甚至数以亿计的结点所组成的网络不可能形象化5现在的网络更多的、更大型的网络出现了5因特网地图6因特网地图6因特网7因特网7网络的类型社会网络知识(信息)网络科学网络生物网络8网络的类型社会网络8社会网络链接表示社会中的互动熟人的网络协作网络演员的网络合作作者的网络导演的网络电话呼叫网络e-mail网络IM网络蓝牙网络性网络主页/博客网络9社会网络链接表示社会中的互动9知识（信息）网络结点代表信息,链接是信息的联系引文网络(有向无循环的)网络(有向的)点对点网络词网络基于信任的网络图形软件10知识（信息）网络结点代表信息,链接是信息的联系10科学网络为商品分配所建的网络互联网路由器标准,AS标准能量格航班网络电话网络交通网络公路，铁路，行人交通11科学网络为商品分配所建的网络11生物网络网络代表生物系统蛋白质相互作用网络基因调控网络基因共同表达网络代谢路径食物网神经网络12生物网络网络代表生物系统12理解大型的图关于现实生活网络的数据有哪些？?我们可以解释网络是怎样产生的吗？13理解大型的图关于现实生活网络的数据有哪些？?13关于网络性质的研究1999年左右WattsandStrogatz,Dynamicsandsmall-worldphenomenon（动力学和小世界现象）Faloutsos3,Onpower-lawrelationshipsoftheInternetTopology（基于权利-法律关系的互联网拓扑）Kleinbergetal.,TheWebasagraph（作为一张图的互联网）BarabasiandAlbert,Theemergenceofscalinginrealnetworks（现实网络中标度的出现）14关于网络性质的研究1999年左右14现实网络的性质大多数结点只有少数的邻居(度),但也有一些结点有很高的度数(度的幂律分布)无标度网络如果一个结点x

连接着y和z,那么y

和z

就很可能是连接的高聚类系数大多数结点平均只相距几条边的距离小世界网络各个不同领域的网络(从因特网到生物网络)有着相同的性质是否有可能有一个统一的基本生成过程？15现实网络的性质大多数结点只有少数的邻居(度),但也有一些小世界网络例如：六度分离理论但是有超过六十亿人口生存在这个世界上！16小世界网络例如：六度分离理论但是有超过六十亿人口生存在这个世小世界网络(a)蛋白质(b)神经元(c)互联网17小世界网络(a)蛋白质(b)神经元(c)互生成随机图经典图形理论模型(Erdös-Renyi)每条边的独立产生概率为P很好的研究模型，但是:大多数顶点的度大致上相同两个结点相连的概率与它们是否共有一个邻居结点无关平均路径短18生成随机图经典图形理论模型(Erdös-Renyi)18现实网络建模现实生活网络不是随机的我们是否可以定义一个模型，它能够产生与现实生活中相似的具有统计性能的图?一系列关于随机图的模型19现实网络建模现实生活网络不是随机的19网络的作用过程理解网络的结构为什么重要?流行病学:病毒在无标度网络中传播地更快随机接种疫苗的结点无法正常工作，但有针对性的疫苗接种是非常有效的20网络的作用过程理解网络的结构为什么重要?20网络结构随机网络无标度网络21网络结构随机网络无标度网络21网络结构随机网络VS无标度网络22网络结构随机网络VS无标度网络22网络网络结构23网络网络结构23网络搜索第一代搜索引擎:万维网只是作为一个文件的集合因为垃圾邮件发送者，无实质内容的、非结构化的、以与无人监管的内容，增加了万维网的规模第二代搜索引擎:作为一个网络的万维网应用链接描述文字技术以用来标注好的网页应该被更多的网页指向好的网页应该被更多的好网页指向PageRank算法,Google!24网络搜索第一代搜索引擎:万维网只是作为一个文件的集合24万维网万维网是一个文件之间互相指向的网络结点指网页而边指网页间的链接边是有指向的：链接可以从它们出发或者到达它们25万维网万维网是一个文件之间互相指向的网络25万维网26万维网26网络的未来网络现在看上去是这样的越来越多系统被网络模型化不同学科的科学家致力于对网络的研究(物理学家,计算机学家,数学家,生物学家,社会学家,经济学家)还有许多问题尚未被理解.27网络的未来网络现在看上去是这样的27数学工具图理论概率论线性代数28数学工具图理论28图理论GraphG=(V,E)V=顶点的集合E=边的集合12345无向图E={(1,2),(1,3),(2,3),(3,4),(4,5)}29图理论GraphG=(V,E)12345无向图29图理论GraphG=(V,E)V=顶点的集合E=边的集合12345有向图E={‹1,2›,‹2,1›

‹1,3›,‹3,2›,‹3,4›,‹4,5›}30图理论GraphG=(V,E)12345有向图30无向图12345结点i的度数dd(i)与结点i相连的边数度序列[d(i),d(2),d(3),d(4),d(5)][2,2,2,1,1]度分布[(1,2),(2,3)]31无向图12345结点i的度数dd(i)度序列度分布3有向图12345结点i的入度指向结点i的边数结点i的出度以结点i为起始点的边数入度序列[1,2,1,1,1]出度序列[2,1,2,1,0]32有向图12345结点i的入度结点i的出度入度序列32路径从结点i到结点j的路径:一段连续的边(有向或无向从结点i到结点j的连接)路径长度:路径上的边数结点i和结点j是相连的循环:一段初始和结束结点是同一个结点的路径123451234533路径从结点i到结点j的路径:一段连续的边(有向或无向从结最短路径从结点i到结点j的最短路径也被称作BFS路径,或短线程路径123451234534最短路径从结点i到结点j的最短路径123451234534直径途中距离最长的一条最短路径123451234535直径途中距离最长的一条最短路径123451234535无向图12345连通图:任意两个结点都存在连接的图非连通图:一个无连接的图连通区域:包含相连顶点的子图36无向图12345连通图:任意两个结点都存在连接的图36完全连通图CliqueKn一个最多有n(n-1)/2条边的图（n为顶点数）1234537完全连通图CliqueKn1234537连通图12345强连通图:任意两个顶点之间存在一条路径弱连通图:边没有指向时图就是连通的38连通图12345强连通图:任意两个顶点之间存在一条路径弱连子图12345子图:给定V’

V,E’E,图

G’=(V’,E’)就是G的一个子图.生成子图:给定V’

V,E’E是V’中结点连成的边的集合.则图G’=(V’,E’),是G的一个生成子图39子图12345子图:给定V’V,E’E,3树没有循环的无向连通图1234540树没有循环的无向连通图1234540二分图集合V可以被分割成两个集合L和R的图,而所有的边由L和R的结点连接而成，在集合L和R内部不存在边。41二分图集合V可以被分割成两个集合L和R的图,而所有的边由L线性代数邻接矩阵对称矩阵的无向图1234542线性代数邻接矩阵1234542线性代数邻接矩阵非对称矩阵的无向图1234543线性代数邻接矩阵1234543特征值与特征向量若值λ是矩阵A的特征值，且存在不为零向量的向量X，使得,Ax=λx.向量x是矩阵A的一个特征向量最大的特征向量被称为主特征值对应的特征向量被称为主特征向量对应最大值方向的变动44特征值与特征向量若值λ是矩阵A的特征值，且存在不为零向量的特征值45特征值45随机游动从一个结点开始,它的连接结点一律是随机的。平稳分布:你访问结点i次数的分数,随着随机游动经过边数的增逐渐加接近无穷大如果一个图是强连通图,它的平稳分布收敛与一个唯一的一个向量。46随机游动从一个结点开始,它的连接结点一律是随机的。46随机游动平稳分布:标准邻接矩阵左边的主特征向量x=xP无向图的度分布1234547随机游动平稳分布:标准邻接矩阵左边的主特征向量123454概率论概率空间:给定一对‹Ω,P›Ω:样本空间P:Ω的子集的测量概率随机变量X:Ω→R概率分布函数P[X=x]数学期望48概率论概率空间:给定一对‹Ω,P›48随机图的类随机图的类被定义为一对‹Gn,P›

，Gn

是所有大小为n的图的集合,P

是集合Gn的概率分布Erdös-Renyi图:每条边出现的概率为p当

p=1/2时,我们得到一个统一的分布49随机图的类随机图的类被定义为一对‹Gn,P›，Gn是渐近符号对于两个函数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))50渐近符号对于两个函数f(n)和g(n)50P

与NPP:在多项式时间内可以得到解决的一类问题NP:在多项式时间内可以得到验证的一类问题NP-hard:至少与NP中任何问题一样困难的问题51P与NPP:在多项式时间内可以得到解决的一类问题51近似算法NP-优化问题:给定一个问题的实例,找到一个能将目标函数最小化或最大化的解决方法。算法A

是一个问题的系数c的近似值,若对于每一个输入值x

A(x)≤cOPT(x)(最小化问题)

A(x)≥cOPT(x)(最大化问题)52近似算法NP-优化问题:给定一个问题的实例,找到一个能将复杂网络的实际应用维基百科F.Colaiori,V.Servedio,G.Caldarelli,交流物理学部.,“LaSapienza”,罗马(意大利)D.Donato,S.Leonardi计算机科学学部.,“LaSapienza”,罗马(意大利)L.SaleteBuriol计算机科学学部.,UniversityofPortoAlegre,RioGrandedoSul(巴西)53复杂网络的实际应用维基百科F.Colaiori,V维基百科的复杂网络网络描述维基百科的统计分析模型与解释54维基百科的复杂网络网络描述54555556565757维基百科是怎样工作的？多亏了维基科技,一个用户可以

增加新的条目到百科全书中

修改已存在条目的内容

修改其链接在万维网中，每个用户只对从他的网页发出的指令负责

58维基百科是怎样工作的？多亏了维基科技,一个用户可以58维基百科中的结点与边网络的边是百科全书的条目边是条目间的引用59维基百科中的结点与边网络的边是百科全书的条目59统计特性条目的数目在时间内成倍增长60统计特性条目的数目在时间内成倍增长60度分布61度分布61优先连接为了研究优先连接,我们采用了由纽曼(2001)提出的方法

，建立一个直方图，顶点的度的(k)

，每次获得新的边的阶数t，通过一个系数n(k,t)/N(t)衡量它的贡献,其中:N(t)

是第t次结点的数量n(k,t)

是第t次度为k的结点的数量若(k)

有一个approximatedly线性行为,则我们可能因此可以得出存在优先连接的结论62优先连接为了研究优先连接,我们采用了由纽曼(2001)提出优先连接圆:英语三角:葡萄牙语填充:入度白色:出度63优先连接圆:英语63维基百科的一个模型在每一步中我们增加一个结点与M条边.边的方向是一个随机变量1.概率为R1的边从新结点出发并指向一个已存在的结点，而这个结点被选择的概率与它的入度成比例64维基百科的一个模型在每一步中我们增加一个结点与M条边.边的维基百科的一个模型在每一步中我们增加一个结点与M条边.边的方向是一个随机变量：2.概率为R2的边指向一个新的结点并从一个已存在的结点出发，这个结点被选择的概率与它的出度成比例65维基百科的一个模型在每一步中我们增加一个结点与M条边.边的维基百科的一个模型在每一步中我们增加一个结点与M条边.边的方向是一个随机变量:3.概率为R3=1–R1-R2的边指向一个已存在概率与它的入度成比例的结点并从一个已存在的概率与它的出度成比例的结点出发。66维基百科的一个模型在每一步中我们增加一个结点与M条边.边的相关性速率方