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