英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料

复杂网络中寻找社区的多目标遗传算法

摘要中主要讲述了一种揭示复杂网络社区结构的多目标遗传算法。 算法主要优化了两个目标函数，这两个目标函数能够识别具有稀疏内部连接的密集连接的节点组。 该方法在生成一组具有不同层次网络划分，其中具有的更深层次的社团划分解决方案包含在具有较少社区数量的解决方案中。 社团划分的数量由目标函数的更好的折中而自动确定。在合成和现实生活网络上的实验表明，该算法成功地检测了网络结构，并且与最先进的方法相比仍具有竞争力。

索引--复杂网络，多目标聚类，多目标进化算法。

1、导言

复杂网络中形成了一种有效的形式主义，用来表示构成许多现实世界系统的对象之间的关系。 协作网络，互联网，万维网，生物网络，通信以及传输网络，社交网络就是一些例子。 网络被建模为图形，其中的节点就表示对象，而边就表示这些对象之间的相互作用。

复杂网络研究中的一个重要问题就是社区结构的检测[25]，也可称为聚类[21]，即将网络划分为节点组，称为社区或集群或模块，具有密集内部 - 连接之间稀疏的相互联系。 如[21]中所指出的，这个问题只有在网络建模图形稀疏时才有意义，即边的数量远小于可能的边数，否则它变得类似于数据聚类[31]。 图上的聚类又与数据聚类不同，因为图中的聚类基于边密度，而在数据聚类中，它们是相对于距离或相似性度量接近的点组。 然而，网络中的社区概念并未严格定义，因为它的定义同样受到感兴趣的应用领域的影响。 因此，直观的概念是同一社区内的边的数量应该远高于连接到图的其余节点的边数，就构成了社区定义的一般建议。 这种直观的定义追求两个不同的目标：最大化内部链接和最小化外部链接。

多目标优化是一种解决问题的技术，当需要我们优化多个和冲突目标时，该技术成功地找到一组解决方案。 这些解决方案是通过使用帕累托最优理论[15]获得的，并构成了尽可能满足所有目标的全局最优解。 解决多目标优化问题的进化算法成功之处，是因为它们基于种群的性质同时产生多个最优解和Pareto前沿的良好近似[5]。

因此，社区检测可以转化为为多目标优化问题，并且帕累托最优的框架可以提供与优化目标之间的最佳折中相对应的一组解决方案。 实际上，在上述两个目标之间存在折衷，因为当社区结构由整个网络构成时其外部链接的数量零，因此它被最小化，但是群集密度不高。

在过去几年中，已经提出了许多方法来采用多目标技术进行数据聚类。 大多数这些提议在度量空间[14]，[17]，[18]，[28]，[38]，[39]，[49]，[51]中聚集对象，尽管在[8]中已经提出了一种分区图的方法，[12]中描述了网络用户会话的图聚类算法。

本文提出了一种多目标方法 - 网络多目标遗传算法（MOGA-Net），利用遗传算法发现网络中的社区。该方法优化了[32]和[44]中介绍的两个目标函数，这两个目标函数揭示了在复杂网络中检测社团的有效性。第一个目标函数采用社区评分的概念来衡量网络社区中的划分质量。社区评分越高，聚类越密集。第二个定义属于社团的节点的完整性概念，并迭代地找到具有最高节点稳定性的社团，在下文中称为社区适应性。当此总和达到其最大值时，外部链接的数量将最小化。两个目标函数都具有控制社区规模的正实值参数。参数的值越高，找到的社区的大小越小。

MOGA-Net利用的这两个功能的好处，通过选择性地探索搜索空间来获得网络中存在的社区，而无需事先知道社区的确切数量。 该数字是由两个目标的最佳折中值而自动确定。

多目标方法的一个有趣结果是它不返回网络的单个划分情况，而是返回一组解决方案。 这些解决方案中的每一个对应于两个目标之间的不同折衷，并因此对应于由不同数量的社区的网络的不同划分。 在合成和现实生活网络上的实验表明，该组Pareto最优解决方案揭示了网络的层次结构，其中具有较多数量的社团的解决方案包括在具有较少社团数量的解决方案中。 多目标方法的这种特性为分析不同层次的网络和研究具有不同级别的社团提供了很好的机会。

本文的结构如下。 在下一节中，定义了社区的概念，并将社区检测问题正式化。 第三节描述了社区检测的主要方法。 第四节将社区检测问题表述为多目标优化问题。 第五节描述了方法，所采用的遗传表示以及所使用的变异算子。 在第六节中，讲述了合成和现实生活网络方法的结果以及与一些最先进方法的比较。 最后，第七节讨论了多目标方法的优点，并总结了本文。

2、社区的定义

网络N可以被建模为二维平面图G =（V，E），其中V是一组对象，称为节点或顶点，E是一组链接，称为边，连接V的两个元素。社区（ 在网络中也称为群集或）是一组顶点（即子图），其中具有高密度的边缘，并且社团之间的边密度较低。 社区的这种说法相当模糊，对密度的概念没有普遍的一致意见。 在[48]中通过考虑通过一个通用节点i的度k_i引入了更正式的解释，其中A是，其中A是G的邻接矩阵.A是这样的一个如果从节点i到节点j存在边缘，则位置（i，j）为1，否则为0。 设S是图G中节点i所属的子图，相对于S的i的度可以分割为

是连接i到S中其他节点的边数，是将i连接到网络其余部分的边数。

