复杂网络中的多目标动态社区检测算法研究

作     者：王雯雪 

作者单位：东莞理工学院 

学位级别：硕士

导师姓名：魏文红

授予年度：2024年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 081104[工学-模式识别与智能系统] 08[工学] 070104[理学-应用数学] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：复杂网络 社区检测 启发式变异 多目标优化 演化聚类 

摘      要：近年来,随着网络基础设施的蓬勃发展,复杂网络也越来越贴近人们的日常生活。社区检测能够从复杂网络中提取其社区结构,并通过挖掘社区结构背后的信息来指导人们的现实生活。根据网络结构特征,复杂网络可分为静态社区网络和动态社区网络。动态社区网络可以看作由连续的静态社区网络快照组成,因此动态社区检测问题可以分为静态社区检测算法的研究和时间平滑性的研究。动态社区检测能够反映社区结构随时间变化的演化过程,是当前社区检测领域的研究热点。 目前,多目标进化算法由于其高效的社区划分能力,已成为社区检测领域的主流方法之一。然而,现有的多目标进化算法在解决社区检测问题时存在着搜索空间大、误差累计大和准确率低等缺陷。为了解决这些问题,本文提出基于启发式变异算子的多目标进化算法以及基于演化聚类的多目标动态社区检测算法,其主要内容如下: (1)多目标进化算法解决动态社区检测问题中,第一个网络快照缺乏前置聚类信息的参考,因此被视为静态社区检测问题。为解决静态社区检测中种群多样性差、准确率低的问题,本文提出了基于启发式变异算子的多目标进化算法。该算法利用个体相似度来把控变异方向,增加种群多样性。同时,引入了改进的精英保留策略以减小不必要的搜索空间。实验结果表明,该算法的社区评价指标NMI值和Q值的平均值和最大值都高于其余四种同类比较算法,能够得到更加稳定和准确的社区划分。 (2)针对当前动态社区检测算法容易陷入局部最优的问题,本文提出了基于演化聚类的多目标动态社区检测算法。该算法在演化聚类框架上,设计自适应变异和交叉概率,动态调整不同进化阶段的侧重点,从而提高搜索效率。实验结果表明,与同类比较算法相比,该算法在真实和人工合成的动态数据集中都能获得更高的NMI值,自适应进化策略提高了算法的社区划分能力。 (3)为解决动态社区检测中因初始划分不准确造成的结果漂移问题,本文将基于启发式变异算子的多目标进化算法与基于演化聚类的多目标动态社区检测算法结合。基于启发式变异算子的多目标进化算法用于解决初始快照的社区划分问题,后续快照使用基于演化聚类的多目标动态社区检测算法进行社区划分。实验结果表明,将初始快照使用基于启发式变异算子的多目标进化算法进行处理能够能够使后续快照的社区划分得到更高的NMI值,提高了整体动态社区划分的准确性。