多目标遗传算法中文

《多目标遗传算法中文》由会员分享，可在线阅读，更多相关《多目标遗传算法中文（8页珍藏版）》请在金锄头文库上搜索。

1、一种在复杂网络中发现社区的多目标遗传算法Clara Pizzuti摘要一一本文提出了一种揭示复杂网络社区结构的多目标遗传算法。该算法优化了两个目标 函数，这些函数能够识别出组内节点密集连接，而组间连接稀疏。该方法能产生一系列不同等级 的网络社区，其中解的等级越高，由更多的社区组成，被包含在社区较少的解中。社区的数量是 通过目标函数更佳的折衷值自动确定的。对合成和真实网络的实验，结果表明算法成功地检测到 了网络结构，并且能与最先进的方法相比较。关键词：复杂网络，多目标聚类，多目标进化算法1、简介复杂网络构成了表示组成许多真实世界系统的对象之间关系的有效形式。协作网络、因特网、 万维网、生物网络、

2、通信传输网络，社交网络只是一些例子。将网络建模为图，节点代表个体， 边代表这些个体之间的联系。复杂网络研究中的一个重要问题是社区结构25的检测，也被称作为聚类21,即将一个网 络划分为节点组，称作社区或簇或模块，组内连接紧密，组间连接稀疏。这个问题，如21指出， 只有在建模网络的图是稀疏的时候才有意义，即边的数量远低于可能的边数，否则就类似于数据 簇31。图的聚类不同于数据聚类，因为图中的簇是基于边的密度，而在数据聚类中，它们是与 距离或相似度量紧密相关的组点。然而，网络中社区的概念并未严格定义，因为它的定义受应用 领域的影响。因此，直观的理解是同一社区内部边的数量应该远多于连接图中剩余节点的

3、边的数 量，这构成了社区定义的一般建议。这个直观定义追求两个不同的目标：最大化内部连接和最小 化外部连接。多目标优化是一种解决问题的技术，当多个相互冲突的目标被优化时，成功地找到一组解。 通过利用帕累托最优理论15获得这些解，构成了尽可能满足所有目标的全局最优解。解决多目 标优化问题的进化算法取得成功，是因为它们基于种群的特性，同时产生多个最优解和一个帕累 托前沿5的优良近似。因此，社区检测能够被表述为多目标优化问题，并且帕累托最优性的框架可以提供一组解对 应于目标之间的最佳妥协以达到最优化。事实上，在上述两个目标之间有一个折衷，因为当整个 网络社区结构的外部连接数量为空时，那它就是最小的，然

4、而簇密度不够高。在过去的几年里，已经提出了许多方法采用多目标技术进行数据聚类。这些方法大部分在度 量空间14, 17,18, 28, 38, 39, 49, 51聚集目标，虽然8中给出了分割图的 一个方法，并且在12中描述了网络用户会议的一个图聚类算法。本文中，一个多目标方法，名为用于网络的多目标遗传算法(MOGA-Ne t)，通过利用提出的遗 传算法发现网络中的社区。该方法优化了 32和44 中介绍的两个目标函数，它们已被证实在检 测复杂网络中模块的有效性。第一个目标函数利用了 community score的概念来衡量对一个网络 进行社区划分的质量。community score值越高，聚

5、类密度越高。第二个目标函数定义了模块中 节点fitness的概念，并且反复迭代找到节点fitness总和最大的模块，以下将这个目标函数称 为communityfitness。当总和达到最大时，外部连接是最小。两个目标函数都有一个正实数参 数控制社区的规模。参数值越大，找到的社区规模越小。MOGA-Net利用这两个函数的优点，通 过有选择地探索搜寻空间获得网络中存在的社区，而不需要提前知道确切的社区数目。这个数目 是通过两个目标之间的最佳折衷自动确定的。多目标方法的一个有趣结果是它提供的不是一个单独的网络划分，而是一组解。这些解中的 每一个都对应两个目标之间不同的折衷，并对应多种网络划分方式，即

