【作者】 严钢；

【导师】 陈关荣； 付忠谦；

【作者基本信息】 中国科学技术大学 ， 电路与系统， 2010， 博士

【摘要】 随着信息技术的发展和社会文明的进步,当前涌现出各式各样的大规模信息网络,如互联网自治域级和路由级的拓扑网络、上层的点对点网络、万维网上的在线社会网络等等。这些网络不仅规模大、结构复杂,而且其结构直接影响网络上的群体行为,从而影响网络的功能。因为这类信息网络与我们的日常生活息息相关,所以深入理解这些网络的拓扑性质、演化规律及其结构对功能的影响就显得尤为重要。实际上,自1998年以来,大量的实证研究表明这类网络具有一些共同的拓扑特征,如“小世界”效应、“无标度”性质、模块性等等,并将这类规模很大且结构复杂的网络笼统地称作“复杂网络”。与传统的小规模或者结构简单的网络相比,复杂网络是一个具有较大挑战的研究课题,因此也吸引了多个学科的学者不断加入到这个研究队伍中来,并逐步形成了“复杂网络”这个交叉研究领域。毋庸置疑,扩散与传输是信息网络上最常见的群体行为,例如信息包在互联网各路由器之间的传递,新闻、舆情、口碑等在在线社会网络中的扩散等。于是,一个很自然的问题就是：底层的网络结构对扩散和传输行为有何影响?这正是本文研究的两个问题。具体地,主要研究内容和成果如下：1、分析了含权网络上的扩散行为,结果表明：边权分布越弥散扩散速度也就越慢,且扩散速度在达到峰值之后呈现幂率衰减行为(SI模型)；边权的非对称性对扩散阈值有重要影响,可以通过对边权的非对称性进行平衡或再分配从而增大或减小网络的扩散阈值(SIS模型)。2、分析了含有群落结构的无标度网络上的扩散行为,结果表明：当无标度网络的模块性较大时,全局同步扩散行为将会消失：而在一个中等的模块性下,网络群落内部的同步扩散行为存在一个最小值;随着网络节点的平均度逐渐增大,同步行为存在一个明显的相变行为(SIRS模型)。3、从扩散的角度分析了复杂网络的同步性能,结果表明：拉普拉斯特征值之比相同时,网络的同步性能也可能大不一样。具体地,通过理论分析和数值模拟发现了同步时间和最大延时容忍与网络的拉普拉斯特征值之间的对应关系,适当的延时能够提高网络的同步速度。4、着眼于扩散行为对网络结构演化的反向影响,提出了一个权重网络的演化模型。该模型能够生成生成具有幂率度分布、幂率点权分布、幂率边权分布、点权与节点度非线性相关、大的簇系数、度度相关性为负的权重网络。5、针对无标度网络,提出了一种有效路由策略。与传统的最短路径路由相比,该有效路由策略能够较大地提高网络的处理能力,从而缓解网络的拥塞。本论文中的研究结果有助于更好地理解信息网络上的扩散和传输行为的特征和机理。更多还原

【Abstract】 Spurred by the development of information technology and the advance of social civilization, more and more large-scale information networks emerge. Typical exam-ples include AS-level and router-level topological networks of the Internet, peer-to-peer overlay networks, and online social networks in the World Wide Web. As the networks are closely related to our daily life, it is of utmost importance to search proper methods to characterize basic properties and the evolution of a network’s structure, to understand the interplay between the structure and the function of a network. Actually, since 1998 a number of empirical studies have shown that most large-scale networks have some common topological properties, such as the well-known’small-world’effect, scale-freeness, modularity, etc. The kinds of large-scale networks are called roughly’complex networks’. In contrast to simple and small networks, complex network is a very chal-lenging object for research, which attracts more and more attention of interdisplinary researchers recently.Diffusion and transmission are two important processes taking place in various information networks, such as transmission of packets among ASs or routers in the Internet, diffusion of news, public events or sentiment as well as experience in online social networks, and so on. An important and interesting question is:how does the underlying network structure affect the diffusion and transmission of information on a network? That is the subjectⅠstudied in the thesis. Detailedly, the contents and main results of the thesis are summarized as follows.1. I have studied the diffusion on weighted scale-free networks and found that the large dispersion of edges weights induce slow diffusion, and the velocity of the diffusion decays in a power-law form after its peak value (SI model). Besides, my results also show that one can restore the diffusion threshold by redistributing or balancing the asymmetric weights of edges (SIS model).2. I have studied the SIRS diffusion on scale-free networks with communities and found that there exists a critical value of the modularity which separates the global diffusion-induced synchronous phase and asynchronous phase, and the intra-community synchronization is weak while the modularity equals one medium value.3. I have analyzed the synchronization phenomena on networks from a view point of diffusion and found a relationship between the synchronizing performance, including synchronizing speed and time-delay tolerance, and the Laplacian eigenvalues of the network. Furthermore, I found that proper time-delay can improve the synchronizing speed.4. Based on the reverse effects of diffusion on network structural evolution, I have thereby proposed an evolutionary model for weighted complex networks. This model can generate weighted scale-free networks with power-law node-degree distribution, power-law node-strength distribution, power-law edge-weight distribution, assortativ-ity, nonlinear degree-strength relation and large clustering coefficient, which were dis-covered widely in real-world information networks.5. I have also proposed an efficient routing strategy which, comparing with the traditional shortest path routing, can improve the transmission capacity and thus can reduce the congestion of scale-free networks in general. The results in the thesis contribute to a better understanding of information diffu-sion and transmission on real-world large-scale networks.更多还原