一种基于改进遗传算法的复杂网络社区挖掘方法

摘要

本发明公开了一种基于改进遗传算法的复杂网络社区挖掘方法，属于复杂网络社区挖掘方法研究技术领域，具体使用了一种基于聚类和双种群思想融合的改进遗传算法对复杂网络中的社区进行挖掘。本发明使用归一化共用信息相似度标准作为测量种群中个体间的相似度，融合了聚类和双种群思想。首先引入聚类思想，用最小生成树聚类方法对种群进行划分归类，然后引入双种群思想，对聚类确定主类和副类。其中主类维持种群的进化方向，向目标函数的最优解接近；副类则主要为主类适时地提供多样性，使主类在陷入局部最优时可以跳出来，搜索其他的解空间，实现复杂网络社区挖掘的新方法。

主权项

一种基于改进遗传算法的复杂网络社区挖掘方法，其特征在于包括如下步骤：步骤1：计算机初始化；步骤2：种群初始化,每个个体的基因位随机选择其基因位所代表的结点的某一邻居结点的编号作为此基因位的等位基因，得到父种群，步骤如下：(1)每个个体初始化为一个长度为n位的编码，每个基因位的等位基因全为0，n为个体的编码长度；(2)对个体的每个基因位v，找到网络中结点编号为v的邻居结点编号集N(v)＝{u|结点u与结点v直接相连}；(3)随机选择邻居结点编号集N(v)中的一个结点编号u′作为基因位v的等位基因，对初始化种群中个体的步骤进行循环Popsize(种群规模)次，完成种群初始化；步骤3：计算父种群中所有个体的适应度Q，方法如下：$Q=\frac{1}{2E}\underset{\mathrm{uv}}{\Sigma }[A_{\mathrm{uv}}-\frac{k_u{k}_v}{2E}]\delta (r\left(u\right),r\left(v\right))$其中，A＝(A_uv)_n×n表示网络G中结点的邻接矩阵,如果结点u与v之间存在边连接,则A_uv＝1,否则A_uv＝0；δ(r(u),r(v))为社区认同度函数,其中，r(u)表示u所在的社区，r(v)表示v所在的社区，如果r(u)＝r(v),其取值为1，表示结点u和v在同一社区中；否则取值为0，表示结点u和v不在同一社区中；k_u表示结点u的度，k_v表示结点v的度；E表示网络G中总的边数,被定义为步骤4：对种群进行最小生成树聚类，并进行类别标记，确定主类和副类；步骤5：锦标赛选择主类中的两个个体进行交叉和变异操作，生成Popsize/2个后代个体Pop_m；锦标赛选择副类中的两个个体进行交叉和变异操作，生成Popsize/2个后代个体Pop_r；锦标赛选择主类的一个个体和副类中的一个个体进行交叉和变异操作，生成Popsize/2个后代个体Pop_c，其中Popsize＝100，Pop_m和Pop_c取值为50；步骤6：Pop_m和Pop_c构成主类种群的候选解O_m，Pop_r和Pop_c构成副类种群的候选解O_r；根据主类种群目标函数从O_m中用u+λ选择策略选择Popsize/2个个体作为下一代主类种群个体；根据副类种群的适应度函数从O_r中用μ+λ选择策略选择Popsize/2个个体作为下一代副类种群个体，u+λ选择策略即从父代中选择μ个个体，从子代中选择λ个个体，然后再从u+λ个体中选择μ个个体；步骤7：判断δ是否在连续的50代内不再减小，若是，随机生成一部分个体进入下一代的遗传操作；若否，执行步骤8，δ的变化方法如下：δ_t+1＝δ_t+α·Δt其中，α为0～1的小数，t表示当前代数，Δt取值如下：$\mathrm{\Delta t}=\left\{\begin{array}{cc}\frac{1}{\left|G_t\right|}·{\Sigma }_{(p,p^{\prime })\in G_t}\mathrm{Dis}(p,q)-{\delta }_t& \mathrm{if}\left|G_t\right|>0\\ 0,& \mathrm{otherwise}\end{array}\right.$其中，G_t表示在进化代数t时，成功繁殖的双亲对，则|G_t|表示成功繁殖的双亲对的数目，Dis(p,q)表示个体p和个体q间的距离；表示成功繁殖的双亲间的平均距离，δ_t表示第t代时的距离阈值；则Δt表示第t代的成功繁殖的双亲间的平均距离与距离阈值的差；成功繁殖包含两种情况：一是双亲都来自主类，则有一个后代个体比双亲都好即为成功繁殖；二是一个父代个体来自主类，另一个父代个体来自副类，则有一个后代个体比双亲中来自主类的父代个体好，即为成功繁殖；在种群进化过程中，δ不断减小，当种群趋向于收敛时，δ基本不再减小，本发明设置的是在50代内不再减小，就随机生成15个个体进入下一代的遗传操作；步骤8：重复步骤4‑‑步骤7直到到达种群迭代次数T，得到社区最佳划分；所述的复杂网络采用图G(V,E)表示，其中V为结点v的集合，E为边e的集合，设V中结点数为n，E中边的数目为m，则结点v的编号为(1,2,...,v,...,n)，v∈(1,2,...,v,...,n)，e∈(1,2,...,e,...,m)；所述的种群用Pop表示，指的是复杂网络若干可能的社区划分结果，社区方法称为社区挖掘方法用S表示，s为属于S中的一种划分方法即s∈(1,2,...,s,...,S)，S表示划分方法的总数，其中的任何一种划分结果称为个体，用Pop(s)表示，则所有的可能的划分结果的数目称为种群规模，用Popsize表示；所述的个体的编码采用基于基因座邻接的编码表示，该表示中一个基因代表网络中的一个顶点，一个基因的等位基因用它的邻居节点表示。