论文部分内容阅读
信息化时代的21世纪,现实世界中的复杂网络无处不在,而复杂网络都是以连接复杂系统中各部分之间的纽带的形式存在,如社交系统中的关系网络,生物系统中的蛋白质网络,科技系统中的万维网等。网络的属性除了小世界效应和无标度网络特性之外,还有一个非常重要的社区结构特性,所以,对复杂网络的拓扑结构的分析、功能的理解和潜在规律的挖掘不仅具有是重要的理论意义,更具有广泛的应用前景。近年来,有很多的关于复杂网络社区检测问题的算法被提出,其中基于计算智能算法的优化方法表现突出。本文主要研究蚁群优化算法及其在复杂网络社区检测中的应用,提出了两种基于蚁群优化算法的复杂网络社区检测算法。本文所做的主要工作如下:(1)研究了基本蚁群优化算法的理论和算法模型,以及蚁群算法在优化社区检测问题中的应用,并针对其中存在容易陷入局部最优和计算资源浪费的缺陷引入了智能蚁群的概念,智能蚁群具有继承历史较优解信息的继承学习能力,也具有自我提升进一步改善自身解的质量的自学习能力,通过优化模块度函数,智能蚁群和普通蚁群相互合作能够以更高的效率找到质量更高的全局最优划分。(2)考虑到社区检测算法中传统单目标优化算法存在的分辨率限制问题,借鉴基于分解的多目标进化算法(MOEA/D)的算法框架,针对复杂网络社区检测问题,设计了用于复杂网络社区检测问题的基于分解的多目标蚁群优化算法(Multiobjective Ant Colony Optimization based on Decomposition,简称MOACO/D-Net)。首先将社区检测问题模型化为一个同时优化ratio association和ratio cut两个目标函数的多目标优化问题,并利用MOACO/D-Net算法同时优化这两个目标函数,搜索问题的Pareto最优前沿面。在设计MOACO/D-Net算法时,每只蚂蚁负责搜索一个子问题的解,所有蚂蚁被分为若干组,每组共用一个信息矩阵,蚂蚁利用伪随机概率选择模型构造解。实验表明,算法可以有效地避免了分辨率的限制问题,得到了网络在不同分辨率下的划分。我们还分析了蚁群算法中重要的几个参数对算法性能的影响,包括信息素因子α、启发式因子β,信息素保留系数ρ和蚁群规模m等。并通过组合实验找到了每个参数在社区检测问题上的较优取值范围。本文工作得到如下基金资助:国家自然科学基金(No.61003199),中央高校基本科研业务费专项资金资助(Nos.JB140216和K5051202019)。