复杂网络-总结的还可以.ppt

复杂网络 2 复杂网络 目录 典型的复杂网络应用 复杂网络建模中的相关问题 总结 3 1复杂网络 这部分将从三个方面介绍复杂网络 概念 特性 主要表现方面 4 1 1复杂网络的概念 我国著名科学家钱学森给出了复杂网络一个较严格的定义 具有自组织 自相似 吸引子 小世界 无标度中部分或全部性质的网络称为复杂网络 5 1 1复杂网络的概念 自组织 如果一个系统靠外部指令而形成组织 就是他组织 如果不存在外部指令 系统按照相互默契的某种规则 各尽其责而又协调地自动地形成有序结构 就是自组织 Figure1 网络自组织 6 1 1复杂网络的概念 自相似 一种形状的每一部分在几何上相似于整体 一般对分形而言 7 1 1复杂网络的概念 吸引子 相空间 可以表示出一个系统所有可能状态的空间 中稳定的不动点集 海纳百川 大海就是百川的吸引子落叶归根 树根就是叶子的吸引子热力学系统的平衡态就是该系统的吸引子 8 1 1复杂网络的概念 小世界 Figure2 小世界网络图 9 1 1复杂网络的概念 无标度 Figure3 无标度网络图 10 1 2复杂网络的特性 复杂网络一般具有以下特性 小世界 集群 度 相似性 介数 11 1 2复杂网络的特性 集群 集群即集聚程度 clusteringcoefficient 的概念 Figure4 网络集群图 12 1 2复杂网络的特性 度 度指的是网络中节点与节点关系 用网络中的边表达 的数量 13 1 2复杂网络的特性 相似性 节点u和v的相似性反应的是节点u和v的相同邻居节点的情况 Figure5 节点相似性图 14 1 2复杂网络的特性 介数 节点u的介数含义为网络中所有的最短路径之中 经过u的数量 它反映了节点u的影响力 15 1 3复杂网络的主要表现方面 复杂网络简而言之即呈现高度复杂性的网络 其复杂性主要表现在以下几个方面 16 1 3复杂网络的主要表现方面 结构复杂 表现在节点数目巨大 网络结构呈现多种不同特征 Figure6 Internet在自治系统层次上的拓扑图 17 1 3复杂网络的主要表现方面 网络进化 表现在节点或连接的产生与消失 例如WorldWideWeb 网页或链接随时可能出现或断开 导致网络结构不断发生变化 18 1 3复杂网络的主要表现方面 连接多样性 节点之间的连接权重存在诧异 且有可能存在方向性 Figure7 药物复杂网络带权图 19 1 3复杂网络的主要表现方面 Figure8 社会关系网 20 1 3复杂网络的主要表现方面 动力学复杂性 节点集可能属于非线性动力学系统 例如节点状态随时间发生复杂变化 Figure9 复杂网络随时间变化图 21 1 3复杂网络的主要表现方面 节点多样性 复杂网络中的节点可以代表任何事物 例如 人际关系构成的复杂网络节点代表单独个体 万维网组成的复杂网络节点可以表示不同网页 22 2 典型的复杂网络应用 电力系统复杂网络的应用 Figure10 电力系统复杂网络受到随意攻击 23 2 典型的复杂网络应用 细胞复杂网络的应用 Figure11 肺部细胞形成一个复杂网络 24 2 典型的复杂网络应用 因特网复杂网络的应用 Figure12 因特网形成的复杂网络 25 3复杂网络建模中的相关问题 如何向复杂网络中加入一条边 如何区分复杂网络中的一般连接和随机连接 影响复杂网络拓扑结构的性能的因素是什么 26 3 1如何向复杂网络中加入一条边 H Dubois Ferriere M Grossglauser andM Vetterli Agematters efficientroutediscoveryinmobileadhocnetworksusingencounterages inACMMobiHoc 2003 MR MostRecentContacts 方法 每个节点都拥有一张表 它记录着该节点最近一次的相遇节点和相遇时间 t u v 时间变量t oldest n 记录着在该网络中最 老 的一条边出现的时间 只有当一条边满足t u v t oldest n 时才能被加入到该网络中 27 3 1如何向复杂网络中加入一条边 T Hossmann T Spyropoulos andF Legendre KnowThyNeighbor TowardsOptimalMappingofContactstoSocialGraphsforDTNRouting inProc INFOCOM 2010 pp 866 874 MF MostFrequentContacts 方法 任意一对节点 u和v 都保存有一个计数器c u v 该计数器记录着这个相遇在过去发生的次数 c least n 记录着网络中具有最少次数的相遇的ID和次数统计值 加入网络中的边需满足c u v c least n 受密度限制 28 3 2如何区分复杂网络中的一般连接和随机连接 k means谱聚类模块Q函数 29 3 2如何区分复杂网络中的一般连接和随机连接 k means R O Duda P E Hart andD G Stork PatternClassification 2ndEdition Wiley Interscience November2000 Figure13 k means算法示意图 30 3 2如何区分复杂网络中的一般连接和随机连接 k means谱聚类模块Q函数 31 3 3影响复杂网络拓扑结构的性能的因素是什么 T Hossmann T Spyropoulos andF Legendre KnowThyNeighbor TowardsOptimalMappingofContactstoSocialGraphsforDTNRouting inProc INFOCOM 2010 pp 866 874 网络场景密度 32 3 3影响复杂网络拓扑结构的性能的因素是什么 网络场景 分为合成相遇过程 Syntheticcontactprocesses 和真实移动轨迹 Realmobilitytraces 33 3 3影响复杂网络拓扑结构的性能的因素是什么 合成相遇过程 SW模型和CAVE模型 34 3 3影响复杂网络拓扑结构的性能的因素是什么 SW 1998年 美国康奈尔大学的Watts和Strogatz在Nature上著文建立了第一个复杂网络模型 即 小世界网络模型 Figure14 SW模型 1 35 3 3影响复杂网络拓扑结构的性能的因素是什么 SW Figure15 SW模型 2 36 3 3影响复杂网络拓扑结构的性能的因素是什么 CAVE 与SW模型类似 只不过CAVE模型首先会将拥有N个节点的网络划分成具有相同k个近邻节点的节点所组成的社区 就相当于是一种小的洞穴 因此取名为CAVE模型 这样 不同的社区代表不同的节点 这就有别于SW模型 因为SW模型并没有严格地将节点划分成社区 SW模型的社区有可能是重叠的 除此之外 边的重连和SW模型相似 37 3 3影响复杂网络拓扑结构的性能的因素是什么 真实移动轨迹 MIT INFO ETH 38 3 3影响复杂网络拓扑结构的性能的因素是什么 MIT 麻省理工真实挖掘MITRealityMining 通过传感器收集人们社会行为的现实信息 以获取知识 譬如 从人们的谈话的内容 亲近 时空位置等信息 分析其社会行为 就像现在许多人身上都有一个智能手机 网络 一个可以穿戴的传感器贴在身上 别在腰间 那是很容易的 从这些传感器传出来的现实信息 可以挖掘出主要两方面的知识 人们的社会行为 人的健康状况 39 3 3影响复杂网络拓扑结构的性能的因素是什么 INFO INFOCOM是IEEE组织在通信网络领域中的旗舰型会议 也是目前国际通信网络领域的一大标志性会议 该实验是将一种小型的蓝牙设备部署到参加参加2005年INFOCOM会议的54为参与者身上 从而获取人们的社会行为 40 3 3影响复杂网络拓扑结构的性能的因素是什么 ETH ETH轨迹 是瑞士科技城研究中心的研究成果 该实验是在办公环境中 给二十位实验者身上装有由IEEE802 11b无线接口支持的个人数字助理PDA 这二十位实验者就相当于adhoc网络中的二十个节点 他们都在研究所的同一楼层上工作 然后以此来观察随着时间所形成的网络拓扑结构 41 3 3影响复杂网络拓扑结构的性能的因素是什么 我们可以看出 MIT INFO ETH是三种通过不同手段对真实的节点移动轨迹的追踪过程 Figure16 REALMOBILITYTRACESCHARACTERISTICS 42 3 3影响复杂网络拓扑结构的性能的因素是什么 不同的协议在不同的密度下的性能表现 Figure17 不同协议在不同的密度下的性能表现 43 3 3影响复杂网络拓扑结构的性能的因素是什么 SimBet E M DalyandM Haahr Socialnetworkanalysisforroutingindisconnecteddelay tolerantmanets inACMMobiHoc 2007 协议思想 当前携带消息的节点首先判断与它相遇的节点是否和它属于同一社区 如果是 则比较两个节点与目的节点的相似度 如果相遇的节点与目的节点的相似度高 则将消息转发给这个相遇的节点 否则 将消息保留在该社区内介数最高的节点 44 3 3影响复杂网络拓扑结构的性能的因素是什么 SimBet Figure18 SimBet转发机制 45 3 3影响复杂网络拓扑结构的性能的因素是什么 BubbleRap P Hui JCrowcroft andE Yoneki Bubblerap Social basedforwardingindelaytolerantnetworks inACMMobiHoc 2008 协议思想 与SimBet相比 有两点不同之处 社区的识别不是通过相似性 而是通过集体检测的算法 消息在社区内的转发是通过比较节点在社区内的介数 而不是相似性 集体检测 K CLIQUE和WNA WeightedNetworkAnalysis 46 3 3影响复杂网络拓扑结构的性能的因素是什么 K CLIQUE Figure19 Communitiesbasedoncontactdurationswithweightthreshold 388800s 4 5days 648000s 7 5days andk 3 4 47 3 3影响复杂网络拓扑结构的性能的因素是什么 WNA WeightedNetworkAnalysis 基本思想 对于一个划分成多个社区的网络来说 我们计算出该网络的模块化的值Q 该值可以用来衡量对网络的分割是否准确 如果计算出的Q值越低 则说明该划分下的社区间的界限比较模糊 该划分并不是最优的划分方案 Q值越高 则说明该划分方案是较为优化的方案 Q值在0 3左右是较为理想的社区划分方案 48 3 3影响