基于进化算法的复杂网络重叠社团发现算法研究

发布时间：2018-03-26 01:56

本文选题：复杂网络　切入点：重叠社团　出处：《兰州大学》2017年硕士论文

【摘要】：真实世界里的大部分复杂系统可以被抽象成复杂网络模型,而网络模型中研究最多的对象是社团结构,网络中各社团相互作用的结果形成了网络的整体功能。因此,复杂网络研究中的重要内容是社团结构的发现。在所有的社团发现算法中,基于遗传算法(Genetic Algorithm)的社团发现算法是近年来兴起的具有良好研究前景的新领域,遗传算法是一种通过模拟自然进化过程来搜索最优解的方法。本文就是以遗传算法的思想为出发点设计的一种进化算法FEA(Fang Evolutionary algorithm)。FEA不仅能找到社团结构,同时还能找到重叠社团结构。在研究复杂网络的时候,现实世界的大部分复杂网络的社团数目对我们而言是未知的,许多需要事先知道网络中社团个数的算法就无法用来进行网络的社团发现。因此,为了事先能知道网络社团数目这一先验知识,本文中应用网络拓扑结构对应的Laplace矩阵Jordan标准型获取网络社团个数这一先验知识。在得到了网络社团数目后,以模块度函数Q作为评价函数,应用FEA算法对整个网络进行搜索,最终发现重叠社团结构。在经典网络中进行实验,发现本文提出的FEA算法划分出的社团结构符合网络的真实情况,并且与之前研究者的结果相吻合,说明了FEA算法的可行性与正确性,成功将进化算法应用到了重叠社团结构检测中。
[Abstract]:Most of the complex systems in the real world can be abstracted into complex network models, and the most studied objects in the network model are community structure. The result of the interaction of communities in the network forms the whole function of the network. Among all the community discovery algorithms, the community discovery algorithm based on genetic algorithm (GA) is a new field with good research prospect in recent years. Genetic algorithm (GA) is a method to search for the optimal solution by simulating the natural evolution process. In this paper, an evolutionary algorithm, FEA(Fang Evolutionary algorithm).FEA, which is designed based on the idea of genetic algorithm, can not only find the community structure. We can also find overlapping community structures. When we look at complex networks, the number of communities in most complex networks in the real world is unknown to us. Many algorithms that need to know the number of communities in the network in advance cannot be used for community discovery in the network. Therefore, in order to know in advance the prior knowledge of the number of communities in the network, This paper applies the Laplace matrix Jordan standard form corresponding to the network topology to obtain the prior knowledge of the number of network communities. After obtaining the number of network communities, the modular degree function Q is used as the evaluation function, and the FEA algorithm is used to search the whole network. Finally, the overlapping community structure is found. The experimental results in classical network show that the community structure of the proposed FEA algorithm accords with the real situation of the network, and is consistent with the previous results of the researchers. The feasibility and correctness of the FEA algorithm are illustrated, and the evolutionary algorithm is successfully applied to the overlapping community structure detection.
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】