会员服务 ·

演化算法（EA）在社区发现方面的进展

2018 年 3 月 27 日 PaperWeekly 张晋媛

本文经授权转载自微信公众号「ECOLE」。

社区（Community）结构在复杂网络中普遍存在，整个网络由许多个社区组成，同一社区内的节点与节点之间连接紧密，而社区与社区之间的连接比较稀疏。

为了发现及分析复杂网络中的社区结构，许多社区发现（Community Detection）算法被提出。

一般而言，复杂网络中的社区发现是一个 NP 难问题，而多数现有社区发现算法都是基于贪婪算法，因此，当面临大规模复杂网络时，这类算法的性能有时不能达到使用者的要求与期望。

与此同时，很多社区发现算法需要关于社区结构的先验信息，而在实际社会网络中，很难获得此类信息。为此，越来越多的研究者们开始关注基于演化算法的社区发现算法。

今天我们将与大家分享 5 篇基于演化算法的社区发现相关论文，由于笔者能力有限，因此，如果分享过程中疏漏了重要工作，还请大家不吝赐教与指正。

GECCO 2008

■ 论文 | Community Detection in Social Networks with Genetic Algorithms

■ 链接 | https://www.paperweekly.site/papers/1775

■ 作者 | Clara Pizzuti

本文发表在 GECCO 2008，作者提出了一种用以在社交网络中发现社区的遗传算法。算法基于构成社区的节点中存在的链路数量和拓扑来定义社区中网络划分的质量度量，并且通过运行遗传算法来优化这些社区。

在算法结束时，网络结构中的所有密集社区都是通过选择性地探索搜索空间获得的，而不需要事先知道社区数的确切数量。

算法在实际网络中进行实验，结果表明遗传算法能够正确的检测社区，并且结果与当时最好的社区发现算法相当。

LION 2012

■ 论文 | Community Detection in Social and Biological Networks using Differential Evolution

■ 链接 | https://www.paperweekly.site/papers/1776

■ 作者 | Guanbo Jia / Zixing Cai / Mirco Musolesi / Yong Wang / Dan A. Tennant / Ralf. J. M. Weber / John K. Heath / Shan He

本文提出了一种基于差分进化的社区发现算法 DECD。在 DECD 中，DE 将网络模块化作为适应值函数来搜索网络的最佳分区。

考虑到 DECD 中个体是以社区标识符为基础的，传统交叉算子无法很好使用，文章提出了一种在演化过程中能有效传输相关社区结构化重要信息的基于标准 DE 交叉算子的二项式交叉算子。

此外，DECD 采用了偏向初始化过程和清理过程，通过纠正进入错误社区的节点来提升种群中个体的质量。

不同于其它社区检测算法，DECD 不需要有关社区结构的任何先验知识，这使得 DECD 能够更好的应用于没有先验信息的实际问题中。算法在人工和两个实际社交网络中进行实验，结果表明 DECD 能够得到更好的结果。

Applied Soft Computing 2014

■ 论文 | Multi-level Learning Based Memetic Algorithm for Community Detection

■ 链接 | https://www.paperweekly.site/papers/1777

■ 作者 | Lijia Ma / Maoguo Gong / Jie Liu / Qing Cai / Licheng Jiao

本文提出了通过优化模型进行社区检测的基于多级学习策略的模因算法 MLCD。MLCD 采用遗传算法做全局搜索并提出了多层学习策略来加速收敛。

多层学习策略分别在网络的结点、聚类和网络分区层上工作。通过迭代执行遗传算法和多层学习策略，能够准确、稳定的获得具有高模块化的网络部分。

文章同时使用了模块化标签传播规则，在每次操作时更新每个节点的聚类标识符，简单的更新规则也保证了算法的运行速度。

MLCD 算法在 GN、LFR 和 12 个实际网络中进行了实验，并与其它算法进行比较，实验结果表明 MLCD 在寻找网络的适当社区结构时有优越的性能。

IEEE TEVC 2017

■ 论文 | A Maximal Clique Based Multiobjective Evolutionary Algorithm for Overlapping Community Detection

■ 链接 | https://www.paperweekly.site/papers/1778

■ 作者 | Xuyun Wen / Wei-Neng Chen / Ying Lin / Tianlong Gu / Huaxiang Zhang / Yun Li / Yilong Yin / Jun Zhang

