基于分解的多目标进化算法在动态可重叠社团发现中的应用

发布时间：2018-04-22 05:33

本文选题：社区发现 + 多目标进化算法　；参考：《北京邮电大学》2017年硕士论文

【摘要】：社区发现(又称为社团发现)是复杂网络研究的重要部分,主要目的是挖掘网络中一群相互联系紧密的节点组成的模块。社区发现在推荐系统,危险预警,舆情分析等领域有着广泛的应用。传统基于静态网络的社区发现已有大量研究,并且积累了许多优秀的方法和参数。但是,随着复杂网络的快速发展,新的复杂网络常常具有用户数量多、群体结构复杂、用户社交广泛、发展快等特点。传统静态网络社区发现研究已难以满足当前社区发现需求。动态重叠社区发现研究可以进一步探索复杂网络中社区的复杂性和动态性,是社区发现重要研究方向之一。本文采用一种基于分解的多目标进化算法(Decomposition based multi-objective evolutionary algorithm, MOEA/D)解决动态可重叠社区发现问题。基于MOEA/D的动态社区发现算法(MOEA/D based dynamic community detection algorithm ,MOEAD-DCD)同时优化瞬时评分(Snapshot score, SC)和时间消耗(Temporal cost,TC)两类目标函数。SC采用社区发现经典衡量指标,保证每一个时刻社区发现结果的准确性。TC计算相邻时刻间社区发现结果的相似性,保证动态网络社区发现的稳定性。针对复杂网络的重叠社区发现,传统社区发现往往具有较高时间复杂度,针对该问题本文采用了大量经典策略提高算法效率。包括采用轮盘赌方法设计MOEA/D的初始化算子和进化算子,采用前一时刻社区发现结果初始化当前时刻初始解等。MOEAD-DCD采用一种改进的基于邻接轨迹表达的编码方式,使得网络中一个节点可以同时隶属于多个不同的社区结构。通过保留多种非支配解,MOEAD-DCD保证了社区发现结果多样性,避免人为选择多目标函数的影响权重问题。根据文献调研,本文首次将MOEA/D用于解决动态可重叠社区发现问题。MOEA/D算法具有较高运行效率,能够保证最终非支配解多样性的特点。同时结合本文采用的大量改进策略,与传统社区发现算法相比,MOEAD-DCD能够保证准确性的同时,兼顾动态社区结果的稳定性。计算实验对比验证了 MOEAD-DCD的有效性。
[Abstract]:Community discovery (also known as community discovery) is an important part of the research on complex networks. The main purpose of community discovery is to mine the modules composed of a group of closely connected nodes in the network. Community discovery has a wide range of applications in recommendation systems, hazard warning, public opinion analysis, and so on. Traditional community discovery based on static network has been studied extensively, and many excellent methods and parameters have been accumulated. However, with the rapid development of complex networks, new complex networks often have the characteristics of large number of users, complex group structure, wide social interaction and rapid development. Traditional static network community discovery research has been difficult to meet the current community discovery needs. Dynamic overlapping community discovery can further explore the complexity and dynamics of communities in complex networks and is one of the important research directions of community discovery. In this paper, a decomposition based multi-objective evolutionary algorithm (MOEA / D) is used to solve the problem of dynamic overlapping community discovery. Dynamic community discovery algorithm based on MOEA/D (moat / D based dynamic community detection algorithm / MOEAD-DCDD) simultaneously optimizes two kinds of objective functions: instantaneous scoring (SC) and time consuming time cost (SC). SC uses community discovery classical metrics. To ensure the accuracy of community discovery results at each time. TC to calculate the similarity of community discovery results between adjacent moments, and to ensure the stability of dynamic network community discovery. For the overlapping community discovery of complex networks, the traditional community discovery often has high time complexity. In this paper, a large number of classical strategies are used to improve the efficiency of the algorithm. The method of roulette is used to design the initialization operator and evolution operator of MOEA/D, and the initial solution of the current moment is initialized by the result of community discovery. MOEAD-DCD adopts an improved coding method based on adjacent locus expression. So that a node in the network can belong to multiple different community structures at the same time. By retaining a variety of non-dominant solutions MOEAD-DCD ensures diversity of community discovery results and avoids the influence of artificial selection of multi-objective functions. According to literature research, MOEA/D is used for the first time to solve the dynamic overlapping community discovery problem. MOEA / D algorithm has a high running efficiency and can guarantee the diversity of the final non-dominated solutions. At the same time, compared with the traditional community discovery algorithm, MOEAD-DCD can ensure the accuracy and stability of the dynamic community results. The effectiveness of MOEAD-DCD is verified by numerical experiments.
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;O157.5

【参考文献】