复杂网络概述ppt课件.ppt

复杂网络概述 王驰 1 为什么要研究复杂网络 关于复杂性 大量个体 更典型的是具有适应性的主体 所组成的复杂系统 在没有中心控制 非完全信息 仅仅存在局域相互作用的条件下 通过个体之间的非线性相互作用 可以在宏观层次上涌现出一定的结构和功能 2 为什么要研究复杂网络 复杂系统不能够用分析的方法去研究 必须考虑个体之间的关联和作用 复杂网络是构成复杂系统的基本结构 每个复杂系统都可以看作是单元或个体之间的相互作用网络 复杂网络在刻画复杂性方面的重要性是由于结构决定功能的 理解复杂系统的行为应该从理解系统相互作用网络的拓扑结构开始 网络拓扑结构的信息是构建系统模型 研究系统性质和功能的基础 3 为什么要研究复杂网络 复杂网络是研究复杂系统的一种角度和方法 它关注系统中个体相互关联的作用的拓扑结构 是理解复杂系统性质和功能的基础 4 复杂网络研究所关心的问题 如何定量刻画复杂网络 网络结构的描述及其性质网络是如何发展成现在这种结构的 网络演化模型网络特定结构的后果是什么 网络结构的鲁棒性网络上的动力学行为和过程 5 复杂网络的表示方法 航空网 道路交通网 城市公共交通网 6 复杂网络的表示方法 WWW 电力网 因特网 7 复杂网络的表示方法 图提供了一种用抽象的点和线表示各种实际网络的统一方法 因而成为目前研究复杂网络的一种共同的语言 例子 国际互联网 节点 路由器连接 光纤 科学引用网 节点 文章连接 文章引用 社会网络 节点 个体人连接 人际关系 8 复杂网络的表示方法 按照图中的边是否有向和是否有权 可以有四种类型的图 9 复杂网络的表示方法 图的计算机表示 邻接矩阵邻接矩阵描述了节点与节点之间的邻接关系 通常会用一个方阵A来表示 方阵中的元素用aij表示 10 复杂网络的表示方法 图的计算机表示 11 一 复杂网络的定义 钱学森给出了复杂网络的一个较严格的定义 具有自组织 自相似 吸引子 小世界 无标度中部分或全部性质的网络称为复杂网络 12 一 复杂网络的定义 小世界特性又被称之为是六度空间理论或者是六度分割理论 小世界特性指出 社交网络中的任何一个成员和任何一个陌生人之间所间隔的人不会超过六个 小世界特性 13 一 复杂网络的定义 无标度特性 现实世界的网络大部分都不是随机网络 少数的节点往往拥有大量的连接 而大部分节点却很少 节点的度数分布符合幂率分布 而这就被称为是网络的无标度特性 将度分布符合幂律分布的复杂网络称为无标度网络 14 一 复杂网络的定义 社团结构特性 人以类聚 物以群分 复杂网络中的节点往往也呈现出集群特性 例如 社会网络中总是存在熟人圈或朋友圈 其中每个成员都认识其他成员 集群程度的意义是网络集团化的程度 这是一种网络的内聚倾向 连通集团概念反映的是一个大网络中各集聚的小网络分布和相互联系的状况 例如 它可以反映这个朋友圈与另一个朋友圈的相互关系 15 二 复杂网络中的基本概念 度 degree 节点i的度ki定义为与该节点连接的其他节点的数目 对于有向网络分为出度和入度 直观上看 一个节点的度越大就意味着这个节点在某种意义上越 重要 能力大 网络的平均度 网络中所有节点的度和的平均值 记作 并且 2M N M为网络中的边数 N为节点数 度分布函数p k 随机选定节点的度恰好为k的概率 16 二 复杂网络中的基本概念 度分布函数p k 随机选定节点的度恰好为k的概率 17 二 复杂网络中的基本概念 节点的聚类系数 簇系数 在简单图中 设与节点v相邻的节点有ki个 则节点v的聚类系数定义为这ki个节点之间存在边数Ei与总的可能边数ki ki 1 2之比 即 Ci 2Ei ki ki 1 包含节点i的三角形数目 以节点i为中心的连通三元组的数目 网络的聚类系数C 所有节点i的聚类系数Ci的平均值 0 C 1 C 0 网络中所有节点都是孤立点C 1 网络中任意节点间都有边相连 网络节点间联系的密切程度 体现网络的凝聚力 18 二 复杂网络中的基本概念 节点的介数 边的介数 式中 Njl表示节点vj和vl之间的最短路径条数 Njl i 表示节点vj和vl之间的最短路径经过节点vi的条数 式中 Nlm表示节点vl和vm之间的最短路径条数 Nlm eij 表示节点vl和vm之间的最短路径经过边eij的条数 19 二 复杂网络中的基本概念 许多大规模的实际网络都具有明显的聚类效应 事实上 在很多类型的网络 如社会关系网络 中 你的朋友同时也是朋友的概率会随着网络规模的增加而趋向于某个非零常数 即当N 时 C O 1 这意味着这些实际的复杂网络并不是完全随机的 而是在某种程度上具有类似于社会关系网络中 物以类聚 人以群分 的特性 20 二 复杂网络中的基本概念 最短路径 Shortestpath 两个节点之间边数最少的路径 最短路径的长度称为两点间的距离 用dij 平均路径长度 特征路径长度 L 所有节点对之间的距离的平均值 研究发现 尽管许多实际复杂网络的节点数巨大 网络的平均路径长度却小的惊人 小世界效应 21 三 复杂网络的结构模型 四种结构模型 规则网络随机网络小世界网络无标度网络 22 三 复杂网络的结构模型 规则网络 a 全局耦合网络 b 最近邻耦合网络 c 星形耦合网络 23 三 复杂网络的结构模型 规则网络拓扑性质 最近邻耦合网络 一般情况下 聚集系数较大 平均最短路径较长 24 三 复杂网络的结构模型 随机网络 1 初始化 给定N个节点以及连边概率p 2 随机连边 选择一对没有边相连的不同的节点 生成一个随机数r 如果r p 那么在这对节点之间添加一条边 否则就不添加边 重复步骤 直到所有的节点对都被选择过一次 25 三 复杂网络的结构模型 随机网络拓扑性质 度分布 边数分布 聚类系数 C p N 1 平均路径长度 lnN ln 26 三 复杂网络的结构模型 小世界网络 27 三 复杂网络的结构模型 小世界网络 C p 平均聚集系数L p 平均最短路径 28 PageRank算法 通过人工进行网页分类并整理出高质量的网站 计算用户查询关键词与网页内容的相关程度来返回搜索结果 算法来源 29 PageRank算法 谷歌的两位创始人 当时还是美国斯坦福大学研究生的佩奇和布林开始了对网页排序问题的研究 借鉴了学术界评判学术论文重要性的通用方法 那就是看论文的引用次数 由此想到网页的重要性也可以根据这种方法来评价 30 PageRank算法 如果一个网页被很多其他网页链接到的话说明这个网页比较重要 也就是PageRank值会相对较高 如果一个PageRank值很高的网页链接到一个其他的网页 那么被链接到的网页的PageRank值会相应地因此而提高 31 PageRank算法 算法原理 PageRank算法总的来说就是预先给每个网页一个PR值 PR值物理意义上为一个网页被访问概率 所以一般是1 N 其中N为网页总数 另外 所有网页的PR值的总和为1 预先给定PR值后 通过不断迭代 直至达到平稳分布为止 PR A PR B 2 PR C 32 PageRank算法 算法证明 于是计算PR值的过程就变成了一个Markov过程 那么PageRank算法的证明也就转为证明Markov过程的收敛性证明 如果这个Markov过程收敛 那么存在 且与P0的选取无关 33 PageRank算法 算法证明 状态转移矩阵A需要满足 1 A为随机矩阵 2 A是不可约的 3 A是非周期的 34 作战体系节点重要性分析 机械化战争时代 在通信手段和指挥控制手段受限的情况下 作战体系 形成了一种树状结构 随着指挥信息系统的功能越来越强 作战体系任何两个节点之间均可以根据需要建立联系 逐步形成网络化结构 35 作战体系节点重要性分析 作战体系结构的网络描述 依据复杂网络理论 可以定义作战体系由节点集合V和边集合E组成的图G V E 其中 V v1 v2 vn 代表组成作战体系的指挥控制节点 预警侦察节点 包括战场态势信息源节点和目标信息源节点 攻防交战节点等 E e1 e2 em 代表节点之间信息传递关系 36 作战体系节点重要性分析 作战体系节点重要性的度量指标 度指标 描述在静态网络中节点所产生的直接影响力 介数指标 描述网络中最短路径通过某节点的数量 反映的是该节点在网络中的枢纽性 紧密度指标 紧密度指标用于刻画网络中的节点通过网络到达网络中其它节点的难易程度 37 作战体系节点重要性分析 作战体系受损程度的度量指标 38 作战体系节点重要性分析 重要性指标