多目标遗传算法中文

一种在复杂网络中发现社区的多目标遗传算法

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的度ki，定义kijA，这里A是G的邻接矩阵。如果节点i到节点jij

之间有一条边，那么矩阵A的（i，j）位置上为1，否则为0。假设SG，节点i属于G的子图S，i的度分成两部分，

ki(S)kiin(S)kiout(S)

这里，kiin(S)Aij，是i与S中其他节点相连的边的数量。kioutAij，是i与网络其余

jSjS

部分节点相连的边的数量。如果kiin(S)kiout(S),iS，则子图S称为强社团。如果k

iSini(S)kiout(S)，则子图S称为弱社团。 i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]所采用的随机游动的相同概念产生网络的初始分区，然后运用分层凝聚方法反复连接两个社区。为了合并两个簇，对总模块度贡献最少的节点群被选出，把它与能将模块度增值最大的节点群连接。

Lancichinetti et al.[32]基于社区S的community fitness概念，提出一个方法来检测重

inoutk(S)k(S)是社区S中节点的内度和外度。S的community ii叠和分层的社区结构。设和

fitness Ρ(S)定义如下：

kiin(S) (S)iniS(k(S)kout(S))

ii

outk(S)0,i时，对固i其中α是分辨率参数，是一个正实数参数，控制社区的规模。当

定的α，Ρ(S)达到它的最大值。[32]中使用community fitness以每次一个找出了所有社区。作者介绍了关于社区S的node fitness的概念，作为有和没有节点i，S的community fitness的变化，即

i(S)(S{i})(S{i})

该方法首先随机选择一个节点,并考虑它作为一个社区。然后遍历S的所有相邻节点但不包含在S中，选择相邻节点增加到S中。通过计算每个节点的node fitness做出选择，并且将fitness值最高的节点增加到S中。此时重新计算每个节点的fitness，并且将fitness为负值的节点从S中移除。当S中节点的所有不包含的相邻节点fitness值为负。一旦得到一个社区，选择一个新的节点，重新开始这个过程，直到所有的节点被指派给至少一组。作者发现得到的划分与分辨率参数α=1是相关的。然而，他们引入了一个基于稳定性概念的标准进行选择划分。如果对于一个取值范围内的α都能实现，则认为这种划分是稳定的。这个范围的长度决定了划分的更稳定，这就是最佳的结果。

B.多目标聚类方法

多目标优化聚类数据的应用程序近来引起人们的极大兴趣[14][17][28][38][39][49][51]尽管关于网络划分的建议很少[8][12]。

用于数值和分类数据的多目标聚类算法的参考方法是由Handl和Knowles [28]提出的，并且将之命名为multiobjective clustering with automatic K-determination (MOCK)。MOCK的第一目标是最小化一个划分的整体偏差，即数据项之间总的距离和已经被分配的簇的中心。第二个目标是最小化簇的连通性，计算每个簇数据点有多少个最近的邻点被放在相同的簇中。算法采用Park和Song [43]提出的基于轨迹的邻接，这在下一节中描述，并被MOGA-Net采用了，而且使用了基于最小生长树的特殊初始解，减少了执行时间。MOCK也包含了从帕累托前沿近似中选择最优解的最后一步，能够自动实现最优数量的簇。

MOCK不是专门用于网络划分的，尽管它被用于图的聚类，通过考虑网络的邻接矩阵作为（非）相似矩阵。

Datta et al. [8]提出了优化三个不同的目标用于划分图。目标将边缘值中的净亏损最小化，当两个连接的节点处于不同的社区时，社区在规模以及簇传播上有不同。作者强调了图中区域的概念，意为相邻节点的团体。因此，染色体是节点的集合，其中每个节点根据它在图中的位置是确定的。算法能将图划分为数量可变的区域，然而区域的范围和每个区域的节点数作为输入参数必须固定。

最近，一个专门用于分类网络用户会议的多目标进化算法由Nildem et al. [12]提出。获得的簇被用于网络推荐系统用于表示使用模式。用户访问的web页面序列被表示为一个加权无向图，其中每个序列都是一个节点，连接两个边的序列的权重是两个节点之间计算得到的相似性。他们的算法名为GraSC，使用和MOCK相同的表示法，但待优化的冲突目标是最小-最大削减[13]和轮廓指数[50]。前者试图优化社区内之间的相似性并减小子图之间的相似性，后者计算属于同一社区的顶点的平均轮廓指数。节点i的轮廓指数是两个平均非相似性之间的归一化值：节点i与其它社区的节点之间的最小平均非相似性，节点i和同一社区的其他顶点之间的平均非相似性。

在下一节，社区检测问题被形式化为一个多目标优化问题。

4、作为多目标优化问题的社区检测

