【作者】 王波；

【导师】 王万良； 姚明海； 杨旭华；

【作者基本信息】 浙江工业大学 ， 控制理论与控制工程， 2009， 博士

【摘要】 复杂网络是近十年来随着计算机技术迅猛发展而兴起的一门综合信息学、数学、物理学、生物学、管理学等众多学科的交叉学科。对复杂网络理论和应用的研究,有助于人们更好的认识网络,鉴别存在于自然和社会中各式各样的实际网络;有助于人们了解网络,揭示实际网络的内在特性和形成规律;有助于人们改进网络,使各种实际网络更好的为人类服务。本文从实际网络出发,分别提出了一个无标度网络模型和一个加权演化网络模型;研究了实际公交网络的统计特性,揭示了其网络特征;设计了一个基于加权复杂网络的公交换乘算法;分析了公交网络的社团结构和传播行为。主要研究内容如下:提出了一个基于派系增长和优先连接的无标度网络模型。该模型演化的每一步有一个新的派系加入到网络中,并且这个新加入的派系优先与已存在的具有较多连接的派系相连接。仿真结果显示生成网络的节点度分布为无标度幂律分布。将派系视为节点,派系间连接视为边构成一个新的网络,此网络节点的度分布也符合无标度幂律分布。基于平均场理论,给出了该模型节点度分布的解析结果。提出了一个基于派系重叠增长的加权演化网络模型。该模型在两种不同的连接机制下(优先连接和随机连接)具有不同的网络特性。利用平均场方法,分别分析了在两种不同机制下产生的网络的节点所属派系数分布和节点强度分布。证明了在优先连接机制下,两种分布都符合幂律分布;在随机连接机制下,两种分布都符合指数分布,并且解析得到了其分布指数。数值模拟结果与解析结果很好地吻合。研究了space L描述下的公交网络的平均路径长度、聚类系数、度分布等特性,认为space L描述下的公交网络类似于规则网络,并不具备明显的小世界特性,而其度分布符合幂律分布。随后研究了space P描述下的公交网络的度分布、多重边分布、不同派系之间的重叠节点数分布、每个节点所属派系数分布等规律。并将每个派系看成为一个节点,派系间的重叠看成多重边,构成一个派系网络,研究了该派系网络的平均路径长度、聚类系数和度分布等特性。认为space P描述下的公交网络是一个高度派系重叠、高度派系聚类、具有指数型度分布的小世界网络。最后,根据space P描述下的公交网络的特性,提出一个公交网络演化模型,并基于平均场方法对其进行理论分析。模型的模拟结果和解析结果很好的解释了spaceP描述下的实际公交网络中所呈现的网络特性。用space P方法将公交网络建模成为一个无权复杂网络,然后利用广度优先搜索算法得到需换乘两公交站点间的所有最少次数换乘方案。在此基础上,引入了网络点权,即站点的经纬度,进而得到网络的边权,即站点间的直线距离,把公交网络进一步建模成一个加权的复杂网络模型。结合得到的最少换乘次数方案,最终得到一种在保证换乘次数最少的基础上站间总直线距离也最短的换乘方案。用杭州的实际数据验证了此算法的有效性。利用改进的社团结构划分方法(PKM凝聚算法)分别对space P和space L描述下的实际公交网络进行社团特性分析。得到的结果说明在space L描述下的公交网络具有明显的社团特性,而在space P描述下的公交网络并不具有社团特性。究其原因是由于space P描述下的公交网络具有高度重叠的性质,用以上方法不能有效辨识出此类型网络的社团结构。因此,我们提出一种新的社团的定义,称之为N-深度社团,并给出了这种社团结构的划分方法。将此定义和划分方法应用到一个公交网络模型上,取得了较好的效果。基于SIS传播模型分别在space P描述下的北京、上海和杭州三个实际公交网络上做了传播行为仿真,得到网络中感染节点的密度随时间的变化情况和感染节点的稳态密度随传染率的变化情况。在一个公交网络模型上做了传播行为的仿真研究。利用平均场理论,分析了此模型的传播临界值,与仿真结果一致。更多还原

