基于遗传算法和先验知识的网络社区划分方法

摘要

本发明公开了一种基于遗传算法和先验知识的网络社区划分方法，主要解决技术划分稳定性差，准确率及效率低的问题。其实现步骤是：(1)读入一幅实际网络图，生成邻接矩阵；(2)设置初始化参数；(3)随机生成初始种群；(4)根据邻接矩阵计算适应度值，并选择出适应度值最大的450条染色体作为父代种群；(5)对父代种群中的染色体进行遗传操作，构成子代种群；(6)对子代种群进行局部搜索；(7)合并父代与子代种群，获得新的父代种群；(8)判断步骤(3)中运行代数是否达到50，若达到，则终止运行，输出适应度值最大的染色体中各个节点的划分结果，即社区的划分结果。本发明具有划分结果稳定、划分准确率和划分效率高的优点。

主权项

一种基于遗传算法和先验知识的网络社区划分方法，包括如下步骤：(1)读入一幅实际网络图，并生成网络图对应的邻接矩阵A_ij；(2)设置参数：将社区划分类别数n设为2；运行次数初始值g设为1；最大运行次数g_max设为50、种群S_pop大小设为450、交配池S_pool大小设为225、锦标赛选择S_tour大小设为2、交叉率P_c设为0.8和变异率P_m设为1；(3)更新运行次数g，进行第g次运行：随机生成450条染色体作为初始种群，染色体表示为：$r_m=\left[\begin{array}{cccccc}{r}_m^1& r_m^2& ...& r_m^i& ...& r_m^N\end{array}\right],$其中，向量r_m表示种群中第m条染色体，表示种群中第m条染色体的第i个节点的类别，且均为正整数，N表示社区节点的总数；(4)根据网络图的邻接矩阵A_ij，计算染色体适应度值，并选择出适应度值最大的450条染色体作为父代种群；(5)对父代种群中的染色体进行交叉操作和变异操作，产生新的染色体，构成子代种群；该交叉操作，采用双向交叉，该变异操作，采用单点变异；(6)对子代种群采用模拟退火法进行局部搜索进行局部搜索，并找到适应度值最大的染色体加入到子代种群中；模拟退火法的参数设置为：温度T为800000，常数kk为0.99，T的循环次数tt为10；(7)合并父代种群与子代种群，并选择适应度值最大的450个染色体作为新的父代种群；(8)判断步骤(3)中运行次数g是否达到最大运行次数50，若达到，则终止运行，输出新的父代种群中适应度值最大的染色体，该染色体中各个节点的划分结果就是社区的划分结果；否则，将新的父代种群作为初始种群，并从步骤(3)继续进行第g次运行，直到达到最大运行次数。