论文部分内容阅读
随着社会科技的迅速发展,复杂系统已经遍布我们生活的方方面面。复杂网络作为复杂系统的一种抽象表现形式而存在,它通常可以抽象为图的形式,即把节点表示为对象,节点之间的连线表示节点之间存在的一定联系。而社团结构又是复杂网络的一个重要特性。一般情况下,社团内部的节点之间连接比较紧密,社团之间的节点连接都比较稀疏。因此发现复杂网络内部的社团结构,对理解网络的拓扑结构和作用具有非常重要的意义。复杂网络社团结构划分算法主要是发现复杂网络中真实存在的社团结构,研究人员提出了一系列的算法来检测复杂网络中潜在的社团结构,以便更好地分析复杂网络。传统社团发现算法大多选择模块度作为社团结构的评判函数,近年来有关研究表明模块度存在一定的分辨率问题,为了解决该问题,有关研究人员提出了模块密度作为新的社团评判函数。本文选择模块密度作为社团结构的评判函数,采用化学反应算法,提出了一种新的社团结构检测算法。本文主要工作及创新点如下:(1)研究了复杂网络社团的评判函数及其相关的一些社团结构发现算法。社团结构作为复杂网络的一个重要方面,研究者提出了很多发现算法,寻求最优划分方法一直是研究重点。论文研究了相关算法各自的优点及缺点。(2)研究了化学反应优化算法。化学反应优化算法是计算机领域与化学领域相结合而孕育出来的,是一种元启发式算法。该算法模拟了化学反应中分子与分子间的相互作用,通过寻找整个分子集中的最小分子势能得到最优解。(3)提出了基于化学反应算法优化模块密度的复杂网络社团检测算法。本文利用模块密度作为适应度函数,采用化学反应优化算法,设计实现了单分子撞墙反应算子、单分子分解反应算子、多分子交换反应算子和多分子合成反应算子。实验结果表明,与几种经典的算法相比,所提算法划分结果更加精确高效。(4)引入精英保留策略,从而提高算法的收敛速度。在化学反应算法中,由于分子动能的存在,使得原本结构较好的分子在反应过程中改变为相对结构不优的分子。这种现象使分子种群丰富,但有可能在有限的迭代次数中找不到最优解,使得算法收敛速度比较慢。精英保留策略在分子反应前搜寻最低势能分子,保留下来,在下次反应迭代前用势能最低分子替换掉势能最高分子。(5)引入爬山局部搜索算子,提高算法局部搜索能力。化学反应优化算法具有良好的全局搜索能力,为了提高其局部搜索能力,在算法中加入爬山法局部搜索法作为局部搜索算子,使得算法更加精确高效。