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

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

利用这两个函数的优点，通

过有选择地探索搜寻空间获得网络中存在的社区，

而不需要提前知道确切的社区数目。

这个数目

是通过两个目标之间的最佳折衷自动确定的。

多目标方法的一个有趣结果是它提供的不是一个单独的网络划分，

而是一组解。

这些解中的

每一个都对应两个目标之间不同的折衷，

并对应多种网络划分方式，

即由许多不同簇组成。

对合

成网络和真实网络的实验表明，

这一系列帕累托最优解揭示了网络的分层结构，

其中簇的数目较

多的解包含在社区数目较少的解中。

多目标方法的这个特性提供了一个很好的机会分析不同层级