不同领域的许多问题都自然地通过多个目标表述出来。特别地，将一个网络划分为组内连接紧密，组间连接稀疏的节点群有两个相互矛盾的目标。第一个目标是将属于同一个社区的节点间连接最大化，第二个目标是将社区之间的连接数量最小化。因此，社区检测问题不能够被充分地表示为一个单一目标，增加了暗中满足其他目标的限制。更合适的方法是将这个问题正式化为一个多目标聚类问题[19][28]。

一个多目标聚类问题（Ω,F1, F2, . . . , Ft）定义如下：

minFi(S),i1,...,t 服从S

其中Ω={S1,...,Sk}是网络的一系列可能社区。F = {F1, F2, . . . , Ft}是一组单标准函数。每一个Fi:Ω→R是不同的目标函数，这些函数决定了得到的社区的可行性。因为F是一个将这些相互矛盾的目标必须同时优化的向量，这个问题没有唯一解，但是通过利用帕累托最优理论[15]可以找到一系列解。考虑两个解S1和S2∈Ω，解S1支配解S2，记为S1 ≺S2，当且仅当

i : Fi(S1) ≤ Fi(S2) ∧  i :Fi(S1)

一个支配解并不会引人注意，因为对所有的目标都可以进一步改善。相反，一个非支配解想要在某一个目标上改善就要牺牲另一个目标。多目标优化的目的就是生成和选择非支配解，这些解被称为帕累托最优。因此目标是构建帕累托最佳状态。更正式地讲，一系列帕累托最优解Π被定义为