针对重叠社区检测，本文提出了一种基于最大组合的多目标进化算法 MCMOEA。文章引入了基于最大组合图的新的表示方法，最大组合图定义为使用一组最大组合作为节点、最大组之间的连接作为边。

由于最大组合图是根据使用原始图的一组最大组合作为节点定义的，并且允许两个最大组合共享原始图的相同节点，因此重叠是最大组合图的固有属性，基于此，新的表示方法允许 MOEAs 以类似于分离社区检测的方法来处理重叠社区检测，从而简化优化问题。

MCMOEA 算法在人造网络和实际网络中进行实验，并与其它算法进行比较，结果表明 MCMOEA 更加高效。

IEEE TEVC 2017

■ 论文 | Evolutionary Computation for Community Detection in Networks: a Review

■ 链接 | https://www.paperweekly.site/papers/1780

■ 作者 | Clara Pizzuti

文章对基于演化算法提出的社区结构发现方法进行了总结，特别是归纳了基于遗传算子的策略，并讨论了最常使用的测试函数。文章涵盖了近期针对不同类型网络模型（动态、多维度）提出的单目标、多目标方法。

文章主要从问题定义、问题建模、编码方案、遗传算子、适应值函数及多目标优化等六个方面进行综述。

1. 问题定义

在该部分文章给出了社区网络结构的图表示方法，并对该图中的节点、边、权重等信息的意义进行了详细说明。

2. 问题建模

在该部分，文章将社区结构发现抽象成了优化问题，并根据问题的特性，将其抽象成单目标优化问题和多目标优化问题两种类型。并对问题的解空间、目标空间，给出了定义。

3. 编码方案

在一个算法中解的表示是重要部分，现有的方法对子图网络中的划分进行编码。这些方法通常从用于通过演化方法解决经典数据聚类问题的编码改编而来。文章将这些编码方法分为四类，并分别进行综述：

基于层的表示方法：在这类方法中基因型是一个长度为 n 的整数向量，其中 n 是节点数目。位置 1≤i≤n 对应于节点，因此，如果 k 是社区的数量，则每个基因可以在字母表 {1，…，k} 中给定一个值。该值是标识节点 i 所属的社区标签。这类方法广泛的应用于数据聚类，在引入到社区结构发现中后，成为了最常用的解决复杂网络的方法。

基于轨迹的表示方法：这类方法最早被提出用于数据聚类，并被开发为多目标聚类方法。在这类方法中，个体由 n 个基因组成，并且每个基因可以假定等位基因值在区间 {1，…，n} 中，分配给第 i 个基因的值 j 被解释为节点 i 和 j 之间的链接。这使得将网络划分为连接的组件，通过子图表示出来常常是树形。

基于中心的表示方法：这类方法使用维数 k 为的数组，其中社区数量 k 必须作为输入参数。数组的第 i 个元素包含组成社区的节点之一。

基于置换的表示方法：由于前述方法不允许节点参与多个社区。为此新的课产生重贴社区的方法被提出。这类方法中，同一节点可以提高不止一个社区的适应值，从而增加到许多社区，产生重叠社区。

此外，在这部分文章还分析了四种编码方法各自的优缺点。

4. 遗传算子

在这部分，文章对社区发现中常用的几种遗传算子进行了综述。

交叉算子：将传统的交叉算子应用于社区发现会出现诸多问题，并且这些问题与所用的表示方法有关。为此，诸多适用于社区发现不同编码类型的交叉算子被提出。

变异算子：变异的任务是修改基因值，以便能够在搜索空间中尚未检查的区域探索。然而，变异不能太具有破坏性使得无法找到最佳解决方案。为此，根据社区发现的自身性质，桌多变异算子被提出。

种群初始化：种群初始化通常通过为每个个体分配随机值来产生。然而，这样的策略会给出质量差的网络的初步划分，导致真正的社区高度混合。为此，诸多针对社区发现不同编码类型的不同初始化方法被提出。

局部搜索算子：遗传算子通常可以产生将节点分配到错误社区的解决方案。为了提高社区分工质量，一些启发式方法被提出。

5. 适应值函数

适应值函数是寻找优质解的重要部件，在社区检测中，最常用的函数是模块化的。为此在这部分，文章对常用的这些适应值函数进行了分析和综述。

6. 多目标优化