最新复杂网络-总结的还可以PPT课件.ppt
复杂网络复杂网络-总结的还可以总结的还可以2 复杂网络复杂网络目目 录录 2 典型的复杂网络应用典型的复杂网络应用 3 复杂网络建模中的相关问题复杂网络建模中的相关问题41总结总结 91.1 复杂网络的概念复杂网络的概念无标度：无标度： Figure 3.无标度网络图101.2 复杂网络的特性复杂网络的特性复杂网络一般具有以下特性：小世界，集群，度，相似性，复杂网络一般具有以下特性：小世界，集群，度，相似性，介数。介数。 111.2 复杂网络的特性复杂网络的特性集群：集群即集聚程度集群：集群即集聚程度(clustering coefficient)的概念。的概念。 Figure 4.网络集群图121.2 复杂网络的特性复杂网络的特性度：度指的是网络中节点与节点关系（用网络中的边表达）度：度指的是网络中节点与节点关系（用网络中的边表达）的数量。的数量。 131.2 复杂网络的特性复杂网络的特性相似性：节点相似性：节点u和和v的相似性反应的是节点的相似性反应的是节点u和和v的相同邻居的相同邻居节点的情况。节点的情况。 Figure 5.节点相似性图141.2 复杂网络的特性复杂网络的特性介数：介数：节点节点u的介数含义为网络中所有的最短路径之中，经的介数含义为网络中所有的最短路径之中，经过过u的数量。它反映了节点的数量。它反映了节点u的影响力。的影响力。151.3 复杂网络的主要表现方面复杂网络的主要表现方面复杂网络简而言之即呈现高度复杂性的网络。其复杂性复杂网络简而言之即呈现高度复杂性的网络。其复杂性主要表现在以下几个方面：主要表现在以下几个方面： 161.3 复杂网络的主要表现方面复杂网络的主要表现方面结构复杂：表现在节点数目巨大，网络结构呈现多种不结构复杂：表现在节点数目巨大，网络结构呈现多种不同特征。同特征。 Figure 6.Internet 在自治系统层次上的拓扑图171.3 复杂网络的主要表现方面复杂网络的主要表现方面网络进化：表现在节点或连接的产生与消失。例如网络进化：表现在节点或连接的产生与消失。例如World World Wide WebWide Web，网页或链接随时可能出现或断开，导致网络，网页或链接随时可能出现或断开，导致网络结构不断发生变化。结构不断发生变化。 181.3 复杂网络的主要表现方面复杂网络的主要表现方面连接多样性：节点之间的连接权重存在诧异，且有可能连接多样性：节点之间的连接权重存在诧异，且有可能存在方向性。存在方向性。 Figure 7.药物复杂网络带权图191.3 复杂网络的主要表现方面复杂网络的主要表现方面 Figure 8.社会关系网201.3 复杂网络的主要表现方面复杂网络的主要表现方面动力学复杂性：节点集可能属于非线性动力学系统，例动力学复杂性：节点集可能属于非线性动力学系统，例如节点状态随时间发生复杂变化。如节点状态随时间发生复杂变化。 Figure 9.复杂网络随时间变化图211.3 复杂网络的主要表现方面复杂网络的主要表现方面节点多样性：复杂网络中的节点可以代表任何事物。例节点多样性：复杂网络中的节点可以代表任何事物。例如，人际关系构成的复杂网络节点代表单独个体，万维如，人际关系构成的复杂网络节点代表单独个体，万维网组成的复杂网络节点可以表示不同网页。网组成的复杂网络节点可以表示不同网页。 222. 典型的复杂网络应用典型的复杂网络应用 电力系统复杂网络的应用：电力系统复杂网络的应用： Figure 10.电力系统复杂网络受到随意攻击232. 典型的复杂网络应用典型的复杂网络应用 细胞复杂网络的应用：细胞复杂网络的应用： Figure 11.肺部细胞形成一个复杂网络242. 典型的复杂网络应用典型的复杂网络应用 因特网复杂网络的应用：因特网复杂网络的应用： Figure 12.因特网形成的复杂网络253 复杂网络建模中的相关问题复杂网络建模中的相关问题如何向复杂网络中加入一条边？如何向复杂网络中加入一条边？如何区分复杂网络中的一般连接和随机连接？如何区分复杂网络中的一般连接和随机连接？影响复杂网络拓扑结构的性能的因素是什么？影响复杂网络拓扑结构的性能的因素是什么？ 263.1 如何向复杂网络中加入一条边如何向复杂网络中加入一条边H.Dubois-Ferriere,M.Grossglauser,and M.Vetterli,“H.Dubois-Ferriere,M.Grossglauser,and M.Vetterli,“ Age matters:efficient route discovery in mobile ad Age matters:efficient route discovery in mobile ad hoc networks using encounter ages,”in ACM MobiHoc, hoc networks using encounter ages,”in ACM MobiHoc, 2003. 2003. MR(Most Recent Contacts) MR(Most Recent Contacts)方法：方法：每个节点都拥有一张表，它记录着该节点最近一次的相遇每个节点都拥有一张表，它记录着该节点最近一次的相遇节点和相遇时间（节点和相遇时间（t tu,vu,v）。）。时间变量时间变量t toldest,noldest,n记录着在该网络中最记录着在该网络中最“老老”的一的一条边出现的时间，只有当一条边满足条边出现的时间，只有当一条边满足t tu,vu,vttoldest,noldest,n 时才能被加入到该网络中。时才能被加入到该网络中。 273.1 如何向复杂网络中加入一条边如何向复杂网络中加入一条边T. Hossmann, T. Spyropoulos, and F. Legendre, T. Hossmann, T. Spyropoulos, and F. Legendre, Know Thy Neighbor: Towards Optimal Mapping of Know Thy Neighbor: Towards Optimal Mapping of Contacts to Social Graphs for DTN Routing, in Contacts to Social Graphs for DTN Routing, in Proc. INFOCOM, 2010, pp.866-874. Proc. INFOCOM, 2010, pp.866-874. MF MF（Most Frequent ContactsMost Frequent Contacts）方法：）方法：任意一对节点（任意一对节点（u u和和v v）都保存有一个计数器）都保存有一个计数器c cu,vu,v，该，该计数器记录着这个相遇在过去发生的次数。计数器记录着这个相遇在过去发生的次数。c cleast,nleast,n记录着网络中具有最少次数的相遇的记录着网络中具有最少次数的相遇的IDID和次和次数统计值。数统计值。加入网络中的边需满足加入网络中的边需满足cu,vcleast,ncu,vcleast,n（受密度限制）。（受密度限制）。 283.2 如何区分复杂网络中的一般连接和随机连接如何区分复杂网络中的一般连接和随机连接k-meansk-means谱聚类谱聚类模块模块Q Q函数函数 293.2 如何区分复杂网络中的一般连接和随机连接如何区分复杂网络中的一般连接和随机连接k-means:k-means: R.O.Duda,P.E.Hart,and D.G.Stork,Pattern Classification R.O.Duda,P.E.Hart,and D.G.Stork,Pattern Classification (2nd Edition). Wiley-Interscience,November 2000. (2nd Edition). Wiley-Interscience,November 2000. Figure 13.k-means算法示意图303.2 如何区分复杂网络中的一般连接和随机连接如何区分复杂网络中的一般连接和随机连接k-meansk-means谱聚类谱聚类模块模块Q Q函数函数 313.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么T. Hossmann, T. Spyropoulos, and F. Legendre, T. Hossmann, T. Spyropoulos, and F. Legendre, Know Thy Neighbor: Towards Optimal Mapping of Know Thy Neighbor: Towards Optimal Mapping of Contacts to Social Graphs for DTN Routing, in Contacts to Social Graphs for DTN Routing, in Proc. INFOCOM, 2010, pp.866-874. Proc. INFOCOM, 2010, pp.866-874. 网络场景网络场景密度密度 323.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么网络场景网络场景: :分为合成相遇过程（分为合成相遇过程（Synthetic contact Synthetic contact processesprocesses）和真实移动轨迹（）和真实移动轨迹（Real mobility tracesReal mobility traces）。）。 333.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么合成相遇过程：合成相遇过程：SWSW模型和模型和CAVECAVE模型。模型。 343.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么SW:1998SW:1998年，美国康奈尔大学的年，美国康奈尔大学的WattsWatts和和StrogatzStrogatz在在NatureNature上著文建立了第一个复杂网络模型，即上著文建立了第一个复杂网络模型，即“小世界网络模小世界网络模型型”。 Figure 14.SW模型(1)353.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么SW:SW: Figure 15.SW模型(2)363.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么CAVE:CAVE:与与SWSW模型类似，只不过模型类似，只不过CAVECAVE模型首先会将拥有模型首先会将拥有N N个节个节点的网络划分成具有相同点的网络划分成具有相同k k个近邻节点的节点所组成的社区个近邻节点的节点所组成的社区 （就相当于是一种小的洞穴，因此取名为（就相当于是一种小的洞穴，因此取名为CAVECAVE模型）。这模型）。这样，不同的社区代表不同的节点，这就有别于样，不同的社区代表不同的节点，这就有别于SWSW模型（因模型（因为为SWSW模型并没有严格地将节点划分成社区），模型并没有严格地将节点划分成社区），SWSW模型的社模型的社区有可能是重叠的。除此之外，边的重连和区有可能是重叠的。除此之外，边的重连和SWSW模型相似。模型相似。 373.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么真实移动轨迹：真实移动轨迹：MIT,INFO,ETHMIT,INFO,ETH。 383.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么MIT:MIT:麻省理工真实挖掘麻省理工真实挖掘MIT Reality Mining;MIT Reality Mining;通过传感器收通过传感器收集人们社会行为的现实信息，以获取知识。譬如，从人们集人们社会行为的现实信息，以获取知识。譬如，从人们的谈话的内容，亲近，时空位置等信息，分析其社会行为。的谈话的内容，亲近，时空位置等信息，分析其社会行为。就像现在许多人身上都有一个智能手机，网络。一个可以就像现在许多人身上都有一个智能手机，网络。一个可以穿戴的传感器贴在身上，别在腰间，那是很容易的。从这穿戴的传感器贴在身上，别在腰间，那是很容易的。从这些传感器传出来的现实信息，可以挖掘出主要两方面的知些传感器传出来的现实信息，可以挖掘出主要两方面的知识：识：人们的社会行为人们的社会行为人的健康状况。人的健康状况。 393.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么INFO:INFOCOMINFO:INFOCOM是是IEEEIEEE组织在通信网络领域中的旗舰型会议，组织在通信网络领域中的旗舰型会议，也是目前国际通信网络领域的一大标志性会议也是目前国际通信网络领域的一大标志性会议。该实验是。该实验是将一种小型的蓝牙设备部署到参加参加将一种小型的蓝牙设备部署到参加参加20052005年年INFOCOMINFOCOM会议会议的的5454为参与者身上，从而获取人们的社会行为。为参与者身上，从而获取人们的社会行为。 403.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么ETH:ETHETH:ETH轨迹，是瑞士科技城研究中心的研究成果，该实验轨迹，是瑞士科技城研究中心的研究成果，该实验是在办公环境中，给二十位实验者身上装有由是在办公环境中，给二十位实验者身上装有由IEEE IEEE 802.11b802.11b无线接口支持的个人数字助理无线接口支持的个人数字助理PDAPDA，这二十位实验，这二十位实验者就相当于者就相当于ad hocad hoc网络中的二十个节点，他们都在研究所网络中的二十个节点，他们都在研究所的同一楼层上工作的同一楼层上工作。然后以此来观察随着时间所形成的网。然后以此来观察随着时间所形成的网络拓扑结构。络拓扑结构。 413.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么我们可以看出，我们可以看出，MIT,INFO,ETHMIT,INFO,ETH是三种通过不同手段对真实是三种通过不同手段对真实的节点移动轨迹的追踪过程的节点移动轨迹的追踪过程。 Figure 16.REAL MOBILITY TRACES CHARACTERISTICS423.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么不同的协议在不同的密度下的性能表现：不同的协议在不同的密度下的性能表现： Figure 17.不同协议在不同的密度下的性能表现433.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么SimBetSimBet： E.M.Daly and M.Haahr,“Social network analysis for E.M.Daly and M.Haahr,“Social network analysis for routing in disconnected delay-tolerant manets,” in routing in disconnected delay-tolerant manets,” in ACM MobiHoc,2007. ACM MobiHoc,2007. 协议思想：当前携带消息的节点首先判断与它相遇的节点是协议思想：当前携带消息的节点首先判断与它相遇的节点是否和它属于同一社区，如果是，则比较两个节点与目的节点否和它属于同一社区，如果是，则比较两个节点与目的节点的相似度，如果相遇的节点与目的节点的相似度高，则将消的相似度，如果相遇的节点与目的节点的相似度高，则将消息转发给这个相遇的节点；否则，将消息保留在该社区内介息转发给这个相遇的节点；否则，将消息保留在该社区内介数最高的节点。数最高的节点。 443.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么SimBetSimBet： Figure 18.SimBet转发机制453.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么Bubble RapBubble Rap： P.Hui,J Crowcroft,and E.Yoneki,“Bubble rap:Social-P.Hui,J Crowcroft,and E.Yoneki,“Bubble rap:Social-based forwarding in delay tolerant networks,”in ACM based forwarding in delay tolerant networks,”in ACM MobiHoc,2008.MobiHoc,2008. 协议思想：与协议思想：与SimBetSimBet相比，有两点不同之处：相比，有两点不同之处：社区的识别社区的识别不是通过相似性，而是通过集体检测的算法不是通过相似性，而是通过集体检测的算法消息在社区内消息在社区内的转发是通过比较节点在社区内的介数，而不是相似性。的转发是通过比较节点在社区内的介数，而不是相似性。集体检测：集体检测：K-CLIQUEK-CLIQUE和和WNA(Weighted Network Analysis)WNA(Weighted Network Analysis) 463.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么K-CLIQUE:K-CLIQUE: Figure 19.Communities based on contact durations with weightthreshold = 388800s (4.5days), 648000s (7.5days) and k=3,4 473.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么WNA(Weighted Network Analysis):WNA(Weighted Network Analysis):基本思想基本思想: :对于一个划分成多个社区的网络来说，我们计算出对于一个划分成多个社区的网络来说，我们计算出该网络的模块化的值该网络的模块化的值Q Q。该值可以用来衡量对网络的分割是否。该值可以用来衡量对网络的分割是否准确。准确。如果计算出的如果计算出的Q Q值越低，则说明该划分下的社区间的界限比较值越低，则说明该划分下的社区间的界限比较模糊，该划分并不是最优的划分方案；模糊，该划分并不是最优的划分方案；Q Q值越高，则说明该划值越高，则说明该划分方案是较为优化的方案。分方案是较为优化的方案。Q Q值在值在0.30.3左右是较为理想的社区划分方案。左右是较为理想的社区划分方案。 483.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么不同的协议在不同的密度下的性能表现：不同的协议在不同的密度下的性能表现： Figure 20.不同协议在不同的密度下的性能表现(1)493.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么不同的协议在不同的密度下的性能表现：不同的协议在不同的密度下的性能表现： Figure 21.不同协议在不同的密度下的性能表现(2)503.3 影响复杂网络拓扑结构的性能的因素是什么影响复杂网络拓扑结构的性能的因素是什么密度：只要某个社区的密度超过阈值，停止该社区的聚合。密度：只要某个社区的密度超过阈值，停止该社区的聚合。聚合网络的映射函数聚合网络的映射函数f f：聚合网络密度的计算公式：聚合网络密度的计算公式：其中，其中，|E|=V(V-1)/2|E|=V(V-1)/2 514 总结总结 Thank you
