【作者】 晏先浩；

【导师】 王仲君；

【作者基本信息】 武汉理工大学 ， 应用数学， 2007， 硕士

【摘要】 人们从社会网络、Internet网络、合作网络以及生物网络等现实网络中发现了小世界性和无标度性，使得复杂网络的研究成为一个热点。为了从理论上解释这些特征，研究者提出了许多模型，小世界网络模型解释了社会网络“六度分离”的现象，BA模型研究了幂律分布的形成机制。在此基础上，许多其他的改进模型层出不穷，如增长网络模型、演化网络模型、局域世界演化模型等，它们分别从模型的演化机制、模型算法上做了许多工作。但是这些模型只侧重一些方面而很少考虑这样一个事实，例如社会网络中，个人的精力、资源等是有限的，因此网络演化时节点必然受到成本限制，无法无限制地与其他节点相连：Internet网络中，路由器的端口是有限的，连接到每个路由器上的线路不可能无穷大，这样的现象比比皆是。因此网络演化的过程中，必须考虑节点度的成本，这对实际网络结构特征的研究具有重要意义。本文的主要内容和创新之处可概述如下：1．关于研究复杂网络的数学方法的介绍复杂网络最主要的一个特征就是无标度，即其度分布服从幂律分布。本文首先介绍了幂律分布的一些性质，并从数学的角度对这些性质做了一点推导。其次，从数学的角度介绍研究复杂网络模型的主方程法。主方程法为什么可以解决此类演化问题呢?为此，本文从马尔科夫过程入手，引入主方程法，分析其物理意义及在演化网络模型中的应用。2．关于复杂网络模型的研究由于网络节点度成本不可忽视，因此必须建立考虑节点度成本的演化模型。本文在BA模型的基础上增加节点度成本有限的机制，建立LBA模型。理论分析发现，当最大成本度M低于新节点连边数的2倍时，即2m，网络演化有限步后停止，此时的网络结构是同质网络；而最大成本度超过该阈值时，网络可以无限制地演化；当最大度数无穷大时，该模型将退化为BA模型。利用平均场方法和数值计算的方法分析网络的结构，当M≥2m时，平均场方法计算的节点度分布仍是幂律的，其幂律指数在(2，3)之间，相比无标度网络小，但是更接近实际网络的无标度指数。数值模拟表明该结论是准确的，并且发现演化网络具有较高的集聚性和较短的平均最短路径，集聚系数随网络规模增大而衰减的速度较BA模型缓慢。该模型相比BA模型更适合模拟一些实际的网络，如Internet网络，社会网络等。3．关于复杂网络模型稳定性的研究LBA网络中具有有限度的节点可能会比较多，若受到攻击，其稳定性如何呢?本文采用鲁棒性的概念度量稳定性。对LBA的鲁棒性分析后发现，LBA网络对随机攻击具有相对较高的鲁棒性，删除大部分节点后，其平均最短路径并没有发生急剧的变化；而对蓄意攻击，尤其对最大度节点的攻击，其鲁棒性较低，删除不到30％的重要节点后，网络的连通性基本被破坏，只剩下孤立节点，但是相比BA网络的蓄意攻击，其鲁棒性较高。4．关于复杂网络的应用研究作为节点度成本有限的一个典型应用，友谊网络还有着其他的一些特性，比如友谊随着时间的推移、迁居、死亡等原因会衰减；友谊网络之间具有较高的传递性，朋友的朋友可能就是我的朋友。因此鉴于这几点演化特征，本文建立适合友谊网络演化的模型，采用主方程法分析发现网络演化后同时具有幂律度分布和小世界性，但是幂律指数相对无标度网络幂指数较小。友谊网络不仅具有高度集聚的集团结构，较显著的小世界性，还存在孤立的节点。更多还原

【Abstract】 Small-world property and Scale-free property have been discovered from many real-world networks such as social networks, Internet networks, collaboration networks, biological networks and so on, which makes research on complex networks become a focus. In order to theoretically explain these characteristics, researchers have proposed many models. The small-world network explains "six-degree separations" phenomenon in social networks, the BA model reflects the mechanism that formed the power-law. Based on these two models, many other improved models emerge one after another incessantly, such as the growth network model, the evolution network model, the evolution of local world network model and so on. They have done lots of work from the evolution mechanism and algorithm of network model. But many models did not consider the fact that, personal energy and resources are limited in the social network. So nodes have limited bearing capacity when the network evolves and can not unlimitedly connect to others. The router ports are limited in Internet network, so the data of each router connected to the line can not be infinite. These phenomenons can be found everywhere. So we must consider the cost of nodes in the evolution of network. It will be very meaningful to research the structure character of actual network.The main content and innovation can be summarized as follows.1. The introduction of mathematical method on the complex network.A most important feature of complex network is scaling-free degree, that is, its degree distribution is power-law. First of all, this paper introduces some properties of pow-law distribution and does a little derivation from the mathematical point of view on these properties. However, research of complex network often focused on the calculation method of model. At present there are relatively common methods of mean field, master equation and rate equation. The master equation is a mathematics method and others are statistical mechanics methods. Why master equation can solve such evolution problem? Therefore, this paper introduces how come to the master equation from the Markov process and analyzes its physical meaning and the application of evolution network model.2. On the Model of Complex NetworkBecause of the cost of nodes that can not be overlooked, it is necessary to build a evolution model that consider the cost of nodes. Because the research on other mechanisms of evolution model have been proved useful, in order to simplify study, we build LBA model which add limited degree of nodes on the base of BA model. We find that when M < 2m(M is the cost of nodes,m is number of edges of new node), network evolution will stop after the limited steps and shows homogeneity network. Numerical simulation shows that the conclusions are accurate, and the evolution network have a high concentration and a short average shortest Path. The attenuation rate of cluster coefficient with network size increasing slower than BA model. Compared to the BA model, this model is more suitable for practical network, such as Internet network, Social Network, etc.3 On the stability of the complex network model study.The nodes which have limited degree may be more in LBA network. How about its stability when attack this nodes? The researchers found that there are different robustness between random network and scale-free network with various attack strategies. In this paper, I find that the robustness of LBA network with random attacking is higher. The average shortest path doesn’t change drastically when delete some nodes randomly. But the connectivity of network was damaged when delete less than 30% large degree nodes. So the robustness of LBA network is very low when attacks important nodes deliberate.4 On the application of complex networks.As a typical application of LBA model, friendship network also has a number of other characteristics, such as friendship as time past, transplant, death and other reasons will decay. There is high transitivity in friendship network, just as my friend’s friend may be also my friend. So I build a evolution model of friendship network and find that the scale-free degree distribution and small-world phenomena appear together by using master equation. But the scale-free index is smaller than BA model. Moreover, not only friendship network have highly concentrated community structure and observably small world, but also there are isolated nodes in network.更多还原