kok电子竞技

1、什么是网络?网络: 一个通过链接互相关联的实体的集合.互为朋友的人互相链接的计算机互相指向的网页互相作用的蛋白质什么是网络?网络: 一个通过链接互相关联的实体的集合.图在数学世界, 网络被称作图, 实体被称作结点, 而它们之间的链接被称作边。关于图的理论研究开始于18世纪，由数学家欧拉提出康尼斯堡桥梁问题在那之后图被更广泛深入地研究. 图在数学世界, 网络被称作图, 实体被称作结点, 而它们之间过去的网络图在过去被用作为现有网络制作模型 (举例来说. 有公交网络, 社会网络)通常这些网络都很小网络可以通过目视检查进行研究从而可以发现大量信息过去的网络图在过去被用作为现有网络制作模型 (举例来说

2、. 有现在的网络更多的、更大型的网络出现了科技进步的产物例如：互联网，网页我们收集更多、更好、更复杂数据的能力例如： 基因调控网络由数以千计、数以万计甚至数以亿计的结点所组成的网络不可能形象化现在的网络更多的、更大型的网络出现了因特网地图因特网地图因特网因特网网络的类型社会网络知识 (信息) 网络科学网络生物网络网络的类型社会网络社会网络链接表示社会中的互动熟人的网络协作网络演员的网络合作作者的网络导演的网络电话呼叫网络e-mail 网络IM 网络蓝牙网络性网络主页/博客网络社会网络链接表示社会中的互动知识（信息）网络结点代表信息, 链接是信息的联系引文网络 (有向无循环的)网络 (有向的)点

3、对点网络词网络基于信任的网络图形软件知识（信息）网络结点代表信息, 链接是信息的联系科学网络为商品分配所建的网络互联网路由器标准, AS 标准能量格航班网络电话网络交通网络公路，铁路，行人交通 科学网络为商品分配所建的网络生物网络网络代表生物系统蛋白质相互作用网络基因调控网络基因共同表达网络 代谢路径食物网神经网络生物网络网络代表生物系统理解大型的图关于现实生活网络的数据有哪些？?我们可以解释网络是怎样产生的吗？理解大型的图关于现实生活网络的数据有哪些？?关于网络性质的研究1999年左右Watts and Strogatz, Dynamics and small-world phenomeno

4、n（动力学和小世界现象）Faloutsos3, 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（现实网络中标度的出现）关于网络性质的研究1999年左右现实网络的性质大多数结点只有少数的邻居 (度), 但也有一些结点有很高的度数 (度的幂律分布)无标度网络如果一个结点 x 连接着 y和 z,那

5、么y 和 z 就很可能是连接的高聚类系数大多数结点平均只相距几条边的距离小世界网络各个不同领域的网络 (从因特网到生物网络) 有着相同的性质是否有可能有一个统一的基本生成过程？ 现实网络的性质大多数结点只有少数的邻居 (度), 但也有一些小世界网络例如：六度分离理论但是有超过六十亿人口生存在这个世界上！小世界网络例如：六度分离理论但是有超过六十亿人口生存在这个世小世界网络(a) 蛋白质 (b) 神经元 (c) 互联网小世界网络(a) 蛋白质 (b) 神经元 (c) 互生成随机图经典图形理论模型 (Erds-Renyi)每条边的独立产生概率为P很好的研究模型，但是:大多数顶点的度大致上相同两个结

6、点相连的概率与它们是否共有一个邻居结点无关平均路径短生成随机图经典图形理论模型 (Erds-Renyi)现实网络建模现实生活网络不是随机的我们是否可以定义一个模型，它能够产生与现实生活中相似的具有统计性能的图?一系列关于随机图的模型现实网络建模现实生活网络不是随机的网络的作用过程理解网络的结构为什么重要?流行病学: 病毒在无标度网络中传播地更快随机接种疫苗的结点无法正常工作，但有针对性的疫苗接种是非常有效的网络的作用过程理解网络的结构为什么重要?网络结构随机网络无标度网络网络结构随机网络无标度网络网络结构随机网络VS无标度网络网络结构随机网络VS无标度网络网络网络结构网络网络结构网络搜索第一代

7、搜索引擎: 万维网只是作为一个文件的集合因为垃圾邮件发送者，无实质内容的、非结构化的、以及无人监管的内容，增加了万维网的规模第二代搜索引擎: 作为一个网络的万维网应用链接描述文字技术以用来标注好的网页应该被更多的网页指向好的网页应该被更多的好网页指向PageRank 算法, Google!网络搜索第一代搜索引擎: 万维网只是作为一个文件的集合万维网万维网是一个文件之间互相指向的网络结点指网页而边指网页间的链接边是有指向的：链接可以从它们出发或者到达它们万维网万维网是一个文件之间互相指向的网络万维网万维网网络的未来网络现在看上去是这样的越来越多系统被网络模型化不同学科的科学家致力于对网络的研究

8、(物理学家,计算机学家, 数学家, 生物学家, 社会学家, 经济学家)还有许多问题尚未被理解.网络的未来网络现在看上去是这样的数学工具图理论概率论线性代数数学工具图理论图理论Graph G=(V,E)V = 顶点的集合E = 边的集合12345无向图E=(1,2),(1,3),(2,3),(3,4),(4,5)图理论Graph G=(V,E)12345无向图图理论Graph G=(V,E)V = 顶点的集合E = 边的集合12345有向图E=1,2, 2,1 1,3, 3,2, 3,4, 4,5图理论Graph G=(V,E)12345有向图无向图12345结点i的度数dd(i) 与结点i相连

9、的边数度序列d(i),d(2),d(3),d(4),d(5)2,2,2,1,1度分布(1,2),(2,3)无向图12345结点i的度数dd(i) 度序列度分布有向图12345结点i的入度指向结点i的边数结点i的出度以结点i为起始点的边数入度序列1,2,1,1,1出度序列 2,1,2,1,0有向图12345结点i的入度结点i的出度入度序列路径从结点i到结点j的路径: 一段连续的边 (有向或无向从结点i到结点j的连接)路径长度: 路径上的边数结点i和结点j是相连的循环: 一段初始和结束结点是同一个结点的路径1234512345路径从结点i到结点j的路径: 一段连续的边 (有向或无向从结最短路径从结

10、点i到结点j的最短路径也被称作BFS路径, 或短线程路径1234512345最短路径从结点i到结点j的最短路径1234512345直径途中距离最长的一条最短路径1234512345直径途中距离最长的一条最短路径1234512345无向图12345连通图: 任意两个结点都存在连接的图非连通图: 一个无连接的图连通区域: 包含相连顶点的子图无向图12345连通图: 任意两个结点都存在连接的图完全连通图Clique Kn一个最多有 n(n-1)/2 条边的图（n为顶点数）12345完全连通图Clique Kn12345连通图12345强连通图: 任意两个顶点之间存在一条路径弱连通图: 边没有指向时图

11、就是连通的连通图12345强连通图: 任意两个顶点之间存在一条路径弱连子图12345子图: 给定V V, E E, 图 G=(V,E) 就是G的一个子图.生成子图: 给定 V V, E E 是V中结点连成的边的集合. 则图 G=(V,E), 是G的一个生成子图子图12345子图: 给定V V, E E, 树没有循环的无向连通图12345树没有循环的无向连通图12345二分图集合V可以被分割成两个集合L和R的图, 而所有的边由L和R的结点连接而成，在集合L和R内部不存在边。二分图集合V可以被分割成两个集合L和R的图, 而所有的边由L线性代数邻接矩阵对称矩阵的无向图12345线性代数邻接矩阵123

12、45线性代数邻接矩阵非对称矩阵的无向图12345线性代数邻接矩阵12345特征值与特征向量若值 是矩阵A的特征值，且存在不为零向量的向量X，使得, Ax=x. 向量 x 是矩阵A的一个特征向量最大的特征向量被称为主特征值对应的特征向量被称为主特征向量对应最大值方向的变动特征值与特征向量若值 是矩阵A的特征值，且存在不为零向量的特征值特征值随机游动从一个结点开始,它的连接结点一律是随机的。平稳分布: 你访问结点i次数的分数, 随着随机游动经过边数的增逐渐加接近无穷大 如果一个图是强连通图, 它的平稳分布收敛与一个唯一的一个向量。随机游动从一个结点开始,它的连接结点一律是随机的。随机游动平稳分布:

13、 标准邻接矩阵左边的主特征向量x = xP无向图的度分布12345随机游动平稳分布: 标准邻接矩阵左边的主特征向量12345概率论概率空间: 给定一对,P: 样本空间P: 的子集的测量概率随机变量 X: R概率分布函数 PX=x数学期望概率论概率空间: 给定一对,P随机图的类随机图的类 被定义为一对 Gn,P ，Gn 是 所有大小为n的图的集合, P 是集合Gn的概率分布Erds-Renyi 图: 每条边出现的概率为 p当 p=1/2时, 我们得到一个统一的分布随机图的类随机图的类 被定义为一对 Gn,P ，Gn 是渐近符号对于两个函数 f(n)和g(n)若存在正数 c 和 N, 使得 f(n

14、) 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)渐近符号对于两个函数 f(n)和g(n)P 与 NPP: 在多项式时间内可以得到解决的一类问题NP: 在多项式时间内可以得到验证的一类问题NP-hard:至少与NP中任何问题一样困

15、难的问题P 与 NPP: 在多项式时间内可以得到解决的一类问题近似算法NP-优化问题: 给定一个问题的实例, 找到一个能将目标函数最小化或最大化的解决方法 。算法 A 是一个问题的系数c的近似值, 若对于每一个输入值xA(x) c OPT(x) (最小化问题)A(x) c OPT(x) (最大化问题)近似算法NP-优化问题: 给定一个问题的实例, 找到一个能将复杂网络的实际应用维基百科F. Colaiori, V. Servedio, G. Caldarelli, 交流物理学部., “La Sapienza”, 罗马 (意大利)D. Donato, S. Leonardi计算机科学学部., “

16、La Sapienza”, 罗马(意大利)L. Salete Buriol计算机科学学部., University of Porto Alegre, Rio Grande do Sul (巴西)复杂网络的实际应用维基百科F. Colaiori, V维基百科的复杂网络 网络描述 维基百科的统计分析 模型与解释维基百科的复杂网络 网络描述复杂网络模型复杂网络模型复杂网络模型维基百科是怎样工作的？多亏了维基科技, 一个用户可以 增加新的条目到百科全书中 修改已存在条目的内容 修改其链接在万维网中，每个用户只对从他的网页发出的指令负责 维基百科是怎样工作的？多亏了维基科技, 一个用户可以 维基百科中的

17、结点与边网络的边是百科全书的条目边是条目间的引用维基百科中的结点与边网络的边是百科全书的条目统计特性条目的数目在时间内成倍增长统计特性条目的数目在时间内成倍增长度分布度分布优先连接为了研究优先连接, 我们采用了由纽曼(2001)提出的方法 ，建立一个直方图 ，顶点的度的(k) ，每次获得新的边的阶数t，通过一个系数 n(k,t)/N(t)衡量它的贡献,其中:N(t) 是第t次结点的数量n(k,t) 是第t次度为k的结点的数量若(k) 有一个 approximatedly 线性行为, 则我们可能因此可以得出存在优先连接的结论优先连接为了研究优先连接, 我们采用了由纽曼(2001)提出优先连接圆:

18、 英语三角: 葡萄牙语填充: 入度白色: 出度优先连接圆: 英语维基百科的一个模型在每一步中我们增加一个结点与M条边. 边的方向是一个随机变量1. 概率为 R1 的边从新结点出发并指向一个已存在的结点，而这个结点被选择的概率与它的入度成比例维基百科的一个模型在每一步中我们增加一个结点与M条边. 边的维基百科的一个模型在每一步中我们增加一个结点与M条边. 边的方向是一个随机变量：2. 概率为 R2 的边指向一个新的结点并从一个已存在的结点出发 ，这个结点被选择的概率与它的出度成比例维基百科的一个模型在每一步中我们增加一个结点与M条边. 边的维基百科的一个模型在每一步中我们增加一个结点与M条边.

19、边的方向是一个随机变量:3. 概率为 R3 = 1 R1 - R2的边指向一个已存在概率与它的入度成比例的结点 并从一个已存在的概率与它的出度成比例的结点出发。维基百科的一个模型在每一步中我们增加一个结点与M条边. 边的相关性速率方程允许我们也计算入度-入度相关性相关性速率方程允许我们也计算入度-入度相关性缺乏相关性模型模型 “ 0.5%”缺乏相关性模型模型 “ 0.5%”Naf 解释假定: 入度= 人气出度= 质量若入度增长的概率由入度本身决定，这就意味着在维基百科中人气压倒了质量。就像在万维网中一样吗？Naf 解释假定: 群落结构维基百科显示了一个强有力的群落结构群落结构维基百科显示了一个

20、强有力的群落结构结论 维基百科条目组成了一个拥有优先连接、入度与出度成幂律分布和缺乏相关性的的复杂网络。优先连接解释了主要的统计特性 Naf 解释揭示出维基科技还不足以提供一个能出于对互联网的尊重更好的传播信息的万维网。 群落结构还需要更多理解结论 维基百科条目组成了一个拥有优先连接、入度与出度成幂律分 社会网络增长中的优先连接：网络百科全书维基 百科A.C., V. D. P. Servedio, F. Colaiori, L. S. Buriol, D. Donato, S. Leonardi, 和 G. CaldarelliPhys. Rev. E 74, 036116 (2006)M. E. J. Newman, The structure and function of complex networks（复杂网络的结构与功能）,数学学会评述 , 45(2): 167-256, 2003 参考文献M. E. J. Newman, The structure