论文部分内容阅读
现实世界中存在大量的复杂系统,这些复杂系统通常被抽象的描述为复杂网络,如生物网、神经网络、因特网、万维网和社会网络等,复杂网络通常具有社团结构特性。研究复杂网络的社团结构有助于更好了解网络系统,并能挖掘出网络系统的潜藏功能,因此检测复杂网络的社团结构是个值得研究的课题,具有非常重要的理论意义和现实价值。最近几十年来,研究者们提出了大量的复杂网络的社团检测算法,进化算法由于具有良好并行性、全局搜索以及对任何函数类可用等特性,因此基于进化算法的社团检测方法成为解决复杂网络社团检测问题的重要方法之一,然而这些算法在非重叠社团检测和重叠社团检测领域值得进一步研究。因此本文提出了基于复杂网络归减的社团检测多目标进化算法和基于混合编码的重叠社团检测多目标进化算法。本文的主要研究工作如下:(1)本文提出了基于复杂网络归减的社团检测多目标进化算法(RMOEA)。当前的社团检测多目标进化算法在小型网络上有着很好的社团检测能力,然而这些算法在大型网络上无法表现出很好的社团检测能力。主要原因在于这些算法没有考虑到网络规模越大,多目标进化算法的搜索空间也会越大。因此本文提出了基于复杂网络归减的社团检测多目标进化算法,算法的主要思想是通过逐步归减复杂网络的规模,逐步减小进化算法的搜索空间,从而提高多目标进化算法的搜索能力。复杂网络归减的策略贯穿整个RMOEA:在进化前利用复杂网络中连接紧密的节点容易被划分到一个社团的特性,对复杂网络进行规模减小,称为预归减;在进化过程中利用种群个体之间存在相同局部社团的特性,对复杂网络进行规模减小,称为进化归减。最后利用了容错处理来纠正减小复杂网络规模过程中的错误点。在人工生成的基准网络数据集和真实网络数据集上与当前的社团检测进化算法进行比较,实验结果表明RMOEA算法可以很好的检测出大规模复杂网络的社团结构。(2)本文提出了基于混合编码的重叠社团检测多目标进化算法(MRMOEA)。当前的社团检测多目标进化算法在非重叠社团上有着很多的研究成果,然而在重叠社团上的研究成果屈指可数,主要原因在于能解码成重叠社团结构的编码很少。因此本文提出了基于混合编码的重叠社团检测多目标进化算法,算法的主要思想是,通过混合编码解决重叠社团检测问题。其中提出混合编码的基因由候选重叠点和非重叠点混合组成,候选重叠点采用离散编码(0或-1),非重叠点采用向量编码。基于混合编码,提出了挖掘候选重叠点的方法以及提出了粒子群的学习方式来产生子代。在真实网络数据集上与当前的重叠社团检测算法进行比较,实验结果表明,MRMOEA算法可以很好的检测复杂网络的重叠社团结构。