【Abstract】 Complex network is a new interdisciplinary science which sprang up with the swift and violent development of the computer technology in recent ten years. It colligates many subjects including information science, mathematics, physics, biology, management science and so on. The study on complex network theory and application can help us to recognize networks, identify the different kinds of practical networks in nature and society; realize networks, open out the internal characteristics and evolving rules; improve networks, make the practical networks service for human better.Form the practical networks in this dissertation, a novel scale-free network model and a weighted network model are proposed respectively. The statistic characteristics of the real bus transport networks are analyzed. An optimal bus transport transfer algorithm based on weighted complex network is designed. The community structure and spread behavior of the real bus transport networks are analyzed. The main contributions are as follows:Firstly, a novel scale-free network model based on clique (complete subgraph of random size) growth and preferential attachment is proposed. Every time step of the evolving procedure, a new clique is added into the network, and this new clique attaches preferentially to the old ones that are already well connected. This novel model evolves on the basis of cliques, not vertices. Simulation results show that the degree of vertices of the generating network follows a scale-free power-law distribution. Besides, the cliques also constitute a network, with the connections of the cliques being their links. The degree distribution of this clique network also has the scale-free power-law properties. And based on the Mean-field theory, the analytical results of this model are given.Secondly, a weighted evolving network model on the basis of clique overlapping growth is proposed. The model shows different characteristics under two different attachment mechanisms which are preferential attachment and random attachment respectively. By Mean-field theory, we analyze the distributions of so-called "the number of cliques a vertex joins" and "the vertex strength" of this model under different attachment mechanisms. We verify that both of the distributions follow the scale-free power-law distribution in preferential attachment mechanism while both of them follow the exponential distribution in random attachment mechanism. Simulation results are in agreement with the analytical results well. Besides, we present the empirical investigation results on the practical bus transport networks of three major cities in China. The results show that this kind of collaboration networks can be modeled by our model very well.Thirdly, the statistic characteristics of the practical bus transport networks described by space L are studied, including the average path length, clustering coefficient, degree distribution and so on. We consider that the bus transport network described by space L is similar to the regular network, which do not have the obvious small-world phenomenon, and whose degree distribution follows the power-law distribution. Then the statistic characteristics of the practical bus transport networks described by space P are studied, including the degree distribution, multiple edges’ overlapping times distribution, distribution of the overlap size between any two overlapping cliques, distribution of the number of cliques that a node belong to. Naturally, the cliques also constitute a network, with the overlapping nodes being their multiple links. We also research its network properties such as degree distribution, clustering coefficient, average path length and so on. We propose that the bus transport network described by space P has the properties of random clique increment and random overlapping clique, at the same time, it is a small-world network with highly clique clustered and highly clique overlapped. Finally, we introduce an evolution model whose simulation results agree well the statistical laws which emerge in real bus transport networks described by space P.Fourthly, we use the method of space P to model the bus transport network, by which an unweighted complex network model is obtained. Then by using the breadth-first search algorithm, we get all the least transfer routes between two inquired stations. We introduce the vertex weight, namely every station’s longitudes and latitudes. The edge weight——straight-line distance between every two stations——will be got by computing the vertex weight. Further we model the BTN to a weighted complex network. A final transfer route which has the shortest total straight-line distance on the basis of the least transfer is obtained by this weighted complex network model and all the least transfer routes are got in prior. The practical data of Hangzhou is used to testify the new algorithm’s efficiency. Fifthly, by improved community dividing algorithm (PKM agglomerative algorithm), we did the community property analysis on the BTN which is described in space L and space P respectively. The results show that BTN which is described in space L has obvious community property, but the one described in space P hasn’t. The reason is that the BTN described in space P has the intense overlapping property, which makes the algorithm used above noneffective. So, a new community definition called N-depth community is proposed. And the method of finding this kind of communities in networks is represented. We obtained very good effect by using this community definition and dividing method on a BTN model.Finally, based on the SIS spread model, the spread behavior on the practical bus transport networks described by space P of Beijing, Shanghai and Hangzhou is simulated. The variations of the infected vertices’ density with the time and the infected vertices’ steady density with the infection rate are obtained. And the spread behavior on a bus transport network model is simulated. By the Mean-field theory, we analyze the epidemic threshold of this model which agrees with the simulation result well.更多还原