子图S是强势社团，则有

,

子图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等人在 [3]提出了一种基于模块度优化来划分大型网络的方法。该算法由两个阶段组成，这两个阶段迭代重复，直到无法获得进一步的改进。最初，网络的每个节点都被视为一个社团。然后，对于每个节点i，考虑其所有邻居j，并且计算用于从其社团中移除i并将其添加到j社团的模块度增益数值。该节点位于社团中，其增益为正和最大。如果没有社区有正面收益，我仍然在其原始群体中。重复该第一阶段直到没有节点移动可以改善模块性。第二阶段构建网络，其中所获得的社区被视为新节点，并且如果属于a的节点与属于b的节点之间存在边，则存在两个社区a，b之间的边路。可以对网络进行加权，在这种情况下，a和b之间的边的权重是对应社区的节点之间的边路的权重的总和。此时，可以重复该方法，直到不再进行任何改变来改进模块度。该算法返回在不同层次级别找到的所有聚类。

Pons和Latapy [45]引入了一种名为Walktrap的凝聚层次算法来计算网络的社区结构。该方法基于图上随机游走的概念以及随机游走往往会陷入图中密集连接部分的想法。 通过利用随机游走的特殊属性，引入了两个节点之间距离的新定义，并且这个定义被推广用于计算社区之间的距离。 因此，算法从图的分区开始，其中每个节点是社区，然后合并两个相邻的社区（即，具有至少一个共同边缘），计算其最小化每个顶点与其社区之间的距离的平均值。 重新计算社区之间的距离，并重复上一步骤，直到所有节点属于同一社区。 为了确定最佳划分社区选择，采用Newman和Girvan的模块度标准。

Pujol等。 在文献[47]提出了一种凝聚层次方法，它结合了光谱分析和模块度优化，以获得网络聚类的效率和准确性。 他们使用Pons和Latapy [45]采用的相同的随机游走的概念来产生网络的初始分区，然后应用迭代加入两个社区的凝聚分层方法。 为了合并两个集群，选择对总模块性贡献最小的节点组，并将其与最大化模块度增量的组连接。

Lancichinetti等。 文献[32]中提出了一种基于S的社区适应性概念来检测重叠和分层社区结构的方法。让 和 成为属于社区的节点的内部和外部度 S.然后定义S的社区效率P（S）如下：

其中alpha;，称为分辨率参数，是控制社区规模的正实值参数。 当 ，对于任意的i时，P（S）达到固定alpha;的最大值。 社区健全已被[32]用于一次发现一个社区。 作者介绍了关于社区S的节点适应度的概念，作为有和没有节点i的S的社区有效性的变化，即

该方法首先随机选择一个节点，并将其视为社区S.然后执行S中未包括的S的所有邻居节点的循环，以便选择要添加到S的邻居节点。通过计算每个节点的节点精度，并用具有最高值的节点来扩充S来完成。此时，重新计算每个节点的精度，如果一个节点的结果为负值，则将其从S中删除。当S中节点的所有尚未包含的相邻节点都为负时，则过程停止网络的适应度。获得社区后，将选择一个新节点并重新启动该流程，直到所有节点都分配给至少一个社团。作者发现，为分辨率参数alpha;= 1获得的分区是相关的。但是，他们引入了一个基于稳定性概念选择分区的标准。如果分区的值为alpha;，则分区被认为是稳定的。该范围的长度决定了更稳定的分区，这被认为是最好的结果。

B、多目标聚类方法

多目标优化在聚类数据中的应用最近获得了越来越多的关注[14],[17]，[28]，[38]，[39]，[49]，[51]，[8],[12]尽管很少有提案关注网络的划分。

用于数值和分类数据的多目标聚类算法的参考方法是由Handl和Knowles [28]提出的，并且命名为具有自动K-确定（MOCK）的多目标聚类。 MOCK的第一个目标是最小化划分社团的总体偏差，即数据项与它们已被分配的社团中心之间的总距离。第二个目标是最小化社团连通性，该社团连通性评估每个社团数据点有多少最近邻居已被放置在同一社团中。该算法采用Park和Song [43]提出的基于轨迹的邻接表示，在下一节中描述并由MOGA-Net使用，并使用基于最小生成树的解决方案的特殊初始化来减少执行时间。 MOCK还包含一个最终步骤，用于从Pareto前沿近似中选择最佳解决方案，自动提供最佳数量的群集。

MOCK不是专门用于划分网络，尽管它可以通过将网络的邻接矩阵视为（dis）相似性矩阵来应用于图上的聚类问题。

Datta等人提出了一种优化三种不同目标的图划分方案。[8]。 当两个连接的节点放置在不同的社团中时，目标最小化边值的净损失，社团的大小差异以及社团的扩展。 作者强调了图中社团的概念，旨在作为相邻节点的社团。 因此，染色体是节点的集合，其中每个节点由其在图中的位置指定。 该算法能够在可变数量的区域中划分图，但是区域的范围和每个区域的节点数量必须固定为输入参数。

最近，Nildem等人提出了一种专门用于聚类Web用户会话的多目标进化算法 [12]。然后，将获得的聚类用于Web推荐系统中以表示使用模式。用户访问的网页序列表示为加权无向图，其中每个序列是节点，并且连接两个序列的边的权重是两个节点之间计

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[20211]，资料为PDF文档或Word文档，PDF文档可免费转换为Word