节点文献
复杂网络模型及应用研究
Study on Complex Network Models and Its Application
【作者】 谭利;
【导师】 侯振挺;
【作者基本信息】 中南大学 , 概率论与数理统计, 2010, 博士
【摘要】 网络在自然界和人类社会中无处不在,常见的网络有生态网、万维网、人际关系网和交通网络等等.对真实网络特性的解释使得复杂网络成为了近年来的研究热点之一.为了探索真实网络的行为和功能,必需对网络的拓扑结构进行详细研究.本文的主要工作是通过生成机制建立网络模型,模拟真实网络的演化行为,寻找求解网络统计特征的严格方法.本文从概率论角度和统计学角度出发,分别给出了严格求解度分布的马氏链方法和极限定理法.此外,还根据真实网络的特征提出了几类按边迭代的网络模型以及基于合作网络的模型,探讨了模型的拓扑结构,并进行了模拟分析.现归纳如下:1、从概率学角度严格推导了LCD模型和B-O模型的度分布解析式.求解度分布常用的方法有平均场方法、率方程方法和主方程方法等.这些方法在求解模型度分布时,往往需要做一定的假设,只能得到度分布的近似表达式.LCD模型和B-O模型虽然利用鞅方法严格求解,但是求解过程比较复杂,而且鞅方法只适用于带有重连和自连的网络模型.本文从概率论的角度出发,将节点的度数看成一系列马氏链.根据马氏链首达概率和度数概率之间的关系严格证明了这两类模型的度分布存在性,得到了度分布的精确解析式.此外,还将该方法简化,同样严格证明度分布存在性,并得到度分布的精确表达式.最后,对LCD模型和B-O模型进行模拟分析,数值模拟结果与理论推导表明两类模型均服从幂率分布.LCD模型的度指数为3,而B-O模型的度指数依赖于吸引度.2、从统计学角度给出了严格求解度分布的极限定理法.此方法从时刻t网络中度数为k的节点平均数出发,利用极限定理推导度数为k和k-1的节点平均数之间的关系,从而证明度分布的存在性并得到度分布的精确解析式.此方法简单而且适用范围广.对于具有重连和自连的网络模型,仍然可以简易推导.此外,该求解度分布的极限定理法同样可以运用于求解加权网络的点权分布和边权分布.3、提出了几类按边迭代的网络模型.现实网络的节点之间是相互关联的.网络演化过程中,如果忽略节点之间的关联性便不能很好的刻画现实网络.为了体现网络择优过程中的节点关联性,本文提出了几类按边迭代网络模型.首先对按单边迭代网络模型进行了研究,严格分析了模型的度分布、群集系数和度相关性等.发现网络具有幂率度分布,群集系数大.两节点度的相关性只与网络规模有关,且随网络规模成对数增长.其次,扩展了按单边迭代的网络模型,提出了多边迭代网络模型以及加权的按边迭代网络模型.利用极限定理方法对模型的特征参数做了严格而详细的分析,发现模型节点度分布、点权分布和边权分布都是幂率的,而且群集系数大.具有现实网络的基本特征.4、提出了基于合作网络的确定性、随机性和集团融合模型.通过对演员合作网络的分析,本文提出了每个项目参与人数固定的简易模型.利用极限定理法分析了模型的集团度分布和度分布,它们均具有幂率性质,度指数与项目参与人数相关.对节点的相关性研究表明,两节点度的相关性只与网络规模有关,呈指数增长.模型具有较大的群集系数.由于现实网络每个项目参与人数是不断变化的,本文将每个项目参与人数看成一个随机变量,提出了项目人数变化的随机性模型,发现其集团度分布和度分布均与随机变量的参数有关.同时,由于演员合作网络中新旧项目间节点是有重合的,本文提出了节点相互关联的融合模型.通过对模型的模拟分析和理论推导,发现模型具有无标度特征,度指数依赖于新旧项目间节点重合的比例.两节点度的相关性与网络规模有关,网络群集系数较大.
【Abstract】 Networks exist in every aspect of nature and society, the most commons are the ecosystems, the World Wide Web, human relationship networks and transportation networks, etc. The importance and urgency of understanding real networks made complex networks become a hot research area in recent years. In order to explore the behavior and function of real networks, one needs to make a scrutiny into the topological structure of real networks. The main task of this paper is to build up network models that can simulate the evolving behavior of real networks, and to work out rigorous methods for the statistical properties of networks. In this paper, rigorous methods for degree distribution are proposed from the standpoint of probability and statistics respectively. Meanwhile, some new models are presented, the statistical parameters are analyzed and simulations are also taken to verify the theoretical derivations. The main results are as follows:1、Rigorous derivations of the degree distribution of the LCD model and the B-O model are given from the probability aspect. The frequently used methods of solving degree distribution are the mean-field method, the rate equation method, the master equation method and so on. While use these methods, one needs to make some assumptions, and obtains only approximate expressions of degree distribution. Although, the LCD model and the B-O model were rigorously derived with the martingale method, the calculating processes were somewhat complicated. Moreover, the martingale method can only analyze networks with multiple edges and loops. As we know, from the aspect of probability, the degree distributions of vertices are series of Markov chains. Thus, with the relationship of degree probability and first passage probability of Markov chains, this paper gives a rigorous proof to the existence of degree distribution, and obtains the exact analytic expressions of degree distribution. Moreover, a simplified method is proposed, which also gives rigorous analysis to the degree distribution. Finally, simulations of the LCD model and the B-O model are taken. The numerical simulations and theoretical analyses show that both the two models are power-law. The degree exponent of the LCD model is 3, while that of the B-O model depends on the attractiveness.2、A new method based on a limit theorem is proposed to solve degree distribution from the point of statistics. The average number of vertices with degree k at time t is analyzed firstly. Then, the relationship of degree distributions between k and k-1 is derived with the Stolz theorem. With this relationship, the existence of the degree distribution is thus proved and the exact expression of the degree distribution is derived. This method is simple and can be widely extended to other models, such as models with multiple edges and loops. Furthermore, this method can also be easily applied to solve vertex strength distribution and edge weight distribution of weighted networks.3、Some network models with edge iterations are proposed. Vertices are correlated in most real networks, and it is difficult to describe a real system if the correlations among vertices are ignored in the evolving processes. To give expressions to correlations of vertices in the preferential process, some models based on edge iterations are given. Firstly, the network model with one edge iterated is studied. Analyses show that the model has power-law degree distribution, high clustering coefficient and the two vertex degree correlations are logarithmically increased with the network size. Secondly, the network model with one edge iterated is extended. Network models with multiple edges iterated and weighted network models with edge iterations are suggested. With the limit theorem method, we give rigorous and detailed analyses to the topological characteristics of networks. Results show that the vertex degree distribution, the vertex strength distribution and the edge weight distribution are all power-law for the weighted networks, and the models display high clustering coefficient, which possesses the essential feature of real networks.4、The deterministic model, the random model and the merging model are proposed based on collaboration networks. At first, the model is evolved with fixed number of people for each project. With the limit theorem method, the clique degree distribution and the degree distribution are studied, both with scale-free property and the degree exponents depend on the number of people involved in each project. Besides, it is find that the degree correlations grow exponentially with network size, and the model shows high clustering coefficient. However, the number of people involved is usually different from one project to another, we assume the number of people involved in a project to be a random variable, and propose the random model. The clique degree distribution and the degree distribution are similar to that of the deterministic model, but the degree exponents are related to the parameters of the random variable. Meanwhile, based on the fact that the vertices of new projects often coincide with vertices of old projects, a merging model with vertices correlated to each other is presented. The simulation results and theoretical derivations indicate that the model is scale-free, the degree exponent depends on the proportion of vertices coincided between new and old projects. In addition, the two degree correlations are related to the network size, and the model owns high clustering coefficient.