复杂网络的某些性质研究及其应用
发布时间：2018-09-18 20:40
【摘要】：自从Watts,Strogatz 1998年发现真实网络的小世界特性以来,复杂网络融合了图论、工程数学、计算机理论、社会科学等学科的有关理论与成果,已成为了一门单独的学科。经过十多年的研究,科学家们已经发现了一些典型复杂网络模型如小世界网络模型、无标度网络模型、确定性小世界网络模型等,同时也发现了这些典型网络模型的一些主要特性。本文围绕复杂网络的小世界现象,针对典型复杂网络模型重点研究了网络节点度序列长度特性、电阻距离特性及其应用;基于代数图论中的凯莱图(Cayley)模型在随机化加边后也同样具有复杂网络的小世界特性,论文结合无线传感器网络和数据中心网络的应用需求,同时研究了基于代数图论的具有小世界特性的复杂网络模型及应用。论文主要成果如下:(1)在肖文俊等人提出复杂网络度序列长度新特性的基础上,论文从理论上证明了具有扩展幂律分布、泊松分布、指数分布的复杂网络模型的度序列长度的新特性:即度序列长度l与log_2N是同级别的结论,进一步完善了肖文俊等人的结论。实验仿真结果及现实网络的数据验证了该结论的有效性。该结论从理论上解释了为什么现实世界的网络直径不大的问题,可以作为复杂网络的基本特性之一,同时论文提出了基于复杂网络的度序列长度的复杂网络模型。针对复杂网络的搜索问题,论文完成了最短路径算法和最大度算法的仿真实验,结果表明在复杂网络中基于最大度的搜索算法相比基于最短路径的搜索算法更有效。(2)论文研究了复杂网络中的电阻距离特性及其在社团划分中应用的需求,提出了结合节点中心性指标与电阻距离的社团划分算法。论文选择了节点度中心性、接近度指标、特征向量、聚类系数及最短路径等5类节点中心性指标,基于模拟网络、空手道网络和宽吻海豚网络等三种网络进行了仿真实验,随后论文将电阻距离引入到Kernighan-Lin(KL)算法和Fast Newman(FN)算法中,实验结果表明结合节点度中心性与电阻距离的社团划分算法及基于电阻距离的KL算法能准确划分三个实验网络的社团结构,但其它基于电阻距离的社团划分算法只能正确划分部分实验网络的社团结构,存在一定的误差。(3)基于复杂网络模型的小世界特性的启发,论文结合基于代数图论中的Cayley理论与复杂网络理论,针对无线传感器网络节点动态变化及虚拟路由的实际需求,提出了具有小世界特性的CayleyDHT模型,并在该模型的基础上提出了CayleyDHTVCP路由协议,仿真实验表明该协议具有较好路由的效率和鲁棒性。(4)针对目前数据中心网络需要利用廉价设备构建的趋势,论文分析了现有数据中心网络结构的优缺点,应用基于代数图论中的Cayley图与复杂网络理论,提出了基于数据中心网络的C~3Cube模型,并在此模型的基础上,提出了基于C~3Cube路由协议及容错协议,仿真实验表明该协议的有效性,可以有效地解决利用廉价设备构建数据中心网络的问题。
[Abstract]:Since Watts and Strogatz discovered the small-world properties of real networks in 1998, complex networks have become a separate discipline, fusing the theories and achievements of graph theory, engineering mathematics, computer theory, social science and other disciplines. Bounded network model, scale-free network model, deterministic small-world network model and so on, and some main characteristics of these typical network models are also found. The Cayley model in number graph theory also has the small-world characteristics of complex networks after randomized edge addition. This paper combines the application requirements of wireless sensor networks and data center networks, and studies the complex network model with small-world characteristics based on algebraic graph theory and its application. On the basis of the new characteristics of degree sequence length proposed by Wen Jun et al, this paper theoretically proves the new characteristics of degree sequence length of complex network model with extended power law distribution, Poisson distribution and exponential distribution: that the length of degree sequence L is the same level as log_2N, which further perfects the conclusion of Xiao Wenjun et al. The validity of this conclusion is validated by real results and real network data. This conclusion explains why the diameter of real world network is not large and can be used as one of the basic characteristics of complex network. At the same time, a complex network model based on the length of degree sequence of complex network is proposed. The simulation results show that the algorithm based on maximum path is more effective than the algorithm based on shortest path in complex networks. (2) The resistance distance characteristics in complex networks and its application requirements in community partitioning are studied, and the joint nodes are proposed. Five kinds of node centrality indexes, such as node centrality, proximity index, eigenvector, clustering coefficient and shortest path, are selected in this paper. Three kinds of network are simulated based on Simulation network, karate network and bottlenose dolphin network. In Kernighan-Lin (KL) algorithm and Fast Newman (FN) algorithm, experimental results show that the community partitioning algorithm based on nodal centrality and resistance distance and KL algorithm based on resistance distance can accurately partition the community structure of three experimental networks, but other community partitioning algorithms based on resistance distance can only partition part of the experimental network correctly. (3) Inspired by the small-world characteristics of complex network model, this paper proposes a Cayley DHT model with small-world characteristics, which combines the Cayley theory based on algebraic graph theory with the complex network theory, aiming at the dynamic changes of wireless sensor network nodes and the actual needs of virtual routing. A Cayley DHTVCP routing protocol is proposed on the basis of the proposed model, and the simulation results show that the protocol has good routing efficiency and robustness. (4) Aiming at the trend that the current data center network needs to use cheap equipment to build, this paper analyzes the advantages and disadvantages of the existing data center network structure, and applies the Cayley diagram based on algebraic graph theory and complex network. Based on the network theory, a C~3Cube model based on data center network is proposed. Based on this model, a C~3Cube routing protocol and fault-tolerant protocol are proposed. Simulation results show that the protocol is effective and can effectively solve the problem of constructing data center network with cheap equipment.
【学位授予单位】：华南理工大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5
[Abstract]:Since Watts and Strogatz discovered the small-world properties of real networks in 1998, complex networks have become a separate discipline, fusing the theories and achievements of graph theory, engineering mathematics, computer theory, social science and other disciplines. Bounded network model, scale-free network model, deterministic small-world network model and so on, and some main characteristics of these typical network models are also found. The Cayley model in number graph theory also has the small-world characteristics of complex networks after randomized edge addition. This paper combines the application requirements of wireless sensor networks and data center networks, and studies the complex network model with small-world characteristics based on algebraic graph theory and its application. On the basis of the new characteristics of degree sequence length proposed by Wen Jun et al, this paper theoretically proves the new characteristics of degree sequence length of complex network model with extended power law distribution, Poisson distribution and exponential distribution: that the length of degree sequence L is the same level as log_2N, which further perfects the conclusion of Xiao Wenjun et al. The validity of this conclusion is validated by real results and real network data. This conclusion explains why the diameter of real world network is not large and can be used as one of the basic characteristics of complex network. At the same time, a complex network model based on the length of degree sequence of complex network is proposed. The simulation results show that the algorithm based on maximum path is more effective than the algorithm based on shortest path in complex networks. (2) The resistance distance characteristics in complex networks and its application requirements in community partitioning are studied, and the joint nodes are proposed. Five kinds of node centrality indexes, such as node centrality, proximity index, eigenvector, clustering coefficient and shortest path, are selected in this paper. Three kinds of network are simulated based on Simulation network, karate network and bottlenose dolphin network. In Kernighan-Lin (KL) algorithm and Fast Newman (FN) algorithm, experimental results show that the community partitioning algorithm based on nodal centrality and resistance distance and KL algorithm based on resistance distance can accurately partition the community structure of three experimental networks, but other community partitioning algorithms based on resistance distance can only partition part of the experimental network correctly. (3) Inspired by the small-world characteristics of complex network model, this paper proposes a Cayley DHT model with small-world characteristics, which combines the Cayley theory based on algebraic graph theory with the complex network theory, aiming at the dynamic changes of wireless sensor network nodes and the actual needs of virtual routing. A Cayley DHTVCP routing protocol is proposed on the basis of the proposed model, and the simulation results show that the protocol has good routing efficiency and robustness. (4) Aiming at the trend that the current data center network needs to use cheap equipment to build, this paper analyzes the advantages and disadvantages of the existing data center network structure, and applies the Cayley diagram based on algebraic graph theory and complex network. Based on the network theory, a C~3Cube model based on data center network is proposed. Based on this model, a C~3Cube routing protocol and fault-tolerant protocol are proposed. Simulation results show that the protocol is effective and can effectively solve the problem of constructing data center network with cheap equipment.
【学位授予单位】：华南理工大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5
【相似文献】
相关期刊论文 前10条
1 冯业荣;BP网络及其学习功能初探[J];广东气象;1995年01期
2 卓莹;张强;龚正虎;;网络态势预测的广义回归神经网络模型[J];解放军理工大学学报(自然科学版);2012年02期
3 岳博,焦李成;Bayes网络学习的MCMC方法[J];控制理论与应用;2003年04期
4 余振复;;N位M进制数码网络及其参数计算[J];自动化学报;1981年02期
5 王艳;李应兴;靳二辉;;复杂网络健壮社团挖掘算法[J];计算机工程与应用;2012年31期
6 孙鸿宾;吴子燕;刘书奎;;基于动态Bayes网络的结构时变可靠性分析[J];应用数学和力学;2014年01期
7 朱朝晖;滕少华;廖俊;游俊慧;黄国康;庄卿卿;;GSM网络优化支撑系统的设计与实现[J];江西师范大学学报(自然科学版);2008年04期
8 ，
本文编号：2249051
本文链接：https://www.wllwen.com/shoufeilunwen/jckxbs/2249051.html
