基于多目标免疫算法的复杂网络社区结构检测

摘要

随着科技的高速发展,人类社会已经步入了一个信息万变的网络时代。在现实世界中,很多复杂的系统可以表示为网络的形式,比如说社交网络、蛋白质生物网络、协作网和引文网络等。一般来说,网络可以表示为图的形式,其中图中的顶点(或节点)代表着网络中的对象,而图中的边则可以表示对象间的连接信息。近年来,对复杂网络的研究吸引了来自各个学科领域的学者。研究发现,社区结构是复杂网络中最重要的网络拓扑属性之一。挖掘复杂网络的社区结构,具有非常重大的意义,它可以帮助我们发现新的规律和现象,有助于更深刻地理解和认识网络结构和功能之间的关系。
　　近年来,相继有很多经典的社区结构检测算法被提出,其中基于模块度的优化方法是其中的一个重要分支。但是,有学者提出模块度函数本身存在分辨率限制问题。自此,复杂网络的多分辨问题逐渐引起了学者的关注。为了揭示网络的多分辨结构,很多定量的指标和方法相继被提出。但是,这些方法均需要预先设定一个调节参数来确定网络的多分辨结构。
　　进化多目标优化主要研究如何利用进化计算方法求解多目标优化问题,它已经成为进化计算领域的研究热点之一。本文所做的工作,主要是将复杂网络的社区结构检测看作一个多目标优化问题,利用进化多目标算法的优势,求解复杂网络的社区结构。本文所做的工作如下:
　　(1)针对复杂网络的多分辨率问题,提出了一种基于多目标免疫算法的多分辨社区结构检测方法。算法的目的是在一次程序运行的情况下,能够得到代表网络不同分辨下社区结构的一组折中解集。通过采用一种高效的进化多目标算法NNIA,同时优化两个具有一定冲突的目标函数 Modified Ratio Association(MRA)和Ratio Cut(RC)。其中,优化MRA趋向于将网络划分为小的社区,而优化RC则趋向于将网络划分为大的社区。同时优化这两个目标函数,就可以得到两个目标间的折中解集,其中的每一个解代表着某一分辨率下的网络划分结构。在人工和真实网络上的实验表明,该算法在揭示网络的多分辨结构方面具有很高的效率。
　　(2)针对复杂网络问题,为了减小解的搜索空间,提高进化多目标算法的搜索效率,在本文中,我们提出了一种基于多目标密母算法的社区结构检测方法,即MIMA-Net算法。该算法采取以下策略来提高网络划分结构的质量:(a)采用Random Walker的方式对初始解进行预处理操作;(b)在进化过程中,为了提高算法的局部搜索能力,加入了 NBI的局部搜索分解策略,以提高算法全局搜索能力。通过大量的实验以及和其它算法的对比,本文提出的 MIMA-Net算法在各个数据集上都取得了较好的结果,从而验证了Random Walker和NBI局部搜索分解策略这两种方式的高效性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景和意义

1.2 复杂网络的特性

1.3 复杂网络社区结构的研究现状

1.4 论文的主要内容与结构安排

第二章 复杂网络及进化多目标算法相关理论

2.1 复杂网络的表示方式

2.2 复杂网络社区结构检测算法

2.3 复杂网络的多分辨结构检测方法

2.4 进化多目标算法相关理论

第三章 基于多目标免疫算法的多分辨社区结构检测算法

3.1 相关工作

3.2 MICD算法介绍

3.3 实验结果分析

3.4 本章小结

第四章 基于进化多目标密母算法的社区结构检测

4.1局部搜索

4.2 算子介绍及算法流程

4.3 实验结果分析

4.4 本章小结

第五章 总结和展望

5.1 本文总结

5.2 展望

致谢

参考文献

硕士期间成果