论文:Kaiqi Chen, et al. (2019) – A new genetic algorithm for community detection using
matrix representation method

论文摘要

1、不同于以往的基于遗传算法的社团划分方法,本文作者主要设计了一个和划分结果同构的矩阵表示方法,也就是遗传编码表示,以此来解决遗传算法过早收敛这一缺点。

2、根据矩阵表示的意义设计了交叉算子和变异算子。

3、在计算机生成的网络数据和现实世界网络数据上分别测试了上述算法。

社团结构包含了网络的重要信息,在数据挖掘中对人们的工作有很大的帮助,实际上,已经提出两种基于遗传算法的社团划分方法,或者说是遗传编码方法,分别为:SGR (Tasgin et al., 2008), LAR (Pizzuti, 2008),这两种有着过早收敛这一共同缺点,基于这个事实,作者提出了上述新型矩阵表示方法,这种方法将社团划分的全部信息囊括其中。

相关背景介绍

社团划分在复杂网络研究中的重要地位不言而喻,为了更好的社团划分,研究者们已经提出过很多社团划分算法。

传统划分方法

首先从非遗传算法的方法讲起,Freeman在1997年首先定义了节点中介中心性(vertex betweenness),这个性质描述了节点在图中传输信息的重要性,与节点中介中心性相似,Newman在2002年定义了边的中介中心性(edge betweenness)并且提出了社团划分GN算法:迭代的移除社团间连边直到获得最高的模块度Q(modularity)。

在随后的的研究工作中,Newman定义了一个模块度矩阵,用该矩阵的特征向量重新定义了模块度,随后的研究者们基于这个模块度设计了很多中算法:Newman设计的贪心算法,Blondel提出了Louvain算法,Clauset使用提述的数据结构优化模块度,Philipp提出多步贪心算法,基于图矩阵性质,Donetti使用拉普拉斯矩阵结合层次划分提出更高效快速的社团划分算法,Raghavan更是提出了一种在线性时间内的划分算法:label propagation算法,可以被应用到大规模网络数据中。

基于GA的划分方法

因为社团划分问题是一个NP问题,基于Q的社团划分算法,在本质上是一个求全局最优化的问题,研究者们应用了多种最优化方案,其中遗传算法是最流行的一种。在遗传算法中主要考虑两类搜索空间:

1、伪布尔优化问题:当S为离散空间
B^L = {0, 1}^L
时,即所有长度为L且取值为0或者1的二进制位串的集合时,相应的优化问题在遗传计算领域称为伪布尔优化问题。

2、连续参数优化问题:当S为n维实数空间R^n中的有界集合
S = \Pi^{n}_{i=1}[a_i, b_i]
相应的连续变量的优化问题称为连续参数优化问题。

对于伪布尔优化问题采用的度量是海明距离,对于连续参数优化问题采用的度量是欧氏距离。

遗传算法的流程主要如下图所示:

总的来说遗传算法涉及六大要素:参数编码,初始群体的设定,适应度函数的设计,遗传算子的设计,控制参数的设定以及迭代终止条件。

Tasgin设计提出了TGA算法,使用String-of-Group Representation(SGR),实现了单向交叉和简单变异算子,是社团划分领域中最简单的GA算法,Pizzuti提出了GA-Net算法,应用了Locus-Based Adjacency Representation(LAR),实现了统一交叉和简单变异算子。由于简单性和普遍性,这两种是复杂网络领域目前最广泛应用的遗传优化算法。但是这两种方法都存在过早收敛(premature convergence)这一问题,即最终结果得到的是局部最优而非全局最优,为了解决该问题,研究人员开始将注意力放到辅助算子上,Li和Deng提出了局部搜索改进的方法结果表现优异,Shang提出了MiGA高级遗传算法,结合模拟退火方法局部搜索提高了稳定性和社团划分的准确性,一些研究者还将注意力放到多步处理和初始化上,Said使用划分参数去初始化染色体(CC-GA),CC-GA可以在某种程度上在初始化截断找到真正的社团结构,提高了算法的准确度,Shang提出了APMOEA,网络最开始用affinity propagation初始化,随后应用了多目标优化遗传算法,最终使用外部信息去防止衰退。Shang还提出了结合三种技术的TJA-net算法,用于社团挖掘,在初始化阶段用ILPA将网络划分为子社团,ILPA是结合了KNN和LPA的一种方法,下一步这些子社团基于共同节点进行融合,最后TJA-net修订被错误划分的节点。

这些方法都提高了社团划分算法的性能,但有逐渐复杂需要越来越多的经验性参数,作者认为遗传算法过早收敛的本质原因在于表示方法上,对于SGR,染色体与相应的社团划分结果并不是一对一的关系,一种社团划分方法可能对应着多种染色体,对于LAR,缺点是同样的。为了解决这些问题,作者提出了matrix-based GA社团划分算法,称为MAR。

本文MAR方法

矩阵表示

如上图所示,网络中有三个社团:{1,5,6},{2,4},{3}。定义矩阵为:
CG = (c_{ij})_{n*n}
其中c_{ij}表示节点i,j是否属于同一社团。上图网络相对应的矩阵为:

初始化

在这一步中,随机选取互为邻居的节点放到相同的社团中。

交叉操作

定义交叉矩阵T_l,它是一个对角矩阵,对角中各元素从染色体矩阵CG的第l行获取。故交叉矩阵如下所示:

父母染色体交叉生成后代的操作为:
offspring = (I – T_l)CG_1(I – T_l)^T + T_lCGT_l^T

变异操作

随机选取一个节点放到其随机一个邻居节点所在的社团中。

适应度函数

依然选取模块度作为适应度函数

选择操作

适应度强的前一半个体被选中。

算法流程

仿真实验与结果分析

针对计算机生成网络以及实际网络进行仿真实验,作为对比,选取了三个其他的基于遗传算法社团划分方法TGA,CC-GA,GA-Net以及三个传统社团划分方法GN,FN,LPA。算法评价指标使用NMI指数。

遗传算法参数:种群数量分为大100,中50,小25三种。交叉概率为0.8,变异概率为0.3。

在每个实验中,运行每种算法50次,计算其平均NMI指数、最大模块度指数。

计算机生成网络

使用LFR网络,参数\mu从0-0.45,生成10个128个节点的网络,划分为4个社团,每个社团有32个节点,网络中节点的平均度为16。

实验结果如下,加粗字体为在这一组实验中表现最优的算法。

最大模块度指数信息:

平均NMI指数信息:

实际网络数据

是复杂网络研究中常用的四个网络数据集

  • 空手道社交网络
  • 美国大学生足球社交网络
  • 美国政治书出版网络
  • 新西兰海豚社交网络
  • 世界政治博客网络

实验结果如下,加粗字体为在这一组实验中表现最优的算法:
最大模块度指数信息:

平均NMI指数信息:

不同种群数量与其他算法的对比:

总结

在没有使用多种高级遗传算法的前提条件下,实验结果展示作者MAR编码方式的遗传算法已经获得优异的社团划分结果。MAR方法中,矩阵囊括了社团划分的信息,在将来的研究中,希望可以将搜索方向信息加入到矩阵中,以便加速算法,提高效率,应用于大规模复杂网络的社团划分。