复杂网络理论及应用研究.doc

东北农业大学学士学位论文 学号：A20120034复杂网络理论及应用研究 学生姓名：指导教师：所在院系：理学院所学专业：信息与计算科学 东 北 农 业 大 学中国·哈尔滨2016年5月Northeast Agricultural University Bachelor Dissertation Student I.D.A20120034Complex network theory and its applicationStudent: Instructor: Specialty:: College of Science Research Direction: Information and Computing Science Northeast Agricultural UniversityChina·HarbinMay 2016摘要本论文的主要目的研究的是结合具体的复杂网络对象实例,系统研究复杂网络的理论和实践,并且研究复杂网络原理在Ad hoc计算机网络中的应用。

选择了汉语词组网络作为实际复杂网络研究对象提出了一种推广的耦合网络理论模型 该论文的研究方法由于耦合网络的普遍存在,在复杂网络基本理论方面首先研究了耦合网络的模型建立和扩展基于Zheng等的耦合网络演化模型,根据对实际网络的分析,提出了一种扩展模型的方案在耦合演化过程中增加考虑了网络旧节点之间的再生连接,通过速率方程的建立及严格求解,给出了网络中有关度分布函数的幂律渐近解,并求出相关的幂指数通过模型参数的适当设定,所建立的扩展模型可以给出已有相关的实际网络结果,而且具有更广泛的适应性 随后选择了一个具体的复杂网络对象---汉语词组网络,对之进行了比较全面的研究研究基于复杂网络基本理论和对三组实际词组数据的分析建立了汉语词组的复杂网络视图,计算了汉语词组网络的网络结构参数和动态演化特性得到了汉语词组网络具有3度分隔的小世界拓扑和具有幂律的度分布特性的重要结果关键词：复杂网络 耦合网络 模型参数AbstractThe main purpose of the research is combined with the specific example of complex network object, the research of complex system theory and practice of network, and study the application of complex network theory in ad hoc network. Select the Chinese phrase network as the actual complex network research object. A generalized coupled network model is proposed.Research method of the thesis because of the common existence of coupled network, in terms of the basic theory of complex network firstly studies the network coupling model is established and the extended. Evolution model based on Zheng coupled network, based on the analysis of the actual network proposed an extended model. In the process of the evolution of the coupled added connection network between old nodes of regeneration, network of distribution function of the degree of power-law asymptotic solutions are given by the rate equation is established and solved exactly, and calculate the corresponding exponents. Through the appropriate set of model parameters, established the extended model can has been given the actual results of network and Has more extensive adaptability. Then choose a specific object of complex networks, Chinese phrase network, to were more comprehensive research. Research based on complex network theory and analysis of three groups of the actual phrase data. Establish the intricate network of the Chinese phrase view, the calculation of the Chinese phrase network network structure parameters and dynamic evolution characteristics.An important result of the small world topology with 3 degree separation and the degree distribution of power law is obtained.Key words: complex network coupled network model parameters目 录摘 要 IAbstract II前言 - 1 -1.复杂的网络理论概论 - 1 -1.1复杂的网络理论演变历程 - 2 -1.2复杂的网络理论变化目的 - 2 - 1.3复杂的网络理论统计特征 - 2 -2.复杂的网络的统计性质 - 3 -2.1 聚集系数 - 3 -2.2 聚集系数概况 - 3 - 2.3度分布 - 4 - 2.4其他性质 - 4 -2.4.1网络特性 - 5 -2.4.2介数 - 6 - 2.4.3度和聚集系数之间的相关性 - 8 -3.复杂网络模型 - 8 - 3.1小世界网络 - 9 -3.2无标度网络 - 11 - 3.3其他网络模型 - 11 -4.复杂的网络应用 - 13 - 4.1复杂网络的统计特征 - 13 - 4.2复杂网络的稳定性 - 15 - 4.3复杂网络理论在社会上的广泛应用 - 16 -4.4复杂网络的前景 - 16 -总结 - 17 -参考文献 - 18 - 前言 复杂网络是随即图理论中新出现的一个研究分枝，从Monkey语言模型(随机文本模型)出发,建立了对应于汉语词组网络的随机文本理论模型。

