【作者】 刘亚冰；

【导师】 汪小帆；

【作者基本信息】 上海交通大学 ， 导航、制导与控制， 2010， 硕士

【摘要】 现代的复杂网络科学极大促进了人们对现实复杂系统的理解。社团结构是复杂网络的一个极其重要的特性,社团结构就是一组其内部节点间联系非常紧密而与网络中的其他部分联系相对比较稀疏的节点的子集。复杂网络中的社团结构研究在社会学、生物学和计算机科学等多个领域都具有很重要的意义。近年来,针对不同类型的大规模复杂网络,人们提出了很多寻找社团结构的算法。本文首先对最新的社团结构划分算法进行了综述,给出了该领域重要的研究进展。其次,网络的社团结构特性本质上是由网络的几阶度分布决定一直是网络科学领域悬而未决的问题之一。为此,本文采用高阶随机重连方法和社团检测算法进行仿真实验对该问题进行了研究。最后,有针对性地提出了一种基于Louvain的改进新算法,可以用于寻找加权网络中具有重叠性和层次性的社团结构,并利用该算法分析了在线社会网络Wealink的各种特性,重点分析了Wealink社团特性的发展和演化。本论文所作的主要贡献如下:1综述了该领域最新的比较有代表性的一些寻找社团结构的算法,重点分析了基于模块度指标的改进算法,能够体现社团层次性和重叠性的新算法,衡量社团划分算法好坏的基准图。最后展望了该领域的未来研究方向。2在保持网络一阶、二阶和三阶度相关特性不变的情形下,利用随机重连方法和社团检测算法研究了复杂网络的社团结构特性。仿真分析发现保持网络三阶度相关特性不变的随机重连方法所构造的网络则可以很高精度地呈现原有网络的社团特性,从而表明网络的社团结构可以由三阶度相关特性有效地刻画(不需要更高阶)。本文的研究提供了一种网络构造方法,即利用三阶随机重连方法可构造出能够体现真实网络社团结构这一特性的随机网络。3提出了一种可用于寻找加权网络中社团结构特性的算法,使得新算法能够同时体现出网络中社团的层次性和重叠性,并能够在较短时间内处理大规模的网络数据。其次提出了一种基于微调策略分析动态网络演化中社团特性的算法,能够在网络规模变化不大的前提下对网络高效地进行社团特性的分析。从而为动态网络的社团研究提供了一种较好的途径。最后利用基准图对三种经典算法的优劣性进行了比较。4利用新算法对在线社会网络Wealink(http://www.wealink.com)的结构特性和动态演化进行了实证分析,其中包含了网络规模、社团结构、重叠性节点、聚类系数和度分布等特性,重点研究了若邻网中社团结构的动态演化。更多还原

【Abstract】 The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of complex networks is community structure. A community structure is a densely connected subset of nodes that is only sparsely linked to the remaining networks. Detecting communities in complex networks is of great importance in sociology, biology and computer science and so on.In recent years, a lot of community discovery algorithms have been proposed aiming at different kinds of large scale complex networks. In this paper, we have summarized some latest representative algorithms and have pointed out the important progress in this research area. By which order of degree distribution of networks, the community structure in complex networks can be remarkably maintained is always one problem up in the air in the network science. Then, we have studied the problem with the aid of random rewiring algorithm and community structure detection algorithm. Finally, we have constructed a new algorithm which can detect the hierarchical and overlapping communities in weighted networks. We have analyzed the characteristics of Wealink, especially the dynamic evolutions of communities in the network.The main contributions of the dissertation are summarized as follows.1 We have reviewed some latest representative algorithms, focusing on the improved methods based on the modularity function, algorithms which can detect overlapping and hierarchical community structure in networks, benchmark in detecting communities. We have pointed out some promising directions in this area.2 We have compared the community structures of real networks with computer-generated network models on which the random rewiring process took place and have found that community structure is well maintained after third-order random rewiring. We have established a path towards construction of random graphs matching the community structure property of real networks after the third-order random rewiring.3 We have designed a new community detection algorithm which can detect the hierarchical and overlapping communities of networks in a reasonably short time. We have proposed another new algorithm which can detect the dynamic evolution of communities when the evolution of networks is not so significant when compared to the whole size of networks. We have also used the benchmark graphs to compare the advantages and disadvantages of three main algorithms.4 We have studied characteristics and structural evolutions of a large online social network-Wealink (http://www.wealink.com), including network size, community structure, overlapping nodes, clustering coefficient and the distributions of degree and so on, especially the dynamic evolutions of community structure in the network.更多还原