毕业设计（论文）-复杂网络理论及应用研究.docx

东北农业大学学士学位论文 学号：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 UniversityChinaHarbinMay 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目 录摘 要IAbstractII前言- 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。如果我们将系统内部的各个元素作为节点，元素之间的关系视为连接，那么系统就构成了一个网络，例如神经系统可以看作大量神经细胞 通过神经纤维相互连接形成的网络、计算机网络可以看作是计算机通过通信介质如光缆、双 绞线、同轴电缆等相互连接形成的网络，类似的还有电力网络、社会关系网络、交通网络等 等23。强调系统的结构并从结构角度分析系统的功能正是复杂网络的研究思路，所不同的 是这些抽象出来的真实网络的拓扑结构性质不同于以前研究的网络，且节点众多，故称其为 复杂网络（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使用图论解决哥尼斯堡七桥问题。数学家和物理学家在考虑网络的时候往往只关心节点之间有没有边相连，至于节点到底在什么位置。边是长还是短足弯曲还是平直有没有相交等等都是他们不在意的。科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网它看起来像是格子体恤衫上的花纹；又如最近邻环网，它总是会让你想列一群手牵着手、嗣着篝火跳圆圈舞的姑娘。也就是说网络中任意两个节点之间的联系遵循既定的规则。用得最多的规则网络是由N个节点组成的环状网络网络中每个节点只与它最近的K个节点连接。规则网络的特点就是：每个节点的近邻数目都相同。但是对于大规模网络而言由于其复杂性并不能完全用规则网络来表示。 到-f 20世纪50年代末Erdos&Renyi想出了一种新的构造网络的方法在这种方法下两个节点之间连边与否不再是确定的事情而是根据一个概率决定。这是一种完全随机的网络模型数学家把这样生成的网络叫做随机网络。随机网络ER模型的描述如下：给定网络节点总数N，网络中任意两个节点以概率P连接生成的网络全体记为G(NP)构成一个概率空间。由于网络中连线数目是一个随机变量X取值可以从0到N(N一1)1.2复杂的网络理论变化目的在接下来的40年里一直被很多科学家认为是描述真实系统最适宜的网络。规则网络和随机网络足两种极端的情况随着信息技术的飞速发展科学家们发现对于大量真实的网络系统而言。他们既不是规则网络。也不是随机网络。而是介于两者之间，具有与前两者皆不同的统计特征的一种复杂网络。1998年。Watts&Strogatz提出了WS网络模型通过以概率p切断规则网络中原始的边并随机选择新的端点重 新连接构造出一种介于规则网络和随机网络之间的网络小世界网络(Smallwodd Networks)。显然，当p=0 时，相当于各边未动还是规则网络；当p=l时就成了随机网络。1999年Barabasi&Albert在Scienee上发表文章指出。许多实际的复杂网络的连接度分布具有幂律函数形 1.3复杂的网络理论统计特征复杂网络的小同的统计性 质决定了不同的网络内部结构而结构又决定了系统的功能。所以我们先了解一下复杂网络的相父统计性质。度及度分布。在网络中，节点的度足与目标节点相连的边的条数。即与该节点相邻的节点的数目。朋友的个数。而网络的度指网络中所有节点度的平均值。度分布P(k)指网络中一个任意选择的节点它的度恰好为k的概率。即不同度数的节点个数占节点总数的比率。在上面介绍的几种网络中，对于随机网络当N非常大时。随机网络的节点的度分布近似服从P0isson分布：目前，学界尚未给出复杂 网络的精准定义，从 现有研究成果看 ，之所 以称之为复杂网络 ，包含 以 下几层含义：首先 ，它是现 实网络的拓扑抽象 ；l29 J 其次，它既不是规则网络，也不是随机 网络 ，它具有 与二者不同的统计特征，没有一种方法能够生成与 真 实网络完全相 同的复杂 网络；其三，复杂网络是大量真实复杂系统得 以被研究的拓扑基础，可认为 其是开启“复杂系统之所 以复杂 ”的密钥 是公认的。2. 复杂网络的统计性质1736 年德国数学家 Eular 运用网络的技术和理念描述客观的世界，以此解决哥尼斯堡七桥问题。复杂网络研究的不同之处在于首先从统计角度考察网络中大规模节点及其连接之间的性质，这些性质的不同决定着将会有不相似的网络结构，而网络内部结构的不尽相似将导致系统的概不想通。所以，对这些统计性质的描述和理解是我们进行复杂网络相关研究的第一步，下面是对其概述的分论。2.1 聚集系数(The clustering coefficient)聚集系数 C 用来描述网络中节点的聚集情况，即网络有多紧密，比如在社会网络中，你朋友的朋友可能也是你的朋友或者你的两个朋友可能彼此也是朋友。其计算方法为：假设节点 i 通过 ki 条边与其它 ki 个节点相连接，如果这 ki 个节点都相互连接，它们之间应该存在 ki (ki 1) / 2 条边，而这 ki 个节点之间实际存在的边数只有 Ei 的话，则它与 ki (ki 1) / 2之比就是节点 i 的聚集系数，网络的聚集系数就是整个网络中所有节点的聚集系数的平均。显然，只有在全连通网络（每个节点都与其余所有的节点相连接）中，聚集系数才能等于 1，一般均小于 1。在完全随机网络中，C N 1 ，然而实证结果却表明大部分大规模真实网络中的节点倾向于聚集在一起，尽管聚集系数 C 远远小于 1，但都远比 N 1 大2。2.2 聚集系数概况(The clustering coefficient)聚集系数 C 用来描述网络中节点的聚集情况，即网络有多紧密，比如在社会网络中，你朋友的朋友可能也是你的朋友或者你的两个朋友可能彼此也是朋友。其计算方法为：假设节点 i 通过 ki 条边与其它 ki 个节点相连接，如果这 ki 个节点都相互连接，它们之间应该存在 ki (ki 1) / 2 条边，而这 ki 个节点之间实际存在的边数只有 Ei 的话，则它与 ki (ki 1) / 2之比就是节点 i 的聚集系数，网络的聚集系数就是整个网络中所有节点的聚集系数的平均。显然，只有在全连通网络（每个节点都与其余所有的节点相连接）中，聚集系数才能等于 1，一般均小于 1。在完全随机网络中，C N 1 ，然而实证结果却表明大部分大规模真实网络中的节点倾向于聚集在一起，尽管聚集系数 C 远远小于 1，但都远比 N 1 大2。2.3 度分布(The degree distribution)图论中节点 i 的度 ki 为节点 i 连接的边的总数目，所有节点 i 的度 ki 的平均值称为网络的平均度，定义为 k 。网络中节点的度分布用分布函数 p(k) 来表示，其含义为一个任意选择的节点恰好有 k 条边的概率，也等于网络中度数为 k 的结点的个数占网络结点总个数的比值。2.4 其它性质上述三种统计特性是复杂网络研究的基础，随着研究的深入，人们逐渐发现真实网络还具有一些其它重要的统计性质，例如：2.4.1 网络弹性（Network Resilience）网络的功能具有依赖其节点的贯通性，我们称网络节点的删除对网络贯通性的影响为网络弹性，其分析有两种方式：随机删除和有选择的删除，前者称为网络的鲁棒性分析，后者称为网络的脆弱性分析。Albert等人分别对度分布服从指数分布的随机网络模型和度分布服从幂律分布的BA网络模型进行了研究6，结果显示：随机删除节点基本上不影响BA网络的平均路径长度，相反，有选择的删除节点后，BA网络的平均路径长度较随机网络的增长快得多。这表明，BA模型相对随机网络具有较强的鲁棒性和易受攻击性。出现上述现象的原因在于幂律分布网络中存在的少数具有很大度数的节点在网络连通中扮演着关键角色，一般也称它们为Hub节点。2.4.2 介数（betweeness）介数分为边介数和节点介数7。节点的介数为网络中所有的最短路径中经过该节点的数量比例；边的介数含义类似。介数反映了相应的节点或者边在整个网络中的作用和影响力，具有很强的现实意义。例如，在社会关系网络或技术网络中，介数的分布特征反映了不同人员、资源和技术在相应生产关系中的地位，这对于在网络中发现和保护关键资源和技术具有重要意义。2.4.3 度和聚集系数之间的相关性网络中度和聚集系数之间的相关性被用来描述不同网络结构之间的差异8，它包括两个方面：不同度数节点之间的相关性和节点度分布与其聚集系数之间的相关性。前者指的是网络中与高度数（或低度数）节点相连接的节点的度数偏向于高还是低；后者指的是高度数节点的聚集系数偏向于高还是低。实证表明,在社会网络（演员合作网络、公司董事网络、电子邮箱网络）中节点具有正的度的相关性，而节点度分布与其聚集系数之间却具有负的相关性；其它类型的网络（信息网络、技术网络、生物网络）则相反9。正因为如此，这两种相关性被认为是社会网络区别于其他类型网络的重要特征，在社会网络研究中引起了高度重视3. 复杂网络模型最简单的网络模型为规则网络，其特点是每个节点的近邻数目都相同，如一维链、二维晶格、完全图等。上世纪50年代末Paul Erds和Alfred Rnyi提出了一种完全随机的网络模型 ，它由 N 个节点构成的图中以概率 p 随机连接任意两个节点而成，其平均度 k = p ( N 1) pN ；平均路径长度 l ln( N )ln( k) ；聚集系数 C = p ；当 N 很大时，节点度分布近似为泊松分布： P ( k ) e k k k k ! 。随机网络模型的提出是网络研究中的重大成果，但它仍不能很好的刻画实际网络的性质，人们又相继提出了一些小世界网络应用研究概述。最早运用小世界理论。以及目前运用小世界理论最多、最具成效的研究就是疾病传播问题。watts&Stmgatz证明疾病全球传播所需的时间和特征路径长度非常栩似只要在传播网络中加入一些捷径就可以使传播速度明显加快。运用病毒在小世界网络中的传播性质可推出信息在一个平均路径长度为6的网络中传播要比在平均路径长度为一百或一百万的网络中快得多。艾滋病、非典、禽流感等各种传染病等对人类造成巨大的威胁，2003年的“非典”对于宏观经济和人类的生命安全都产生了臣大的负面影响：目前，禽流感也已成为世界关注的一个焦点。于是问题是：在特定的社会网络中传染病如何通过接触关系传播而导致流行呢?决策者如何控制这些疾病将损失降到最低限度呢?从复杂网络的规律有望新的网络模型。3.1小世界网络（Small-World networks）实证结果表明，大多数的真实网络具有小世界性（较小的最短路径）和聚集性（相对较大的聚集系数），见表 1 所示。然而，规则网络虽具有聚集性，平均最短路径却较大；随机图则正好相反，具有小世界性，但聚集系数却相当小。表 1：实际网络的Small-world现象NetworkSizekLlrandCCrandWWW, site level153,12750.10780.00023Internet, domain level3015-62093.52-4.113.7-3.766.36-6.180.18-0.30.001Movie actors225,226613.652.990.790.00027MEDLINE co-authorship1,520,2510.0661.110-5Math. co-authorship70970.595.410-5E.coli, reaction graph31528.32.621.980.590.09Silwood Park food web1544.753.403Workds, synonyms22,31113.484.53.840.70.0006Power grid4,9412.6718.712.40.080.005C. Elegans282142.652.250.280.05下标 rand 为随机网络模型下的计算，通过对比实际网络与相应随机网络（相同的节点数和边数）的性质，可以发现真实网络具有小世界和较高聚集系数的性质。寻找到这些问题的合理的答案和解决途径。 研究者运用小世界网络的基本特征分析研究了Intemet上信息传播的特点发现IIltemet中的网络平均距离L足随网络大小N对数增长的它明瞳具有小世界效应。从结构上看，Intemet的实际结构介乎于规则网络和随机网络表明其具有小世界效应。同时校园网以及超链接的存在和特性也表明Intemet具有集团化、聚类的特征。其 中超链接是“断键重连”也是捷径。于是人们利用小世界的特性有效地改善I，网络信息交流的效率。表现为。利用小世界网络原理减少特征路径长度提高可靠性：重视关键结点的建设来保证网络的鲁棒性和脆弱性并存：利用小世界统计特性控制网络计算机病毒的传播。小世界网络理论为经济管理领域带来了全新的思路，人们试图用小世界理论去分析、解释日益繁杂的市场经济问题。该理论为经管问题提供了一种有效的技术工其，大大丰富了企业网络理论的内容和方法。具体表现在，人们用小世界理论研究了NPD(新产品开发)团队交流网络、企业创新网络、产学研合作创新、产业集群内的知识转移等问题。这些研究的共同点在于：使用平均路径长度模拟分析备节点之间的交流频率：使用集团化系数模拟分析各节点之间集聚程度。从而极大的提高各集团的功能。实现资源共享和技术互补另外小世界网络在生物学、物理学及交通管理等方面都有很好的应用，学者们取得了一定的研究成果。利用这些成果可以去更好的规划分析我们的实际生活。 可见规则网络和随机网络并不能很好展现真实网络的性质，这说明现实世界既不是完全确定的也不是完全随机的。Watts和Strogatz在 1998 年提出了一个兼具小世界性和高聚集性的网络模型12，它是复杂网络研究中的重大突破！他们通过将规则网络中的每条边以概率 p随机连接到网络中的一个新节点上，构造出一种介于规则网络和随机网络之间的网络（简称WS网络），它同时具有较小的平均路径长度和较大的聚集系数，而规则网络和随机网络则分别是WS网络在 p 为 0 和 1 时的特例。模型构造过程如图 1 所示。 WS模型提出后，很多学者在此基础作了近一步改进13，其中应用最多的是Newman和Watts提出的所谓NW小世界模型14。NW模型不同于WS模型之初在于它不切断规则网络中的原始边，而是以概率 p 重新连接一对节点。NW模型的优点在于其简化了理论分析，因为WS模型可能存在孤立节点，但NW不会。事实上，当 p 很小而 N 很大的时候，这两个模型理论分析的结果是相同的，现在我们统称它们为小世界模型。 世界网络（Small-World networks）3.2无标度网络（Scale-free networks）尽管小世界模型能很好的刻画现实世界的小世界性和高聚集性，但对小世界模型的理论分析表明其节点的度分布仍为指数分布形式15。实证结果却表明对于大多数大规模真实网络用幂率分布来描述它们的度分布更加精确2，即： P ( k ) k ，见表 2 所示。表 2：实际网络的Scale-free现象2NetworkSize k out inlreallrandlpowWWW, site325,7294.512.424.77Internet, router150,0002.662.42.41112.87.47Movie actors212,25028.743.654.01Co-authors, SPIRES56,6271721.95Co-authors, math.70,97518.26.53Sexual contacts2,8103.43.4Metabolic, E. coli773.23.322.89Protein, S. cerev.18702.392.42.4Citation783,3398.573Phone call5310Words, co-occurrence460,902。下标 out 、 in 分别表示出度和入度的幂率分布指数，可见很多网络的度分布具有幂率特征。下标 real 、 rand 和 pow 分别表示真实网络、随机网络模型和 Scale-free 网络模型中计算的平均路径长度。 实证结果表明，大多数的真实网络具有小世界性（较小的最短路径）和聚集性（相对较大的聚集系数）2，见表 1 所示。然而，规则网络虽具有聚集性，平均最短路径却较大；随机图则正好相反，具有小世界性，但聚集系数却相当小。表 1：实际网络的Small-world现象2NetworkSizekllrandCCrandWWW, site level153,12750.10780.00023Internet, domain level3015-62093.52-4.113.7-3.766.36-6.180.18-0.30.001Movie actors225,226613.652.990.790.00027MEDLINE co-authorship1,520,2510.0661.110-5Math. co-authorship70970.595.410-5E.coli, reaction graph31528.32.621.980.590.09Silwood Park food web1544.753.403Workds, synonyms22,31113.484.53.840.70.0006Power grid4,9412.6718.712.40.080.005C. Elegans282142.652.250.280.05下标 rand 为随机网络模型下的计算，通过对比实际网络与相应随机网络（相同的节点数和边数）的性质，可以发现真实网络具有小世界和较高聚集系数的性质。可见规则网络和随机网络并不能很好展现真实网络的性质，这说明现实世界既不是完全确定的也不是完全随机的。Watts和Strogatz在 1998 年提出了一个兼具小世界性和高聚集性的网络模型12，它是复杂网络研究中的重大突破！他们通过将规则网络中的每条边以概率 p随机连接到网络中的一个新节点上，构造出一种介于规则网络和随机网络之间的网络（简称WS网络），它同时具有较小的平均路径长度和较大的聚集系数，而规则网络和随机网络则分别是WS网络在 p 为 0 和 1 时的特例。模型构造过程如图 1 所示。 WS模型提出后，很多学者在此基础作了近一步改进13，其中应用最多的是Newman和Watts提出的所谓NW小世界模型14。NW模型不同于WS模型之初在于它不切断规则网络中的原始边，而是以概率 p 重新连接一对节点。NW模型的优点在于其简化了理论分析，因为WS模型可能存在孤立节点，但NW不会。事实上，当 p 很小而 N 很大的时候，这两个模型理论分析的结果是相同的，现在我们统称它们为小世界模型。幂率分布相对于指数分布其图形没有峰值，大多数节点仅有少量连接，而少数节点拥有大量连接，不存在随机网络中的特征标度，于是Barabsi等人称这种度分布具有幂率特征的网络为Scale-Free网络16。为解释Scale-free网络的形成机制，Barabsi 和Albert提出了著名的BA模型17，他们认为以前的网络模型没有考虑真实网络的两个重要性质：增长性和择优连接性，前者意味着网络中不断有新的节点加入进来，后者则意味着新的节点进来后优先选择网络中度数大的节点进行连接。他们不仅给出了BA模型的生成算法并进行了模拟分析17，而且还利用统计物理中的平均场方法给出了模型的解析解18，结果表明：经过充分长时间的演化后，BA网络的度分布不再随时间变化，度分布稳定为指数为 3 的幂律分布。 BA模型的提出是复杂网络研究中的又一重大突破，标志着人们对客观网络世界认识的深入。之后，许多学者对这一模型进行了改进，如非线性择优连接19、加速增长20、重绕边的局域事件21、逐渐老化22、适应性竞争23等等。需要注意的是，绝大多数而不是所有的真实网络都是Scale-free网络，如有的真实网络度分布为指数分布截断形式24等等。3.3 其它网络模型除了经典的小世界模型、无标度网络模型之外，学者们也提出了一些其它的网络模型来描述真实世界的网络结构。3.3.1 局域世界演化模型李翔和陈关荣认为择优连接机制不可能在整个网络上都起作用而只会在某个局域世界里被遵守，通过将局域世界的概念引入BA模型对其作了推广，提出了所谓的局域世界演化网络模型25，其度分布介于指数网络和无标度网络的度分布之间。该模型表明，随着局域世界的扩大，网络演化越不均匀，越接近于BA模型，即：局域世界的规模决定了网络演化的非均匀性。3.3.2 权重演化网络模型上述研究均将网络看作无权网，然而现实网络大多为有权网，即网络节点之间的连接强度是有区别的。Yook等人提出了一种权重演化模型26：假定节点权重正比于节点的度数，也即度数大的节点拥有更大的权数。结果表明，其度分布也符合幂律特征。3.3.3 确定性网络模型上述所有网络模型都引入了某种程度的随机性，那么是否一定要有随机性才能展现出小世界性和无标度特性呢？Barabsi等人提出了一种具有层次结构的网络模型27，它在确定性 ln 2机制下也能表现出无标度特性，节点度分布为 P ( k ) k ln 3 。4. 复杂网络的应用网络结构研究固然重要，但其最终目的是通过研究结构来了解和解释基于这些网络之上的系统运作方式，进而预测和控制网络系统的行为。一般将这种建立在网络上的系统动态性质称为网络上的动力学行为，其涉及面非常之广，如系统的渗流28、同步29、相变30、网络搜索31和网络导航32等等。上述研究理论性较强，有一类应用性很强的网络行为研究已经日益引起人们的兴趣，如计算机病毒在计算机网络上的蔓延、传染病在人群中的流行、谣言在社会中的扩散等等，实际上它们都是一种服从某种规律的网络上的传播行为。4.1 复杂网络的统计特征 复杂网络的统计特征 是网络的静态统计指标 ，它是通过现实网络进行拓 扑抽象、实证研究后再经统计计算而得出的统计指 标 ，主要包括度 (Degree)和度分布 (Degree distribu tion)、 簇 系数 (Clustering Coefficient)、平均路径 长度 (Average Path Length)、介数 (Betweenness)、度 秩函数35和社团 (Community Structure)等。众多学 者的研究结论可总结如下 ：(1)根据统计特征可将 复杂网络分为规则 网络、随机网络 、小世界网络和 无标度 网络 (见表 1)。(2)很多真实网络 的网络度 分布都服从近似幂律分布 ，被称作无标度 网络，度 分布呈现幂律分布的只是其中的一种代表 ；大多数 网络都具有较 小的平均距离和较大 的集散系数 即 小世界特性，如线性蠕虫神经网络 、美 国西部 电力 网络 、电影演员合作网络等都是小世界网络 。(3) 网络无标度性可归结为增长性和优先连接性。 4.2 复杂网络的稳定性复杂网络的稳定性。网络结构稳定性研究 一 般从平均最短距离、平均集聚程度、最大 团相对 大小及团的规模分布模式四个方面进行讨论。复 杂网络稳定性通常针对网络抗毁性研究展开，如对 一 般 网络 的攻击对象可选择取点与取边两种方式 ， 从攻击方式上可分为随机攻击和选择性攻击两种 类型。 复杂网络抗毁性研究最早始于 2000年阿 伯特 (Albea)等 的工作 。【 】郑 (Jeong)等研究了蛋 白 质网络，圳邓恩 (Dunne)等研究 了食物链 网络 ，柏】 纽曼 (Newman)等研究 了电子邮件 网络 ，【 曼歌妮 (Magoni)等研究了英特 网，蛇】萨马特 (Samant)等研 究 了对等 (Peer to Peer，P2P)网络 。【43l有关 复杂 网 络 抗 毁 性 的仿 真 研 究 ， 比较 全 面 的 要 数霍 姆 (Holme) 等的工作 。他们不仅考虑了节 点删除的 情况，还考虑 了边删除的情况，此外还考虑 了基于 介数的攻击策略。大量的抗毁性研究表 明，对于随 机网络与规则网络 ，采取随机攻击和选择式攻击， 其效果相当；无标度网络对随机攻击表现 出较强的 鲁棒性 ，但对基于度和介数的选择性攻击就会造成 很大的结构性破坏。对于有益 网络 ，其抗毁性越强 越好 ；对于有害网络，其抗毁性越弱越好 。 3复杂网络的演化动力学特征 。网络动力学 性质的基本研 究对象是动力学模型在不 同网络上 的性质与相应网络静态统计性质的联系，包括 已知 和未知 的静态几何量。如果发现某个模型在某一 网络上有某种特殊表现 ，就可以认为是这一网络的 某种静态特征影响 了这个模型的表现 。这种特征 可能是 已经得到研究的几何特性，也可能是没有被 发现的几何特征，那么前者将 印证网络上这些几何 量 的重要性，而后者将推动网络研 究的发展 。【451已 有 的研 究成果主要有 ：高 (Gob)等【 【钾】以及 巴泰 勒 米 (Barth61emy)【镐】利用介数来 定义节点或边上 的流量，研究了不同度分布指数的无标度网络上的 流量分布 ，发现其具有幂律分布的特性 ，除了度分 布指数趋于无穷 的情况；霍姆【49利用粒子跳动模 型研究了网络上的流量特性。复杂 网络的混沌 以 及混沌同步是当今 网络动力学研究的热点问题之一4.3复杂网络的理论在社会上的广泛应用复杂网络的理论研究广泛涉足于计算机网络、通信网络、交通和社会学等领域,但其在各个领域的应用研究尚需进一步深入。近年来对如何将复杂网络理论真正付诸于具体的应用之中,引起了学术界的广泛关注。在复杂网络理论中,小世界、无标度网络在交通、管理和社会学等领域,已经出现了一系列重要的研究成果。但在计算机与通信网络中有针对性的复杂网络应用研究尚不多见,本文针对复杂网络上移动行为的位置可预测性、无标度网络的鲁棒性、复杂网络理论在网络安全中的应用及认知无线网中资源分配算法等方面进行了研究,取得的创新性成果如下: 1、解决了人类在复杂网络上移动的可预测度问题。通过定义可预测度,真实位置熵,理论位置熵,规律性等概念,运用Fano不等式对熵进行计算,解决了人类在复杂网络上移动的可预测度问题,人类移动行为平均可预测性高达93%,得到了人类移动位置的预测度与与性别、年龄、生活地区、语言等没有明显相关性的结论。该研究成果对个人隐私信息的保护研究,城市规划,交通运输,移动增值服务等提供了理论依据。 2、提出了根据时空相关度对复杂网络进行抗蓄意攻击的算法。在设计复杂网络改变拓扑结构与逻辑重构算法时,时空相关度具有重要的意义,据此提出了时空无关和时空受限两类网络的定义,在此基础上,分别提出了针对时空受限网络的Hub Split算法与针对时空无关网络的Link Swtich算法,以提升网络抗击攻击的能力。换言之,在实际网络中在既保证了数据信息的高效传输、旅客的快速运送能力,在维持了对随机节点故障的高容忍度的同时,提高了抵抗对网络中关键点攻击的能力。 3、提出了一种基于可预测度和时空相关性的抗分布式拒绝服务攻击的方法。根据分布式拒绝服务也具有较高的可预测性,兼顾历史信息与当前网络状态,运用递归最小二乘法,对疑似攻击行为进行判定。在此基础上,对网络进行逻辑拓扑的改变,即改变路由。达到了针对同一攻击目标在时间、空间上对攻击网络包平滑的目的,缓解甚至消除了分布式拒绝服务攻击。 4、提出了基于可预测度的认知无线网资源分配算法。在实际认知无线网络环境中,由于干扰、散射等因素会使得某些网络参与者即博弈方得不到完全的信息,造成了资源分配的合理性问题。然而认知网络具备无标度网络的特征,其网络博弈各方的信息具有较高的可预测度,在此基础上,提出了一种基于可预测度的非完全信息博弈的资源分配算法,实现了资源的合理利用。4.4 复杂网络理论的前景复杂网络是近年来国内外学者研究的一个热点问题。传统的对网络的研究最早可以追溯到18世纪伟大数学家欧拉提出的著名的“Konigsberg七桥问题”。随后两百多年中，各国的数学家们一直致力于对简单的规则网络和随机网络进行抽象的数学研究。规则网络过于理想化而无法表示现实中网络的复杂性，在20世纪60年代由Erdos和Renyi（1960）提出了随机网络。进入20世纪90年代，人们发现现实世界中绝大多数的网络既不是完全规则，也不是完全随机的，于是提出了一些更符合实际的网络模型。此时，国际上有两项开创性工作掀起了一股不小的研究复杂网络的热潮，一是Wats和Strogata2在Nature杂志上发表文章，提出的小世界模型（WS 模型）。该模型既具有规则网络的高聚类性，又具有类似随机网络的小的平均路径长度。二是Barabs和Albert在Seience上发表文章，提出了无标度网络模型（BA模型）。他们认为现实世界中大多数的复杂系统是动态演化的，是开放自组织的，实际网络中的无标度现象来源于两个重要因素，即增长机制和优先连接机制。目前，国内外学者复杂网络的研究主要集中在三个方面：大量的真实网络的实证研究，分析真实网络的统计特性；构建符合真实网络统计性质的网络演化模型，研究网络的形成机制和内在机理；研究社会关系复杂网络，对企业网络的生长模型进行分析。在复杂网络的结构特征研究方面，张明科等从复杂网络动力学角度，对BA模型进行扩展，构建了网络化战争中的复杂网络拓扑模型。李一宁、汪小帆提出了一种基于较大规模的底层网络生成较小规模的映射网络模型的算法。Richard G. Cleg等利用幂律模型对复杂网络的拓扑生成由此实现网络性能的改善。Jean-Loup Guillaume等通过定性结果的分析方法对互联网的拓扑结构的大型分布式探索。杨博等6利用网络簇结构的复杂网络聚类方法对复杂网络拓扑结构分析理解其功能、发现其隐含模式、预测其行为。在复杂网络的演化机理方面，BA模型很好地在科学研究中体现了从复杂现象中提取简单本质的特点。Andrade根据古希腊数学