揭示了直接用随机文本模型描述自然语言的缺陷和适应性以及对模型的调节途径发现当改变Monkey模型的结构,减少其随机因素,比如考虑单字频度因素和词长的分布因素时,调节选字的集中性等,可以使模型能够更好地刻画和描述自然语言的行为同时模型的分析也揭示出自然语言演化中的一些关键特征,比如最小代价原理的体现研究对全部过程进行了模拟并比较了汉语词组网络和其它少数几种语言的小世界特性,做出基本的分析,认为汉语词组网络属于和英语概念网络相同的无标度小世界网络类型同时从几个角度初步探讨了研究汉语复杂网络的潜在实际应用意义结构决定功能是系统科学的基本观点[1]如果我们将系统内部的各个元素作为节点，元素之间的关系视为连接，那么系统就构成了一个网络，例如神经系统可以看作大量神经细胞 通过神经纤维相互连接形成的网络、计算机网络可以看作是计算机通过通信介质如光缆、双 绞线、同轴电缆等相互连接形成的网络，类似的还有电力网络、社会关系网络、交通网络等 等[2][3]强调系统的结构并从结构角度分析系统的功能正是复杂网络的研究思路，所不同的 是这些抽象出来的真实网络的拓扑结构性质不同于以前研究的网络，且节点众多，故称其为 复杂网络（complex networks）。

近年来，大量关于复杂网络的文章发表在Science、Nature、 PRL、PNAS等国际一流的刊物上，从一个侧面反映了复杂网络已经成为国际学术界一个新 兴的研究热点1.复杂的网络理论概括 复杂网络应用研究是一种较为全新的尝试,根据对MANET(Mobile Ad hoc NETwork)网络的体系结构与路由协议的分析研究基础,我们试图将复杂网络的基本理论和结论用于MANET网络层路由协议的改进和网络的拥塞控制首先从体系结构的低层考虑了复杂网络理念在MANET的切入点,首次引入了广义的拓扑控制和复杂网络视图的概念根据当前的研究,明确了复杂网络视图操作属于网络拓扑控制研究特别的一种,及其在网络体系结构中的位置基于一种MANET的实际应用场景,提出了小世界网络及其视图的构建模型和方案,分析论证了其正确性,进行了相应的计算和拓扑模拟MANET拓扑结构的复杂网络视图,突出了网络更多新的特性,能够为路由算法和拥塞控制算法设计时提供参照从而使之更有效我们仔细研究了MANET的DSR(Dynamic Source Routing)路由协议,对其中路由发现和路由维护阶段进行了一般优化,随后根据所建立的实际网络模型,使用复杂网络视图信息对DSR的路由发现进行了进一步优化和改良。

分析了根据实际所构建的小世界网络可能存在的拥塞问题,用复杂网络视图对问题进行了剖析,并提出了解决的方案,由此对DSR进行了相应的改变除了理论上的定性正确性证明之外,上述全部协议改进和拥塞控制算法均使用ns-2网络仿真工具进行了数字仿真,网络性能指标的改进证实了我们工作的正确性和有效性 本文的研究在汉字网络方面和复杂网络在MANET中应用方面,都是具有开拓性研究工作进行的同时,也提出了许多更深入的问题,留待下一步的工作 1.1复杂的网络理论演变历程．复杂网络演化过程用网络的观点描述客观世界起源于1736年德同数学家欧拉Eular使用图论解决哥尼斯堡七桥问题数学家和物理学家在考虑网络的时候．往往只关心节点之间有没有边相连，至于节点到底在什么位置边是长还是短．足弯曲还是平直．有没有相交等等都是他们不在意的科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网．它看起来像是格子体恤衫上的花纹；又如最近邻环网，它总是会让你想列一群手牵着手、嗣着篝火跳圆圈舞的姑娘也就是说网络中任。