复杂网络-总结的还可以.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)方法：每个节点都拥有一张表，它记录着该节点最近一次的相遇节点和相遇时间（tu,v）。时间变量toldest,n记录着在该网络中最“老”的一条边出现的时间，只有当一条边满足tu,vtoldest,n时才能被加入到该网络中。,27,3.1如何向复杂网络中加入一条边,T.Hossmann,T.Spyropoulos,andF.Legendre,KnowThyNeighbor:TowardsOptimalMappingofContactstoSocialGraphsforDTNRouting,inProc.INFOCOM,2010,pp.866-874.MF（MostFrequentContacts）方法：任意一对节点（u和v）都保存有一个计数器cu,v，该计数器记录着这个相遇在过去发生的次数。cleast,n记录着网络中具有最少次数的相遇的ID和次数统计值。加入网络中的边需满足cu,vcleast,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影响复杂网络拓