基于免疫遗传算法的复杂网络社区发现
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于免疫遗传算法的复杂网络社区发现范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：
针对大部分基于智能优化算法的社区发现方法存在的种群退化、寻优能力不强、计算过程复杂、需要先验知识等问题，提出了一种基于免疫遗传算法（GA）的复杂网络社区发现方法。算法将改进的字符编码和相应的遗传算子相结合，在不需要先验知识的情况下可自动获得最优社区数和社区划分方案；将免疫原理引入遗传算法的选择操作中，保持了群体多样性，改善了遗传算法所固有的退化现象；在初始化种群及交叉和变异算子中利用网络拓扑结构的局部信息，有效缩小了搜索空间，增强了寻优能力。计算机生成网络和真实网络上的仿真实验结果表明算法可自动获取最优社区数和社区划分方案并具有较高的精度，说明算法具有可行性和有效性。
关键词：
社区发现；复杂网络；免疫原理；遗传算法；单向交叉
0引言
复杂网络的研究中，社区结构的发现目前已成为一个热点问题，近年来受到计算机、数学、生物和社会学等领域研究者的广泛关注。复杂网络中的社区是一组彼此相似并与网络中其他节点存在差异的节点构成的集合，同一社区内部节点相互连接密集，而社区间节点相互连接相对稀疏[1]。目前，在生物网、科技网和社会网等真实网络中均能发现社区结构的存在，复杂网络社区结构的发现对于复杂网络的拓扑结构分析、功能分析和行为预测具有重要的理论意义及实用价值。
由于社区结构的发现对于复杂网络的分析研究具有重要意义，许多研究者研究并提出了许多不同的社区结构发现算法。其中，KernighanLin算法[2]和谱平分法[3]是较早提出的2种社区发现算法，谱平分法对社区数为2的网络社区发现效果明显，但对多社区网络的社区发现效果不是很明显；KernighanLin算法则需以网络社区数作为先验知识，但该先验知识往往是很难获得的。在众多的社区划分算法中最著名的算法是Girvan和Newman提出的GN算法[4]，该算法思想简单，精度较高，但是算法复杂度较高（O（n3）），适用于中等规模的网络。Newman对GN算法进行了改进又提出了一种Newman快速算法（Fast Newman， FN）[5]，该算法与GN算法性能相当，但算法复杂度有了较明显的改进O（n log2n）（O（n2））。随着Girvan和Newman提出的定量描述社区结构的模块性Q函数被广泛使用，许多研究者提出了以Q函数作为目标函数的优化算法，由于遗传算法（Genetic Algorithm， GA）具有较强的全局寻优能力，一些基于遗传的复杂网络社区发现算法[6-10]获得了较好的划分效果，但仍存在一些问题。文献[8]采用基于聚类中心的编码方式，使算法解码困难，计算复杂，不适用于较大规模的网络，并且文献[8]需要先验知识如社区数，使算法的使用受到限制；另外一些算法[10]普遍采用随机生成初始种群、无针对地交叉变异，使算法寻优能力不强，收敛速度慢。
基于复杂网络社区发现算法中存在的问题，本文提出了一种基于免疫遗传算法的复杂网络社区发现算法（Community Detection in complex networks based on Immune Genetic Algorithm， CDIGA），该算法利用改进的字符编码方式，不仅简化了算法的计算而且结合本文设计的遗传算子在不需要任何先验信息的情况下可自动确定网络社区数并获得最优社区划分方案；算法同时采用基于免疫原理的选择算子有效抑制了种群的退化现象，增强了算法的全局寻优能力；并且算法在种群初始化和交叉算子中采用启发式方法使算法搜索的解空间更靠近问题的最优解空间，提高了算法的收敛速度，增强了算法的性能。
1社区结构评价标准
网络社区的发现问题就是要揭示不同类型复杂网络中存在的真实社区结构，但是如何来定量地刻画社区划分的优劣是首先要解决的问题，目前应用较多的是用Girvan和Newman提出的模块性函数来定量地描述网络中的社区，衡量社区结构的好坏。所谓模块性是指网络中连接社区结构内部节点的边所占的比例与另外一个随机网络中连接社区结构内部节点的边所占比例的期望值的差值[11]，其一种表达方式为：
Q=∑ki=1（eii -a2i ）
其中：eii表示所连接的两个节点均在社区i内的边占网络中总边数的比例，ai表示至少有一个节点在社区i内的边占总边数的比例，k为划分的社区数。对于一个特定的网络，一个社区划分方案的Q值越小则表示该划分的社区结构越弱，反之社区结构越强。Q值的范围在-1～1，如果Q值为负数则表示社区内部节点的边没有随机连接得到的边多，一个较明显的社区划分的Q函数值一般在0.3～0.7。本文CDIGA采用Q函数作为目标函数。
2CDIGA
2.1编码方式
受分组遗传算法[12]启发，本文基于字符编码并加以改进作为算法编码方式。具体编码方式为，对于有n个节点的网络，每个个体的基因由表示社区划分信息的n位基因和表示社区个数的1位基因两部分组成，其形式化表示为：
rm=[r1mr2m…rim…rnm|k]
其中：rm表示种群中的第m个个体，rim表示网络中第i个节点被划分到哪个社区的信息，最后一位k表示该个体表示的划分方案将网络划分为k个社区。结合本文所设计的种群初始化方案和遗传算子的操作，通过该编码方式不仅有效解决了字符编码交叉困难的问题，而且可自动确定最优社区个数，同时获得准确率较高的社区划分方案。
2.2种群初始化
由上述编码方案可见，对于一个给定的社区划分问题，遗传算法中不同个体所表示的社区划分方案的社区数k通常是未知的，复杂网络社区划分问题本质上是一个特殊的聚类问题，本文借鉴文献[13]初步确定k值，即如果社区数k未知，则k可为[kmin，kmax]范围内的整数，其中：kmin=2，kmax=round（n）（n为网络中节点数）。据此，种群初始化按照如下方法生成每个个体：首先随机生成一个[kmin，kmax]范围内的整数k作为该个体所代表社区划分方案的社区个数，则每个社区可标记为[1，2，…，k]；然后将个体的每一位基因值随机指定为[1，k]范围内的整数来表示该基因位所代表的节点被划分到哪个社区，这一处理过程重复P次，则可初步生成P个个体。
基于在网络中通常一个节点与其绝大多数邻居节点往往属于一个社区这一特点，为了提高初始种群的多样性，并使种群中初始个体具有一定的精度，本文利用网络的这一局部信息作为启发信息进一步优化初始种群。具体方法为：对个体rm，随机选择1个基因位（代表节点），将其基因值（表示对应节点被划分到哪个社区）复制到该基因位所表示节点在网络中所有邻居节点对应的基因中。例如，对个体rm=[33211321|3]，若某次选择的基因位为3（基因值是2），假设节点3在网络中的邻居节点是2和5，则将个体rm中第2和5两个基因位的值修改为第3个基因位的值（2），即rm=[32212321|3]。对每个个体这一过程重复αn次（α是模型参数，本文取经验值0.4）则完成种群初始化。用这样的方法产生的初始种群在一定程度上使得初始解空间靠近了最优解空间，从而可提高遗传算法的收敛速度。
2.3交叉算子
交叉算子通过互换两个个体的部分基因产生新个体的遗传操作、交叉操作产生的后代个体结合了父代个体的特征，能够产生多样化和有潜在希望成为最优解的新个体，在遗传进化进程中起着全局搜索的作用，决定遗传算法的全局搜索能力。
本文借鉴单向交叉（Oneway crossing over）[14]方法并结合本文采用的编码方式加以改进作为CDIGA的交叉算子，具体操作过程描述如下：
第1步从种群中随机选择两个个体，一个作为源个体src，另一个作为目标个体dest。
第2步从源个体src中随机选择一个基因位，获得该基因的值，即对应网络节点被划分到哪个社区的信息ks，在源个体src中找出所有值为ks的基因位。
第3步若ks≤kd（kd表示目标个体dest表示的社区划分方案的社区个数），则将与源个体src基因值为ks的基因位对应的目标个体dest的基因位的值修改为ks；若ks>kd，则将与源个体对应的目标个体dest基因位的值修改为目标个体基因值取值范围[1，kd]内的随机整数。
第4步重新调整交叉后个体的各基因值，使该个体实际社区数与各基因值所表现的社区号一致。
在迭代过程中，对一个个体上述交叉操作的次数控制在ηn次，η为模型参数，本文取经验值η=0.2，n为网络节点数。上述交叉操作表示将在源个体中划分到同一社区中的节点的信息交叉到目标个体中，而不是像传统交叉那样盲目地进行信息交换，所以不仅能够产生多样化的新个体扩展搜索空间，而且有效促进了算法的收敛。一个具体的交叉操作实例如表1所示。
表1说明了对两个待交叉个体在ks≤kd（左）和ks>kd（右）两种情况下单向交叉操作的过程。其中：v表示待划分网络中的8个顶点，src为源个体，dest（before）为交叉前的目标个体，dest（after）为交叉后的目标个体。若源个体src中被选中交叉的基因位为4（表中左部），则源个体src中对应基因值③表示4号顶点被划分到第3个社区，此时ks（=3）≤kd（=3），与该基因值相同的基因位（表示都被划分到第3个社区的顶点）还有2、8号位，则将目标个体dest（before）中对应3个基因值（4、2、8位）都修改为3，如表中dest（after）所示；若源个体src中被选中交叉的基因位为5（表中右部），此时ks（=4）>kd（=3），则将目标个体dest（before）中与该基因值相同的基因位（1、5、7位）都修改为[1，kd]范围内的随机整数（如2），如表中dest（after）所示。