一种高效的基于教与学的社区发现算法的研究

发布时间：2020-05-28 20:40

【摘要】：近些年来,对于复杂网络问题的研究越来越多,这个问题受到了各界人士的广泛关注。在我们的现实生活当中,存在许多的复杂网络系统,通过数学建模将它们转变为相应的复杂网络,社区结构就是复杂网络中节点的不同划分的状态。挖掘网络中的社区结构信息是很有意义的行为,它可以帮助我们分析网络中各事物间的关联关系,由此清晰把握网络的整体结构与特征,挖掘网络内部的潜在模式、了解它的内部结构与特性、预测网络行为等。但目前解决复杂网络的社区划分问题算法,大部分还是存在一定缺陷的,例如需要事先知道社区划分数、一些门限值等,而且还存在时间复杂度过高的问题,不适用于许多大型的复杂网络划分问题。Chen等人于2016年提出的了一种新的智能优化算法MODTLBO/D算法,该算法是一个基于教与学的多目标最优化算法,该算法首次采用基于教与学的最优化策略来解决社区发现问题。通过教学阶段(学生向老师学习)与学习阶段(学生之间相互学习)两个阶段,共同作用提高学生的成绩。但在该算法中,每个个体都是从邻居的平均值处进行学习,算法的时间复杂度高,并且在学习阶段,个体仅从邻居处进行学习,这样的操作容易陷入局部最优。为了提高基于教与学的多目标社区发现算法MODTLBO/D的准确率,降低时间复杂度,我们提出了一种在多种群进化策略下的基于教与学的社区发现算法(简称E-MODTLBO/D)。在E-MODTLBO/D算法中,我们采用自适应学习因子,通过这个因子加强在教学阶段的探索与搜索能力;在学习阶段,每个个体在各自的子种群内可以采用随机学习策略或者是改进的量子行为学习策略。在初始化个体时对个体进行预处理,在每次迭代更新后,子种群间进行信息交流,维持算法的多样性与避免早熟收敛。通过进行大量实验对比,E-MODTLBO/D算法在时间复杂度与发现高质量的社区结构方面要优于MODTLBO/D等一些经典社区发现算法,故该算法与目前其他的一些算法相比是具有一定竞争力的。
【图文】：

离散化,启发式算法,启发式,标签

在ＤＴＬＢＯ算法中，个体向量通过一种启发式算法进行初始化，该启发式算逡逑法在２０１２年被Ｇｏｎｇ等人［４７］首次提出，通过标签传播（ＰＧＬＰ）产生群体，具体逡逑表示如图２－１所示。逡逑（逦ｒ逡逑＾逦Ｉ逦Ｉ邋２邋３邋Ｊ邋５邋６邋７邋８逦Ｉ逡逑ｐａ逦ｃｉＮ邋Ｌ＾ｌ邋Ｔ＼［逡逑￣￣？＂邋：邋ＴｈｅｎｍｄｕＵｅｒ：１邋３５邋８逦＾逡逑Ｇｒａｐｈ邋ｔｏｐｏｌｏｇｙ逦｜邋Ｔｈｅ邋ｗｃｏｎｄ邋ｄｕｓｔｅｒ：邋２邋４邋６邋７逦｜逦Ｃｏｍｍｕｎｉｔｙ逡逑图２－１离散化个体表示逡逑１５逡逑

过程图,邻接表,基因,社区

逡逑图２－２以基因为基础的图的邻接表示方法逡逑由上图可以看到，节点１的等位值是２，，于是把节点１与节点２分为相同的逡逑社区内，由于节点２的等位值为４，于是又把节点２与及节点４分到相同的社区逡逑内，以此类推，若有联系则被分到一个社区中，上图则是分了两个社区。逡逑２．４．３交叉与变异概述逡逑接下来介绍两点式交叉法，它有利于均匀交叉，因为两点式交叉法可以更好逡逑的维持网络中的有效连接，在我们的论文中采用的也是这种方法。假设有双亲Ｊ逡逑与５两个子图，我们随机选取两个点／与点．／其中１２／＾５邋Ａ／，在两点之间的逡逑所有值交换，即Ａｋ＜－＞Ｂｋ，ｋ是在／与７＿之间的任意值。交叉的实例如图２－３逡逑所示。逡逑
【学位授予单位】：厦门大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【参考文献】