论文部分内容阅读
社区发现(又称为社团发现)是复杂网络研究的重要部分,主要目的是挖掘网络中一群相互联系紧密的节点组成的模块。社区发现在推荐系统,危险预警,舆情分析等领域有着广泛的应用。传统基于静态网络的社区发现已有大量研究,并且积累了许多优秀的方法和参数。但是,随着复杂网络的快速发展,新的复杂网络常常具有用户数量多、群体结构复杂、用户社交广泛、发展快等特点。传统静态网络社区发现研究已难以满足当前社区发现需求。动态重叠社区发现研究可以进一步探索复杂网络中社区的复杂性和动态性,是社区发现重要研究方向之一。本文采用一种基于分解的多目标进化算法(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的有效性。