复杂网络模型.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 优先连接 为了研究优先连接, 我们采用了由纽曼(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. Caldarelli Phys. Rev. E 74, 036116 (2006) M. E. J. Newman, The structure and function of complex networks（复杂网络的结构与功能）,数学学会评述 , 45(2): 167-256, 2003 参考文献 * * * * * * * * * * * * * * * * * * * * * 图理论 Graph G=(V,E) V = 顶点的集合 E = 边的集合 1 2 3 4 5 有向图 E={?1,2?, ?2,1? ?1,3?, ?3,2?, ?3,4?, ?4,5?} 无向图 1 2 3 4 5 结点i的度数dd(i) 与结点i相连的边数 度序列 [d(i),d(2),d(3),d(4),d(5)] [2,2,2,1,1] 度分布 [(1,2),(2,3)] 有向图 1 2 3 4 5 结点i的入度 指向结点i的边数 结点i的出度 以结点i为起始点的边数 入度序列 [1,2,1,1,1] 出度序列 [2,1,2,1,0] 路径 从结点i到结点j的路径: 一段连续的边 (有向或无向从结点i到结点j的连接) 路径长度: 路径上的边数 结点i和结点j是相连的 循环: 一段初始和结束结点是同一个结点的路径 1 2 3 4 5 1 2 3 4 5 最短路径 从结点i到结点j的最短路径 也被称作BFS路径, 或短线程路径 1 2 3 4 5 1 2 3 4 5 直径 途中距离最长的一条最短路径 1 2 3 4 5 1 2 3 4 5 无向图 1 2 3 4 5 连通图: 任意两个结点都存在连接的图 非连通图: 一个无连接的图 连通区域: 包含相连顶点的子图 完全连通图 Clique Kn 一个最多有 n(n-1)/2 条边的图（n为顶点数） 1 2 3 4 5 连通图 1 2 3 4 5 强连通图: 任意两个顶点之间存在一条路径 弱连通图: 边没有指向时图就是连通的 子图 1 2 3 4 5 子图: 给定V’ ? V, E’ ? E, 图 G’=(V’,E’) 就是G的一个子图. 生成子图: 给定 V’ ? V, E’ ? E 是V’中结点连成的边的集合. 则图 G’=(V’,E’), 是G的一个生成子图 树 没有循环的无向连通