= {S ∈  :不存在S'且S’≺S}

向量F将解空间映射到目标函数空间。当非支配解标注在目标空间中，它们被称作帕累托前沿。因此帕累托前沿代表了更佳的折衷，尽可能满足所有目标的解。值得注意的是，正如[28]中所概述的，帕累托最优解总是包含优化单目标的聚类问题的最优解。

A.目标函数

我们的目标是将网络划分成一组组{S1,...,Sk}的顶点，在这些组里边的密度比组间边的密度高。为此，我们需要一个目标函数能够最大化每个社区内部连接的数量，以及另一个目标函数最小化社区之间连接的数量。

[44]中介绍了衡量一个社区S质量，最大化S中节点的入度。另一方面，[32]中定义了一个标准，最小化一个社区的出度。两种方法都采用了上述弱社区的定义。首先我们回忆一下这些措施的定义，然后展示它们如何利用多目标方法找到找到社区的。接下来，不失一般性，将网络假设为无向图进行建模。

假设μi表示连接节点i的边与社区S中其他节点的边的比值。更正式地为

1inki(S)|S| i

这里|S|是社区S的基数。

社区S的r阶幂平均值记作M(S)，定义为

M(S)iS(i)r

|S|

注意，M(S)的计算中，因为0≤μ≤1，指数r增加了与属于同一社区的其它节点连接很多的节点的权重，减小了在S中连接较少的那些点的权重。

社区S的体积νS定义为社区内部节点的边的总数，即与S相对应的邻接矩阵中1的数量

S

社区S的score定义为score(S)=M(S)×νS。因此，score将节点间连接比例（通过幂平均值）和社区S包含的内部连接的数量（通过体积）都考虑了。网络的一种社区划分{S1,...,Sk}的community score定义为

第一个目标是最大化社区得分（community score）CS。 i1ki,jSAijCSscore(Si)

正如第三节所述，Lancichinetti et al. [32]介绍了社区S的community fitness概念

kiin(S)(S)iniS(k(S)kout(S))

ii

第二个目标是通过community fitness实现的，通过总结所有Si社区的fitness。参数α调节社区的规模，已经被设置为1，因为正如作者所观察到的，大部分情况下发现的社区划分和这个值是有关的。第二个需要最小化的目标是

(S)i

i1k

在下一节，我们提出一个多目标社区检测方法，同时优化这两个目标。

5、算法描述

在这一节，我们描述了用来划分网络的多目标算法MOGA-Net，并使用了变异操作。在过去的几年里，一直致力于将进化计算用于多目标优化算法的发展。进化算法，实际上，被证明用来解决多目标优化问题是非常成功的，因为该方法以数量为基础的性质允许帕累托集的几个元素在单独的一次运行中存在[5][10]。

A.基因表示

我们的算法使用[43]中提出的基于轨迹的邻接表示，并在[28]和[38]中用于多目标聚类。在这个基于图的表示中，一个单独的个体由N个基因g1,...,gN组成，每个基因可以假设等位基因值j，取值范围是{1,...,N}。基因和等位基因表示网络N的建模——图G = (V, E)中的节点。j值分配给第i个基因被解读为V的节点i和j之间连接。这就意味着在社区解中会发现i和j在同一个社区。然而，解码步骤中关键是识别对应图中所有的单独部分。同一部分中的节点被分配到同一个社区。正如[28]中所观察到的，解码步骤可以在线性时间内完成。这种表示方法的主要优点是，社区的数量k由包含在一个个体中成分的数量和解码步骤自动确定。图1（a）展示了十个节点的网络划分为两个社区。两个社区中的节点分别用圆形和正方形表示。图1（b）中显示了可能的编码基因型解码到图1（c）中发两个连接的部分。这两个部分对应了图的划分。

B.初始化

初始化过程中考虑网络中节点的有效连接。产生随机的个体。然而，如果第i个位置的等位基因值是j，但边(i，j)不存在，个体j会被替代为与i相邻的个体之一。例如，在图2(a)在位置3和10分别对应等位基因值9和5。然而边(3,9)和(10,5)在图1(a)所示网络中不存在，因此9被4替代，5被7替代。

图1(a)10个节点的网络划分为两个社区{1,2,3,4,5,6}和{7,8,9,10} (b)一个基因型的基于路径的表示 (c)基因型基于图的结构

图2(a)基因型中(3,9)和(10,5)不是图1(a)中记录的图的边 (b)修正的基因型

C.均匀交叉

MOGA-Net使用了一个标准均匀的交叉算子。首先，随机产生一个交叉掩码，长度为N即节点的数量。通过从掩码为0对应的第一个父代的基因和掩码为1对应的第二个父代的基因产生一个子代。利用均匀交叉的主要动机是它能保证维持子代个体中网络节点的有效连接。事实上，因为有偏倚地初始化，对种群种每个个体，如果基因i包含值j，那么边(i，j)存在。因为每个i位置的子代包含的j值都是来自两个父代之一，那么边(i，j)存在。图3给出了均匀交叉的一个例子。

图3均匀交叉的例子

D.突变

突变操作是随机改变第i个基因的值j，引起搜索空间的一个无效探测，因为和节点连接的上述观察一样。因此，一个等为基因能够假设的可能值被严格限制在基因i的邻近基因中。例如，考虑图1(a)中的网络，第三个位置的基因所允许的等位基因值是2,4,5,6。这种突变操作保证了每个节点只和它的邻近之一相连的突变子代的后代。

E.选型

多目标聚类返回帕累托最优解集。这些每一个解都对应两个目标之间不同的折衷，因此不同的网络划分包含不同数量的社区。这提供了很好的机会分析几个不同等级的社区。然而，应该建立一个标准，自动选择一个解。出于这个目的，我们采取Newman和Girvan[42]介绍的模块度的概念。模块度是已知的，最常用的用于评估通过聚类方法获得的网络划分质量。设k是网络中社区的数量，模块度定义为

k

Q[

S1lsd(s)2] m2m

这里ls是连接社区s中顶点的边的总数，ds是社区s中节点的度之和。模块度Q的每一项被加数的第一项是社区内边的比例，第二项是在不考虑社区结构，边随机的网络中，边比例的期望值。值接近1表明强社区结构。因此，我们从帕累托前沿的解中选择模块度值最高的解。

图4显示了MOGA-Net算法的伪代码。考虑网络N和以此建模的图G，MOGA-Net从种群随机初始化开始。每个个体生成一个图结构，其中每个部分都是G的连通子图。对固定数量的子代，多目标遗传算法评估它们的客观价值，根据帕累托支配给每个个体分配一个等级，并且将它们排序。通过运用上述专门的变异操作产生一个新的种群。在程序的最后，在帕累托前沿所包含的一系列解中，MOGA-Net返回的是模块度值最高的解。在下一节，实验结果将会证明MOGA-Net算法划分网络的能力，我们显示了帕累托最优解的等级结构，其中社区数量更多的解包含在社区数量较少的解中。

6、实验结果

略

7、讨论与结论

本文将复杂网络社区检测的问题以多目标聚类问题的形式提出，并提出了一种进化多目标方法用于发现社区结构。该方法最大化每个社区内部的连接，最小化不同社区间的连接。该算法的一个主要特性是它能够自动提供一个网络划分，而不需要事先知道社区的精确数量。在社区划分的信息无法得知的情况下，该方法就相当有用。该方法已经在合成网络和现实生活的网络中测试过，显示了能够正确地检测到社区，并且能与最先进的方法相比较。相对单目标方法，多目标方法的优点是，同时优化多重准则，并不是提供单一的划分，而是一系列解，每一种都对应了不同数量的社区，组成了相互矛盾的目标之间的最佳折衷。实验表明，包含在帕累托前沿的非支配解是有意义的，并且支持了不同等级社区结构的分析。不同分辨率下网络特性的研究非常重要，因为往往以分层的形式安排组织，其中小的群体聚集形成更大的社区。可以通过采用划分质量的内部标准，选择一个模型而不是另一个，就像采用本文所描述的方法，即选择模块度值最高的划分，或者符合应用领域的专门标准。

众所周知，当个体数量众多时，遗传算法需要大量执行时间。虽然两个目标的适应度计算可以在网络节点数量的线性时间内完成，多目标方法的时间复杂度则是个体数量的二次方[11]。另一方面遗传算法更适合并行结构。为了处理更大的网络，并使得提出的方法比最先进的社区检测方法更有竞争力，我们计划在并行机器上实现MOGA-Net。