基于局部模块度的遗传算法用于大规模复杂网络社区挖掘的方法

摘要

一种基于局部模块度的遗传算法用于大规模复杂网络社区挖掘的方法，属于复杂网络社区挖掘技术领域，包括：对网络社区划分进行编码；种群初始化；计算适应度函数；进行遗传操作：交叉、变异、选择；解码，得到最佳社区划分。本发明通过在交叉算子中加入轮盘赌选择，而不是随机选择种群中的个体进行交叉操作，使高适应度个体具有优先选择性，可以加快最优划分的产生；在变异算子中引入局部模块度函数，使变异后的候选解更接近最优解，强化了变异算子的局部搜索能力，更具针对性，提高了算法的搜索性能；利用LMGACD算法进行复杂网络社区挖掘可以取得好的划分效果，且时间复杂度较低。

主权项

一种基于局部模块度遗传算法用于大规模复杂网络社区挖掘的方法，其特征在于包括以下步骤：步骤一，对网络社区划分进行编码，方法如下：使用基于基因座邻接的编码来表示由若干个网络社区划分组成的种群中的一个个体，即用一个个体的编码表示一个网络社区划分的结果；在基于基因座邻接的编码表示中，每个基因型g都有n个基因，每个基因都代表了网络N中的一个结点；每个基因i都可以取一个j(j∈(1,2,...n))作为它的等位基因，即i和j之间存在一条连接；基于基因座邻接的编码表示是一种图表示方法，基因型g所表示的图中若i和j之间存在一条边，同时说明了基因型g解码后结点i与j在同一个社区；步骤二，种群初始化，方法如下：①将每个个体初始化为一个n位等位基因全部为0的编码，n为编码长度；②对个体的每个基因位j，找到网络中结点j的邻居结点；③随机选择结点j的一个邻居结点作为基因位j的等位基因，重复步骤②、③，完成个体的初始化；④重复①～③Popsize(种群规模)次，完成种群初始化；步骤三，计算适应度函数，方法如下：个体的适应度能对其给出的社区结构的好坏做出合理的评价，为了定量地刻画网络社区结构划分的优劣，采用网络模块度函数作为群体中个体的适应度函数，所述网络模块度函数为Q函数；Q函数定义为社区内实际连接数目在网络中所占的比例与随机连接情况下社区内期望连接数目在网络中所占比例之差，其表达式为：$Q=\frac{1}{2m}\underset{\mathrm{ij}}{\Sigma }[A_{\mathrm{ij}}-\frac{k_i{k}_j}{2m}]\delta (r\left(i\right),r\left(j\right))$其中，A＝(A_ij)_n×n表示网络N的邻接矩阵,如果结点i与j之间存在边连接,则A_ij＝1，否则A_ij＝0；对于函数δ(u,v)，如果u＝v,其取值为1，否则取值为0；k_i表示结点i的度；m表示网络N中总的边数，被定义为步骤四，进行遗传操作：交叉，变异和选择；步骤五，解码，得到最佳社区划分，方法如下：LMGACD算法进化T代(一般取100≤T≤200)后，得到种群的最佳解，通过解码，识别出最佳解编码的各个组成部分，从而得到网络的最佳社区划分。