基于遗传算法的社区发现(2)
比如共同特性，信仰、合作、利益、友谊等等。网络中普遍存在有无标度性[4]
和小世界性[5]
等基本特性。复杂网络的另一重要特性：社区结构[6]
也已被广泛关注，并掀起了科学界的研
究热潮。在这些网络研究中探讨较多的的一个典型特性是社区结构，即将网络划分成具有浓
密的内引线和稀疏顺畅的内部联系的组（也称为群集）。探测网络群集分区可以提供重要的
信息和有用的见解来理解这些关系的结构是如何影响个体和他们的关系的。复杂网络中社区
结构的探测发现意义重大，其在网络的功能分析和行为预测等方面的理论意义与实用价值不
可估量，现已被广泛应用，应用领域如预测陈代谢途径(Pathway)、管理组织结构、社区挖掘、
识别恐怖组织、分析蛋白质相互作用网络等很多领域[7]
.
目前国内外对于社区结构发现领域已经提出了很多行之有效的方法，按照历史发现的顺
序即迭代二分法、层次聚类法、G-N 算法、Radicchi 算法、W-H算法等，具有代表性的算法
有谱平分算法[8]
、Kernighan-Lin 法、凝聚或分裂算法，以及科研工作者对这些算法的改造设
计优化，如将聚类融合引入遗传算法的交叉算子，增强算法寻优能力，如将局部搜索引入遗
传算法的变异算子。这些算法在社团结构划分领域均有好的性能，遗传算法应用于社区探测
领域也是近年来的研究热点，是由于遗传算法区别于传统算法的独特的优势，然后遗传算法
只是解决问题的流程框架，由于其三个算子具体实现的差别，算法应用的性能差别也是很大
的，本文就是对三个算子的具体实现进行设计。模块化 Q 函数是广泛应用于社区结构探测问
题的定量的衡量标准，它是 NP 完全问题[9]
，所以算法所能得出的均是近似最优解，在算法性
能比较上也是近似最优解的比较与分析。
本文组织如下：下一小节是遗传算法基本介绍以及应用遗传算法解决问题的通用基本流
程框架介绍。在第三节，将解决遗传算法与社区发现相结合的接口连接问题，提供了必要的
社区发现问题的数据结构背景来使问题输入输出形式化，给出了一个在社区发现问题中遗传
算法主要步骤结合概述。在第五节，给出了使用 MATLAB 实现遗传算法主要的细节实现。最
后在第优尔节，分析本文算法在给定三个数据集上得到的测试结果，以及对比对每一个数据集测试得到的结果与标准划分的差别分析。2 遗传算法简介
2.1 算法基本介绍
1975 年，John H.Holland 教授出版《Adaption in Natural and Artificial Systems》一书，这
是关于遗传算法(Genetic algorithm, GA)的里程碑性的经典之作，自此以后，遗传算法得到多
领域的广泛应用。遗传算法的历史发展经久不息，于 20 世纪 70 年代兴起，发展于 20 世纪
80 年代，20 世纪 90 年代进入高潮发展。遗传算法以其高效实用、鲁棒性强的性能优化能力，
发展极为迅速。它与以往算法大有不同，大多数优化方法是基于评估函数的变化来产生确定
的解向量，遗传算法不根据这些变化资源，强调概率转换方法来引导其搜索解空间的过程，
它是高效搜索编码的问题参数空间的导向性随机搜索方法，利用根据具体问题而制定的编码
技术。
遗传算法借鉴孟德尔的遗传学说与达尔文的进化论，模仿基因重组与生物进化原理构建
起来的全局随机搜索与优化的方法。本质上它的搜索全局而且并行，搜索方向控制自适应，
自动存取关于搜索空间的资源以达到最优解。遗传算法提供了优化非线性、多目标、多模型