一种在复杂网络中发现社区的多目标遗传算法Clara Pizzuti摘要——本文提出了一种揭示复杂网络社区结构的多目标遗传算法。
该算法优化了两个目标函数，这些函数能够识别出组内节点密集连接，而组间连接稀疏。
该方法能产生一系列不同等级的网络社区，其中解的等级越高，由更多的社区组成，被包含在社区较少的解中。
社区的数量是通过目标函数更佳的折衷值自动确定的。
对合成和真实网络的实验，结果表明算法成功地检测到了网络结构，并且能与最先进的方法相比较。
关键词：复杂网络，多目标聚类，多目标进化算法1、简介复杂网络构成了表示组成许多真实世界系统的对象之间关系的有效形式。
协作网络、因特网、万维网、生物网络、通信传输网络，社交网络只是一些例子。
将网络建模为图，节点代表个体，边代表这些个体之间的联系。
复杂网络研究中的一个重要问题是社区结构[25]的检测，也被称作为聚类[21]，即将一个网络划分为节点组，称作社区或簇或模块，组内连接紧密，组间连接稀疏。
这个问题，如[21]指出，只有在建模网络的图是稀疏的时候才有意义，即边的数量远低于可能的边数，否则就类似于数据簇[31]。
图的聚类不同于数据聚类，因为图中的簇是基于边的密度，而在数据聚类中，它们是与距离或相似度量紧密相关的组点。
然而，网络中社区的概念并未严格定义，因为它的定义受应用领域的影响。
因此，直观的理解是同一社区内部边的数量应该远多于连接图中剩余节点的边的数量，这构成了社区定义的一般建议。
这个直观定义追求两个不同的目标：最大化内部连接和最小化外部连接。
多目标优化是一种解决问题的技术，当多个相互冲突的目标被优化时，成功地找到一组解。
通过利用帕累托最优理论[15]获得这些解，构成了尽可能满足所有目标的全局最优解。
解决多目标优化问题的进化算法取得成功，是因为它们基于种群的特性，同时产生多个最优解和一个帕累托前沿[5]的优良近似。
因此，社区检测能够被表述为多目标优化问题，并且帕累托最优性的框架可以提供一组解对应于目标之间的最佳妥协以达到最优化。
事实上，在上述两个目标之间有一个折衷，因为当整个网络社区结构的外部连接数量为空时，那它就是最小的，然而簇密度不够高。
在过去的几年里，已经提出了许多方法采用多目标技术进行数据聚类。
这些方法大部分在度量空间[14], [17],[18], [28], [38], [39], [49], [51]聚集目标，虽然[8]中给出了分割图的一个方法，并且在[12]中描述了网络用户会议的一个图聚类算法。
本文中，一个多目标方法，名为用于网络的多目标遗传算法(MOGA-Net)，通过利用提出的遗传算法发现网络中的社区。
该方法优化了[32]和[44]中介绍的两个目标函数，它们已被证实在检测复杂网络中模块的有效性。
第一个目标函数利用了community score的概念来衡量对一个网络进行社区划分的质量。
community score值越高，聚类密度越高。
第二个目标函数定义了模块中节点fitness的概念，并且反复迭代找到节点fitness总和最大的模块，以下将这个目标函数称为community fitness。
当总和达到最大时，外部连接是最小。
两个目标函数都有一个正实数参数控制社区的规模。
参数值越大，找到的社区规模越小。
MOGA-Net利用这两个函数的优点，通过有选择地探索搜寻空间获得网络中存在的社区，而不需要提前知道确切的社区数目。
这个数目是通过两个目标之间的最佳折衷自动确定的。
多目标方法的一个有趣结果是它提供的不是一个单独的网络划分，而是一组解。
这些解中的每一个都对应两个目标之间不同的折衷，并对应多种网络划分方式，即由许多不同簇组成。
对合成网络和真实网络的实验表明，这一系列帕累托最优解揭示了网络的分层结构，其中簇的数目较多的解包含在社区数目较少的解中。
多目标方法的这个特性提供了一个很好的机会分析不同层级的网络和研究不同模块化水平的社区。
本文组织如下，在下一节定义社区的概念，规范化社区检测问题。
第三节描述社区检测的主要方法。
第四节将社区检测问题公式化为一个多目标优化问题。
第五节描述了该方法，采用基因表示，变异操作的使用。
第六节给出该方法用于合成网络和真实网络的结果，以及与一些最先进方法的对比。
最后，在第七节讨论多目标方法的优点，得出结论。
2、社区定义一个网络N 能被模型化为一个图G=(V,E)，其中V 是一系列客体，被称作节点或顶点，E 是一系列连接，被称作边，这是连接了V 中的两个元素。
网络中的一个社区（也被称作簇或模块）是一组相互连接密度较高的顶点（即一个子图），并且组与组之间连接密度较低。
社区的这个定义相当模糊，并且在密度这个概念上没有达成一致。
[48]中介绍了一个更为正式的定义，通过考量一个一般的节点i 的度k i ，定义ijj i A k ∑=，这里A 是G 的邻接矩阵。
如果节点i 到节点j 之间有一条边，那么矩阵A 的（i ，j ）位置上为1，否则为0。
假设G S ⊂，节点i 属于G 的子图S ，i 的度分成两部分，)()()(S k S k S k out i in i i +=这里，∑∈=S j ij in i A S k )(，是i 与S 中其他节点相连的边的数量。
∑∉=Sj ij out i A k ，是i 与网络其余部分节点相连的边的数量。
如果S i S k S k out i in i ∈∀>),()(，则子图S 称为强社团。
如果∑∑∈∈>S i Si out i in i S k S k)()(，则子图S 称为弱社团。
因此，在一个强社区中，每个节点在社区内与图中剩余部分相比，连接更多。
在一个弱社区中，子图内节点内度的总和大于节点外度的总和。
接下来，我们采用弱社区的概念，因此一个社区被看作一系列节点，它们的内部连接的数量高于不同簇之间外部连接的数量。
3、相关工作来自不同领域例如物理学，统计学，数据挖掘，进化计算的许多不同算法已经被提出用来检测复杂网络中社区。
被采用的这些方法可以被概括地归为三类：分层分裂方法，分层凝聚方法[31]，以及优化方法。
分层分裂方法从完整的网络开始，检测连接不同社区的边，并移除它们。
这些方法的例子可以在[3],[25],[35],[41],[42]和[48]。
分层凝聚方法将每个节点看成一个社区，然后递归地合并相同的社区，直到得到整个图[4],[34],[40],[45],[47],[58]。
优化方法定义了一个目标函数将图划分为子图，并且尝试将这个目标最大化从而获得网络的最佳分割[1],[32],[53]。
在这些优化方法中，有几种方法通过利用进化技术已经成熟。
尤其[18],[20],[26],[29],[34],[44],[55]运用了遗传算法。
许多其他的方法利用多目标进化算法在度量空间来分割图或者聚集对象[8], [12],[14], [17], [28], [38], [39], [49], [51]。
接下来，我们首先回顾一下来自物理和数据挖掘领域的主要建议，然后报告一个多目标进化聚类方法的描述。
A.复杂网络的社区检测一些研究人员研究了社区检测问题，最先进建议的完整描述已经超出了本文的范围。
复杂网络社区识别方法广泛而详细的概述可以在[6],[21],[23]中找到。
检测社区最著名的算法是由Newman 和Girvan[25]提出的。
该方法通过删除边来反复地分裂网络。
通过利用中间性的测量来选择被移除的边。
以边的中间性为基础的想法来源于观察到的：如果两个社区通过几条社区间的边连接，那么从一个社区的顶点到另一个社区的顶点的所有路径，必须要通过这些边。
路径决定了计算边所得的中间性分值，通过计算穿过每条边的所有路径，并且删除得分值最高的边，网络内部的连接被破坏。
重复这个过程，并且将网络划分为更小的部分，直到没有边剩余。
同一作者[42]提出了一个基于不同的中间性测量值的分层分裂方法。
在这篇文章中，Newman 和Girvan 指出需要通过一个算法得出网络划分质量的测量值。
出于这个目的，他们引入了模块度的概念。
通俗地讲，模块度就是如果不考虑社区结构而边随机，社区内边的比例与边比例的期望值之差（模块度的正式定义是在下一节中）。
数值接近1表明社区结构明显。
因此，该算法计算某网络的每个分立社区的模块度，并且作者表明，当社团结构先验已知，高数值的模块度密切对应预期的网络划分。
Newman[40]认为因为高数值的模块度对应好的网络划分，找到网络可能最佳划分的方法就是优化它。
因此，他提出一个分层凝聚方法用于搜寻模块度的最优值。
Newman 注意到，彻底搜寻所有可能的划分方式以获得模块度的最优值，对于由超过20个顶点构成的复杂网络来说是难以实现的，因此需要近似方法。
他提出一个贪婪方法，连接社区使得模块度值产生最大增值。
基于相同策略的一个更快的方法在[4]中由Clauset ，Newman 和Moore 描述。
Blondel et al .[3]提出了一个方法划分大型网络，也是基于模块度优化。
该算法由两个阶段组成，反复迭代，直到没有得到进一步改善。
起初，网络中的每个节点都认为是一个社区。
然后，对每个节点i ，考虑它所有相邻的节点j ，并且计算将i 从它所在的社区移除以及将它增加到j 所在的社区后的模块度增益。
将节点放置在增益为正且最大时的社区中。
如果没有社区有正的增益，i 保留在它原来的分组中。
重复第一阶段直到没有节点可以移动来改善模块度。
第二阶段建立一个网络，其中已有的社区当作一个新的节点，如果有一条边在属于a 社区的节点和属于b 社区的节点之间，那么在ab 两个社区之间有连接。
新的社区能够被加权，在这种情况下，ab 之间边的重量就是相应社区节点之间的连接的权重之和。
在这一点上，可以重复该方法，直到无法做更多的改变以提高模块度。
算法返回所有发现的不同等级的聚类。
Pons 和Latapy [45]介绍了一个名为Walktrap 的分层凝聚算法，用于计算网络的社区结构。
该方法是基于图的随机游动，并且认为随机游动倾向于困在图中密集连接的部分。
两个节点之间距离的新定义是利用随机游动的性能引入的，并且这个定义可以推广到计算两个社区之间的距离。
算法从图的划分开始，其中每个节点是一个社区，然后合并两个相邻的社区（即至少有一个公共边），将两个顶点之间距离的平方值的均值以及它的社区最小化。
重新计算社区之间的距离，重复先前的步骤，直到所有的节点属于同一社区。
为了选出最佳划分，采用Newman 和Girvan 的模块度标准。
Pujol et al .[47]提出一个分层凝聚算法，将光谱分析和模块度优化结合获得网络社区识别的效率和准确度。
他们利用Pons 和Latapy [45]所采用的随机游动的相同概念产生网络的初始分区，然后运用分层凝聚方法反复连接两个社区。