【作者】 史伟；

【导师】 赵政；

【作者基本信息】 天津大学 ， 计算机应用技术， 2010， 博士

【摘要】 网络动力学的研究主要包括网络演化机制以及网络行为两个方面。根据最新的研究成果表明,大量的真实网络如Internet、WWW等既不是纯粹的规则网络也不是完全的随机网络,而是介于确定性与随机性之间的复杂网络。此前,有关网络动力学的研究是建立在确定的规则网络或是随机的均匀网络基础上的,因此有些结论在复杂网络中并不一定成立。本文汲取了复杂网络研究的最新成果对信息网络的演化机制及传输行为进行了研究,主要贡献如下:1.提出了“基于Agent的信息网络演化模型”,设计了新的网络演化机制并通过迭代的方式生成了该模型的拓扑结构。相对于其它网络演化模型,该模型不仅将“小世界特性”、“无标度特性”、“高聚类特性”以及“社团性”纳入到同一框架内,而且还可以通过调节演化参数来控制网络的拓扑演化进程。2.将模拟退火算法应用于社团划分并提出了“基于节点类型的网络社团划分算法”。该算法的基本思想是首先将原始网络随机地划分为若干社团,然后根据初始划分后的结果对各社团内部的节点以及社团间节点的连接方式进行分类,根据分类结果对网络进一步进行划分,直到满足最优化条件。最后通过实验将该算法与模拟退火算法以及GN算法进行了比较,实验结果表明该算法能够有效、准确地对网络社团结构进行划分。3.定量地研究了网络“平均度”、“无标度特性”、“小世界特性”以及“社团性”对信息传输能力产生的影响。实验发现,(1)随着网络平均度的逐渐增大,网络的传输能力逐渐增强;(2)在网络平均度一定的情况下,随着长程连接的逐渐增多,网络的传输能力开始由弱变强,然后由强变弱;(3)随着幂指数γ的值的不断增加,网络的临界相变点都在逐渐减小。(4)网络社团性越强,传输能力越弱,反之亦然。4.推导出了一般路由行为下网络临界相变点的计算公式;通过实验和理论证明了在节点传输能力一定的情况下ω=-1对应的基于节点连接度的局部路由策略表现最优以及节点传输能力不定的情况下ω=1、对应局部路由策略最优;提出了根据节点“有效介数”进行选路的路由策略。实验结果表明,β=1对应的路由算法表现最优且基于节点有效介数的路由策略普遍要比基于节点连接度的路由策略表现更好。更多还原

【Abstract】 The studies on network dynamics can be divided into two groups: the evolution mechanisms of networks and the behavior on networks. According to the latest studies, many real networks such as Internet、WWW etc are not complete regular networks or random networks, on the contrary, they are complex networks that both have certainty and uncertainty. Therefore, those conclusions that based on random networks or regular networks may not apply to complex networks. In this paper, the studies mainly focus on the evolution mechanisms of networks and information transmission problems based on the latest research on complex networks1. A new evolving network model named“the information transmission model based on agent”is proposed. New evolution mechanisms are designed by summarizing the common topological properties of information networks and by using the methord of network dynamics theory for reference. Compared to other models, this model could not only incorporate small-world property, scale-free property and community property into the same framework but also control the evolution process of network by adjusting the parameters.2. SA algorithm is applied to find community structure of networks and a new algorithm that based on the roles of nodes (PANT) in complex networks is proposed for the same purpose. The basic idear of PANT algorithm is as follows: Firstly, stochastic algorithm is adopted for initial partition. Then, nodes are classified into four different types and the connections between different communities are classified into three types. According to different types of connctions, further partitions of the network are made until the algorithm reaches optimization. Experimental results show that this algorithm could find the community structure efficiently.3. How topological properties of complex networks such as small-world property, scale-free property and community property affect the transmission capacity of a network are studied. Experimental results show that (1) as the average degree of the a network increases, the transmisison capacity of a network increases either (2) when the average degree of a network keeps unchanged, as the number of long-range connections increases, the capacity of a network increases at first and then decreases when the quantity of long-range connections is much more than local conncetions.(3) when exponentialγincreases, the capacity decreases.(4) the stronger the modularity is , the lower efficiency the transmission capacity has.4. It is found thatω=-1 responds to the optimal local routing strategy when the capacity of each node is a constant andω=1 responds to the best local routing strategy when the capacity of each node is not a constant. In order to further maximize the capacity of the network, a glocal routing strategy based on“effective betweenness”is proposed. Experimental results show thatβ=1 responds to the best routing strategy and routing strategies based on effevtive betweenness run better than those routing algorithms based on the degree of nodes.更多还原