论文部分内容阅读
现实世界中的很多复杂系统可以由网络表示出来,如技术网络、社交网络、交通运输网络及生物网络等。这些网络经过建模以后可抽象化为图,其中节点表示对象,节点之间的连接可以表示对象之间具有某种关系。社团结构是复杂网络的一个重要特性,它可以定义为网络中的一个由若干节点构成的子集,其内部节点之间连接紧密,而与网络中其他节点之间的连接较为稀疏。研究社团结构对于分析复杂网络的拓扑结构、理解复杂网络的功能、预测复杂网络的行为具有重要的意义。近年来,社团检测问题受到了各个领域的学者的广泛关注,许多算法也相继被提出来,如图划分方法、层次聚类法、谱聚类法、基于相似度的方法以及基于进化的优化算法等。密母算法是计算机科学和社会生物学的交叉产物,它建立在模拟文化进化基础之上,实质是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体。经过多年发展,密母算法已被越来越多的研究人员接受并广泛应用到组合优化、模式识别、图像处理等领域中。本文针对复杂网络社团检测进行了系统地研究,所取得的主要研究成果为:1.研究进化算法的基本理论,并深入理解密母算法及其改进算法在复杂网络社团检测问题中的应用。在此基础上,提出了一种利用局部结构信息的密母算法(Memetic algorithm using local structural information,MA-LSI)用于解决复杂网络的社团检测问题。在该算法中,利用模块度函数Q作为适应度函数,并利用一个局部社团的质量评价函数来定义局部搜索算子,此外还采用了一种节点移动策略来改善划分结果。与经典的快速纽曼(Fast Newman,FN)聚类算法和其他密母算法相比,实验结果表明该算法可以产生更为精确的划分结果。2.研究了传统的模块度优化所具有的分辨率限制问题,采用另外一个可以克服分辨率限制问题的目标函数:扩展模块度密度函数。该函数中含有一个可调参数,通过改变参数的取值可以实现以不同分辨率分析网络,从而检测出网络的多分辨结构。基于扩展模块度密度函数的优化,提出另外一种密母算法(Memetic algorithm with simulated annealing strategy and tightness greedy optimization,MA-SAT)用于复杂网络社团检测。该算法中有两个局部搜索算子,一个采用了模拟退火策略,另一个采用了局部社团紧密度函数的贪心优化。模拟退火策略可以加速算法的收敛且有助于算法跳出局部最优,紧密度贪心优化充分利用了网络的结构信息来产生邻居划分,计算代价小并且有助于提高种群的多样性。与几种经典算法对比的实验结果表明该算法是非常有效的。本文工作得到如下基金资助:国家自然科学基金(No.61003199),中央高校基本科研业务费专项资金资助(Nos.JB140216和K5051202019)。