基于最小生成树聚类的遗传算法的复杂网络社区挖掘方法

摘要

基于最小生成树聚类的遗传算法的复杂网络社区挖掘方法属于复杂网络社区挖掘技术领域，其特征在于，包括以下步骤：计算机初始化、种群初始化、用最小生成树法对种群聚类、对种群内聚类后的各个体进行单点交叉操作、变异操作和选择操作、迭代T次得到复杂网络的最佳社区划分。本发明通过对种群进行最小生成树聚类，利用种群间的交叉，维持种群多样性，抑制未成熟收敛现象，利用物种间较优的个体进行交叉操作，增大了搜索含有更优解的空间的概率，通过选择使局部模块度M_l最大的邻居结点作为变异值，提高了算法的搜索效率。

主权项

基于最小生成树聚类的遗传算法的复杂网络社区挖掘方法，其特征在于，是在计算机中依次按以下步骤实现的：步骤(1)，计算机初始化，设定以下参数：复杂网络，用G(V,E)表示，V为结点v的集合，网络中结点v的编号为(1,2,3,...,|V|)，v∈(1,2,3,...,|V|)，|V|为结点v的总数，E为边e的集合，e∈(1,2,3...,|E|)，|E|为边e的总数；基因，表示一个结点v；种群，用Pop表示，指的是复杂网络若干可能的社区划分结果，社区方法称为社区挖掘方法S,s为属于S中的一种划分方法，s∈S，|S|表示划分方法的总数，其中的任何一种划分结果称为个体，用Pop(s)表示，所有可能的划分结果数称为种群规模；个体的编码，是用于表示某种划分结果的一个数组或位串，也称染色体，所述基因在所述染色体中的位置称为基因座或基因位，同时也表示所述复杂网络中的一个结点，所述染色体所对应的是一个所述复杂网络的一种划分方法，所述染色体的解空间对应于全部可能的划分方法，从所述的解空间映射到一个所述的染色体，称为编码，从一个所述的染色体映射到所述解空间，称为解码；步骤(2)，种群初始化：步骤(2.1)，任意选择一种复杂网络社区划分的结果，用个体Pop(s)表示；步骤(2.2)，同一个所述复杂网络G(V,E)中结点v的总数|V|表示所述个体Pop(s)的编码长度，为|V|位，各个结点v的等位基因全部为零；步骤(2.3)，对于所述个体Pop(s)中的每个结点v，建立邻居结点集N(v)＝{u|(u,v)∈E}，u表示邻居结点；步骤(2.4)，随机选择步骤(2.3)中某个结点v的所述邻居结点集N(v)＝{u|(u,v)∈E}中的一个结点u′作为所述结点v在自身邻居节点集N(v)＝{u|(u,v)∈E}中的一个等位基因，用Pop(s,v)＝u′，表示个体Pop(s)中结点v在邻居节点集N(v)＝{u|(u,v)∈E}中的一个等位基因；步骤(2.5)，对种群Pop中的各个个体Pop(s)按步骤(2.1)～步骤(2.4)循环|S|次，完成种群初始化；步骤(3)、对于一个设定的个体Pop(s)，用一个网络模块度函数Q表示种群Pop对各个体Pop(s)的适应度，用Q表示一个复杂网络社区挖掘的充分度，所有结点p，q实际连接边的数目越大，表示社区挖掘越充分，Q值也越大；其中：|E|为所述复杂网络的总边数，A＝(A_pq)_|V|×|V|表示复杂网络的结点邻接矩阵，A_pq＝1，表示结点p、q间用有向边连接，反之，则A_pq＝0，$\left|E\right|=\frac{1}{2}\underset{pq}{\Sigma }{A}_{pq},$k_p、k_q分别表示结点p、结点q的度数，度数是指一个结点所连接的有向边数，r(p)、r(q)分别表示结点p、结点q所在的社区，对于函数δ(r(p),r(q))，若δ(r(p),r(q))＝1，则表示结点p和结点q在同一社区中，r(p)＝r(q)，否则，δ(r(p),r(q))＝0，表示r(p)≠r(q)，结点p和结点q不在同一社区，δ(r(p),r(q))＝1，表示所有社区内，实际连接边数目占网络的总连接数目之比，δ(r(p),r(q))＝1，表示在随机情况下，所有社区内，期望连接边数目占网络的总连接数目之比，把Q存入种群在一种划分方法s下的适应度数组Pop_Q中；步骤(4)，对于所有的网络社区划分方法S，按步骤(3)计算Pop_Q(s)，得到一个对应于一个种群的Pop_Q；步骤(5)，按以下步骤对种群进行聚类：步骤(5.1)，利用归一化共用信息I(Pop(s_A),Pop(s_B))度量一个种群中两个个体Pop(s_A)和Pop(s_B)间距离d，步骤如下：步骤(5.1.1)，按下式计算归一化共用信息I(Pop(s_A),Pop(s_B))其中：C为置乱矩阵，共有I行J列，所述I是第一种划分方法s_A中包含的社区数，所述J是第二种划分方法s_B中包含的社区数，C_i.是所述置乱矩阵C中第i行的元素之和，i＝1,2,...,i,...,I，C_.j是所述置乱矩阵C中第j列的元素之和，j＝1,2,...,j,...,J，V_ij是第一种划分方法s_A中的社区i和第二种划分方法s_B中的社区j共同拥有的结点数；当没有共同结点时，V_ij＝0，当有部分共同结点时，V_ij为其交集中的结点数，当所有结点都相同时，V_ij取社区i或社区j中的结点数，|V|为所述复杂网络中的结点数，当第一种划分方法s_A的结果和第二种划分方法s_B的结果完全相同时，I(Pop(s_A),Pop(s_B))＝1，当第一种划分方法s_A的结果和第二种划分方法s_B的结果不同时，I(Pop(s_A),Pop(s_B))＝0，步骤(5.1.2)，按下式计算两种划分方法的结果Pop(s_A)和Pop(s_B)间的距离d：d＝1‑I(Pop(s_A),Pop(s_B))；步骤(5.2)，按以下步骤，利用最小生成树对种群Pop进行聚类：步骤(5.2.1)，按下式所述计算种群Pop中各Pop(s)间的距离矩阵，是一个下三角的种群各个体间距离的矩阵：$\left[\begin{array}{cccccccc}0& & & & & & & \\ d\left(Pop\right(S_2),Pop(S_1\left)\right)& 0& & & & & & \\ d\left(Pop\right(S_3),Pop(S_1\left)\right)& d\left(Pop\right(S_3),Pop(S_2\left)\right)& & & 0& & & \\ \mathrm{...}& \mathrm{...}& \mathrm{...}& & & & & \\ d\left(Pop\right(S),Pop(S_1\left)\right)& d\left(Pop\right(S),Pop(S_2\left)\right)& & \mathrm{...}& & d\left(Pop\right(S),Pop(S_S\left)\right)& \mathrm{...}& 0\end{array}\right]$步骤(5.2.2)，利用Prim算法根据步骤(5.2.1)得到的结果生成由|S|‑1条距离最短的有向边组成的最小生成树，每条有向边反映了该有向边的起点和终点之间的最短距离，步骤如下：步骤(5.2.2.1)，对所有的|S|‑1条最短有向边定义一个结构体数组edge[|S|‑1]，其中包括：fromvex,每条有向边的起点，endvex，每条有向边的终点，所述起点fromvex和终点endvex间的距离d，表示各边的权重；步骤(5.2.2.2)，按以下步骤对所述种群各个体间的距离矩阵使用Prim算法，得到由|S|‑1条距离最短边组成的最小生成树：步骤(5.2.2.2.1)，在所述种群各个体间的距离矩阵的第1列j₁中找出其余各个个体中离个体Pop(s₁)距离最近的一个个体Pop(s₁′)，步骤(5.2.2.2.2)，在所述种群各个体间的距离矩阵的第2列j₂中找出其余各个体中离所述个体Pop(s₁′)最近的一个个体Pop(s₂′)，…,一直到第|S|列为止，得到|S|‑1条最短边，步骤(5.2.2.2.3)，计算所述最小生成树中|S|‑1条最短边的平均距离d_cp，并把所述|S|‑1条最短边中小于1.11*d_cp的最大距离作为权重下限值，步骤(5.2.2.2.4)，从所述个体Pop(s₁)开始，向下遍历所述|S|‑1条最短边，去掉其中权重大于所述权重下限值的所有边，使所述最小生成树断裂成为一个森林，完成种群的聚类划分，再对所述森林中的各段最小子生成树中的个体进行类别标记，保存到类别数组classid[|S|]中，类别标记包括：类别序号以及各个体Pop(s)的排序号；步骤(6)，依次按以下步骤对步骤(5.2.2.2.4)得到的分属于不同类别的个体Pop(s)进行单点交叉操作，以提高社区最优划分的速度，步骤如下：步骤(6.1)，设定：交叉概率P_c＝0.8，选择性地随机生成一个0～1之间的小数r₁，条件为r₁＜P_c，步骤(6.2)，按以下步骤进行轮盘赌选择：步骤(6.2.1)，计算种群Pop中所有个体Pop(s)适应度的总和步骤(6.2.2)，随机生成一个个体适应度累积和的界限值rand＝r₂*Q_sum，r₂为0～1之间的小数，累积计算种群Pop前|s|个个体Pop(s)的个体适应度累积和，一直到不小rand值，此刻的|s|值即为选中的个体Pop(s)编号，|s|＝1,2,3,...,|S|；步骤(6.2.3)，判断步骤(6.2.2)中编号为Pop(s₁)的个体和被选中的编号为s的个体是否在同一类别中，classid(s₁)是否等于classid(s)；若相等，比较个体适应度值Pop_Q(s₁)和Pop_Q(s)，淘汰适应度较低的个体，返回步骤(6.2.1)，一直到两个个体Pop(s₁)和Pop(s)不在同一类别中，执行步骤(6.2.4)，若不相等，则执行步骤(6.2.4)，步骤(6.2.4)，按以下步骤对步骤(6.2.3)得到的两个不在同一类别中的个体完成单点交叉，并保存到子种群Pop2中，步骤(6.2.4.1)，在步骤(6.2.4)中两个不属于同一类别的个体的个体编码串中，设定一个相同的交叉点jcross，jcross∈(1,2,...,|V|)，jcross是一个位号，步骤(6.2.4.2)，把个体Pop(s₁)的个体编码串中第jcross位到第|V|位与被选中的Pop(s)的个体编码串中的第jcross位到第|V|位进行互换，生成两个新的个体保存到所述子种群数组Pop2中；步骤(6.2.5)，重复执行步骤(6.2.1)～(6.2.4)共|S|/2次，完成所有个体的交叉操作，得到Pop2(S)；步骤(7)，对步骤(6.2.5)的结果按以下步骤进行变异操作，以强化变异操作的变异算子的局部搜索能力，提高搜索性：步骤(7.1)，定义：弱社区，社区内部总的边数edge_in大于社区与网络其他部分相连的边数之和edge_out，局部模块度M_l值表示社区划分的充分度，M_l越大，表示社区划分越合理；步骤(7.2)，依次按以下步骤对所述子种群Pop2中的个体执行变异操作：步骤(7.2.1)，依次按以下步骤对步骤(6.2.5)得到的Pop2(S)的个体Pop2(s)解码得到其社区划分结果：步骤(7.2.1.1)，获得Pop2(s)中所有的有向连接边，并将所述有向边按边的结点编号顺序排列，步骤(7.2.1.2)，初始化全部所述有向连接边的遍历状态，设定：全部所述有向连接边的访问向量visited，是一个1×|V|的向量，向量分量用0、1表示，1表示已遍历，0表示未遍历，初始时为0，全部所述有向连接边的社区编号向量lables，是一个1×|V|的向量，向量分量表示结点编号的社区编号，表示社区的划分结果，初始化时为0，循环控制变量，用结点编号n表示，初始时，n＝0，步骤(7.2.1.3)，从Pop2(s)的循环控制变量n开始遍历，未遍历，visited[n]＝0，则社区编号l＝1，遍历后，lables[n]＝l，visited[n]＝1，步骤(7.2.1.4)，继续执行步骤(7.2.1.3)，按结点编号顺序遍历，一直到n＝|V|为止，执行步骤(7.2.1.5)，步骤(7.2.1.5)，找出所有与结点n有有向连接边、但尚未遍历的结点编号，组成结点编号集{u_n}，重复循环执行步骤(7.2.1.3)～(7.2.1.4)，对结点u₁标注，lables[u₁]＝l，visited[u₁]＝1执行步骤(7.2.1.6)，步骤(7.2.1.6)，找出所有与结点u₁有有向连接边，但尚未遍历的结点组成结点编号集{w},对{w}中的结点w执行步骤(7.2.1.5)，直到编号集{w}中结点编号都遍历完，再执行步骤(7.2.1.4)，一直到结点|V|结束；步骤(7.2.2)设定：编译概率P_m＝0.03，选择性地随机生成一个0～1间的小数r3，使r3＜P_m，步骤(7.2.3)，判断个体Pop2(s)的结点v的编号是否小于所述基因的编码长度，若结点v的编号等于或大于编码长度|V|，则退出，若结点v的编号小于编码长度|V|，则获取结点v上作为邻居结点的邻居结点以及其社区标签lables，执行步骤(7.2.4)，步骤(7.2.4)遍历步骤(7.2.3)中各邻居结点的社区标签并计算邻居结点属于各自社区时的局部模块度M_l，步骤(7.2.5)，从步骤(7.2.4)的结果中找出能使M_l最大的社区标签再随机取社区标签的一个结点作为变异值，步骤(7.2.6)，重复执行步骤(7.2.3)～步骤(7.2.5)，直到Pop2(S)中的个体Pop2(s)都完成变异操作；步骤(8)，按以下步骤执行选择操作：对第一代的种群Pop和步骤(7.2.6)中所得到的子种群Pop2中的各个体Pop(s)和Pop2(s)的个体适应度进行统一地由高到低的排序，取排序后的结果中的前|S|个个体作为下一代种群；步骤(9)，重复执行步骤(5)～步骤(8)，得到社区最佳划分；步骤(9.1)，设定迭代次数T＝100，步骤(9.2)，执行迭代操作，步骤(9.3)，判断迭代次数t：若t≤n,则返回步骤(5)，取n＝20,0<n<T若n<t<T，则返回步骤(6)，步骤(9.4)，t＝100时，得到复杂网络最佳社区划分。