6、由许多不同簇组成。对合 成网络和真实网络的实验表明，这一系列帕累托最优解揭示了网络的分层结构，其中簇的数目较 多的解包含在社区数目较少的解中。多目标方法的这个特性提供了一个很好的机会分析不同层级的网络和研究不同模块化水平的社区。本文组织如下，在下一节定义社区的概念，规范化社区检测问题。第三节描述社区检测的主 要方法。第四节将社区检测问题公式化为一个多目标优化问题。第五节描述了该方法，采用基因 表示，变异操作的使用。第六节给出该方法用于合成网络和真实网络的结果，以及与一些最先进 方法的对比。最后，在第七节讨论多目标方法的优点，得出结论。2、社区定义一个网络N能被模型化为一个图G=(V,E)，其中

7、V是一系列客体，被称作节点或顶点，E是 一系列连接，被称作边，这是连接了 V中的两个元素。网络中的一个社区(也被称作簇或模块) 是一组相互连接密度较高的顶点(即一个子图)，并且组与组之间连接密度较低。社区的这个定 义相当模糊，并且在密度这个概念上没有达成一致。48中介绍了一个更为正式的定义，通过考 量一个一般的节点i的度k.，定义k =丫 A，这里A是G的邻接矩阵。如果节点i到节点j1 j ij之间有一条边，那么矩阵A的(i, j)位置上为1,否则为0。假设S u G，节点1属于G的子 图S， i的度分成两部分，k (S)二 kin (S) + kout (S)kout = A，是i与网络其余

8、 iijjSiii这里，k (S)A，是i与S中其他节点相连的边的数量。 iijjwS则子图S称为强社团。如果部分节点相连的边的数量。如果kin (S) koUt (S)，S G S,II工kin(S) 工kout(S)，则子图S称为弱社团。iiieSieS因此，在一个强社区中，每个节点在社区内与图中剩余部分相比，连接更多。在一个弱社区 中，子图内节点内度的总和大于节点外度的总和。接下来，我们采用弱社区的概念，因此一个社 区被看作一系列节点，它们的内部连接的数量高于不同簇之间外部连接的数量。3、相关工作来自不同领域例如物理学，统计学，数据挖掘，进化计算的许多不同算法已经被提出用来检 测复杂网络

9、中社区。被采用的这些方法可以被概括地归为三类：分层分裂方法，分层凝聚方法 31，以及优化方法。分层分裂方法从完整的网络开始，检测连接不同社区的边，并移除它们。这些方法的例子可以在3,25,35,41,42和48。分层凝聚方法将每个节点看成一个社 区，然后递归地合并相同的社区，直到得到整个图4,34,40,45,47,58。优化方法定 义了一个目标函数将图划分为子图，并且尝试将这个目标最大化从而获得网络的最佳分割 1,32,53。在这些优化方法中，有几种方法通过利用进化技术已经成熟。尤其 18,20,26,29,34,44,55运用了遗传算法。许多其他的方法利用多目标进化算法在 度量空间来分割图

10、或者聚集对象8, 12,14, 17, 28, 38, 39, 49, 51。接下来，我们首先回顾一下来自物理和数据挖掘领域的主要建议，然后报告一个多目标进化 聚类方法的描述。A复杂网络的社区检测一些研究人员研究了社区检测问题，最先进建议的完整描述已经超出了本文的范围。复杂网 络社区识别方法广泛而详细的概述可以在6,21,23中找到。检测社区最著名的算法是由 Newman和Girvan25提出的。该方法通过删除边来反复地分裂网络。通过利用中间性的测量来 选择被移除的边。以边的中间性为基础的想法来源于观察到的：如果两个社区通过几条社区间的 边连接，那么从一个社区的顶点到另一个社区的顶点的所有路径

