基于模拟退火遗传算法的网络社区划分方法

摘要

本发明公开了一种基于模拟退火遗传算法的网络社区划分方法，主要解决现有遗传算法中搜索能力较弱和划分效率低下的问题。其实现步骤是：(1)读入一幅网络图；(2)根据网络图，生成邻接矩阵；(3)初始化遗传算法参数；(4)对染色体进行解码，并计算目标函数值；(5)选择目标函数值较大的染色体构成父代种群；(6)对染色体进行交叉和变异，产生新的染色体构成子代种群；(7)初始化模拟退火法参数，进行局部搜索；(8)获得下一代父代种群并进行迭代；(9)判断迭代代数是否达到最大代数Gmax若达到，则终止迭代，输出目标函数值最大的染色体，输出的染色体中对各个节点的划分即为社区中节点的最终划分结果。本发明具有搜索能力强和准确率高的优点。

主权项

1.一种基于模拟退火遗传算法的网络社区划分方法，包括如下步骤：(1)读入一个社区的实际网络图S；(2)根据网络图S，生成网络对应的邻接矩阵，邻接矩阵中的元素由a_ij表示，其中i、j表示网络中任意两个节点，若节点i与节点j相连，则a_ij=1，否则a_ij=0；(3)初始化遗传算法参数初始化迭代次数G_max为50、种群大小S_pop为450、交配池大小S_pool为225、锦标赛选择大小S_tour为2、交叉率P_c为0.8和变异率P_m为1，随机产生S_pop条染色体作为初始种群，染色体表示为：$x_m=[x_m^1{x}_m^2···x_m^i···x_m^N]$其中，向量x_m表示种群中第m个染色体中各个节点所属类别的集合，表示种群中第m个染色体的第i个节点的所属类别，且均为正整数，N表示社区中节点的总数；(4)对每条染色体x_m,m∈{1,...,S_pop}进行解码，并且根据解码后的染色体采用社区划分中常用的模块度函数Q计算适应度值，即目标函数值：$Q=1/2M\underset{\mathrm{ij}}{\Sigma }(A_{\mathrm{ij}}-\frac{k_i{k}_j}{2M})\delta (i,j)$其中M是网络中的边的个数，i,j为社区中任意两个节点，k_i和k_j分别为节点i和节点j的度，A_ij是网络中的邻接矩阵，δ(i,j)表示社区中i和节点j的连接关系，如果节点i和节点j在一个社区中δ(i,j)＝1，否则为δ(i,j)＝0；(5)选择出步骤(4)中目标函数值较大的染色体构成父代种群；(6)对步骤(5)中选择出的染色体进行交叉操作和变异操作，产生新的染色体构成子代种群；(7)初始化模拟退火法中的参数：初始温度T为800000，常数q为0.99，T的循环次数tt为10，并从步骤(6)构成的子代种群中选择出适应度值最大的一个染色体，用模拟退火法进行局部搜索，找到目标函数值最大的染色体加入到子代种群中；(8)对步骤(5)产生的父代种群和步骤(7)产生的子代种群进行由大到小排序，选择目标函数值最大的S_pop个染色体作为下一代父代种群进行迭代，S_pop为种群大小；(9)判断迭代代数是否达到最大代数G_max，若达到，则终止迭代，输出目标函数值最大的染色体，输出的染色体中对各个节点的划分就是社区中节点的最终划分结果，并输出社区的划分结果；否则转到步骤(4)进行下一次循环迭代。