11、，必须要通过这些边。路径决定 了计算边所得的中间性分值，通过计算穿过每条边的所有路径，并且删除得分值最高的边，网络 内部的连接被破坏。重复这个过程，并且将网络划分为更小的部分，直到没有边剩余。同一作者42提出了一个基于不同的中间性测量值的分层分裂方法。在这篇文章中，Newman 和Girvan指出需要通过一个算法得出网络划分质量的测量值。出于这个目的，他们引入了模块 度的概念。通俗地讲，模块度就是如果不考虑社区结构而边随机，社区内边的比例与边比例的期 望值之差(模块度的正式定义是在下一节中)。数值接近1表明社区结构明显。因此，该算法计 算某网络的每个分立社区的模块度，并且作者表明，当社团结构先

12、验已知，高数值的模块度密切 对应预期的网络划分。Newman40认为因为高数值的模块度对应好的网络划分，找到网络可能最佳划分的方法就是 优化它。因此，他提出一个分层凝聚方法用于搜寻模块度的最优值。Newman注意到，彻底搜寻 所有可能的划分方式以获得模块度的最优值，对于由超过20个顶点构成的复杂网络来说是难以 实现的，因此需要近似方法。他提出一个贪婪方法，连接社区使得模块度值产生最大增值。基于 相同策略的一个更快的方法在4中由Clauset, Newman和Moore描述。Blondel et al. 3提出了一个方法划分大型网络，也是基于模块度优化。该算法由两个阶 段组成，反复迭代，直到没有

13、得到进一步改善。起初，网络中的每个节点都认为是一个社区。然 后，对每个节点i,考虑它所有相邻的节点j,并且计算将i从它所在的社区移除以及将它增加 到j所在的社区后的模块度增益。将节点放置在增益为正且最大时的社区中。如果没有社区有正 的增益，i保留在它原来的分组中。重复第一阶段直到没有节点可以移动来改善模块度。第二阶 段建立一个网络，其中已有的社区当作一个新的节点，如果有一条边在属于a社区的节点和属于 b社区的节点之间，那么在ab两个社区之间有连接。新的社区能够被加权，在这种情况下，ab 之间边的重量就是相应社区节点之间的连接的权重之和。在这一点上，可以重复该方法，直到无 法做更多的改变以提高模

14、块度。算法返回所有发现的不同等级的聚类。Pons和Lat apy 45介绍了一个名为Walk trap的分层凝聚算法，用于计算网络的社区结构。 该方法是基于图的随机游动，并且认为随机游动倾向于困在图中密集连接的部分。两个节点之间 距离的新定义是利用随机游动的性能引入的，并且这个定义可以推广到计算两个社区之间的距 离。算法从图的划分开始，其中每个节点是一个社区，然后合并两个相邻的社区(即至少有一个 公共边)，将两个顶点之间距离的平方值的均值以及它的社区最小化。重新计算社区之间的距离， 重复先前的步骤，直到所有的节点属于同一社区。为了选出最佳划分，采用Newman和Girvan 的模块度标准。Pu

15、jol etal.47提出一个分层凝聚算法，将光谱分析和模块度优化结合获得网络社区识别 的效率和准确度。他们利用Pons和Latapy 45所采用的随机游动的相同概念产生网络的初始 分区，然后运用分层凝聚方法反复连接两个社区。为了合并两个簇，对总模块度贡献最少的节点 群被选出，把它与能将模块度增值最大的节点群连接。Lancichinetti et al.32基于社区S的community fitness概念，提出一个方法来检测重kin (S) kout (S)叠和分层的社区结构。设i 和i 是社区S中节点的内度和外度。S的communityfitness P (S)定义如下：kin (S)P(S) = E亠述(kin (S) + kout (S)a ii其中a是分辨率参数，kout (S)二 0, Vi是一个正实数参数，控制社区的规模。当i时，对固定的a， P (S)达到它的最大值。32中使用community fitness以每次一个找出了所有社区。 作者介绍了关于社区S的node fitness的概念，作为有和没有节点i， S的community fitness 的变化，即P. (S) = P(S u i) P(S i)i该方法首先随机选择一个