基于蚁群优化的多目标社区检测算法

杨楠吕红娟++陈婷

摘要：蚁群优化算法作为单目标优化问题，由于只有一个目标函数，通常会将解限制到特定的范围内。当优化的目标不恰当时，算法可能失效，比如分辨率限制问题。我们将多目标优化的思想与传统的用于社区检测的蚁群优化算法相结合，增加了目标函数个数，即增加了解的评价指标数目。该算法引入多目标策略，提出多目标ACO算法，该算法在一次运行过程中会产生一组Pareto最优解。并在三个真实世界网络证明该算法的有效性和准确性。

关键词：复杂网络；社区检测；蚁群优化算法；多目标优化

中图分类号：TP18文献标识码：A

1引言

1991年意大利学者Dorigo M等人首次提出了蚁群优化算法[1，2]引起了学者的广泛关注与研究。蚁群算法是一种基于种群的启发式仿生进化系统，该算法采用了正反馈分布式并行计算机制，易于与其它方法相结合并且具有较强的鲁棒性。

本文介绍了一种基于蚁群优化的多目标社区检测方法，将蚁群优化算法与多目标策略[3]相结合，是一种优化模块度的社区检测方法。对于多目标优化问题，通常无法得到最优解，若同时考虑多个目标函数则算法将会得到一组优于其它解的最优解集。该集合叫做帕雷托（Pareto）解集或者非支配解集。

2基于蚁群优化的多目标社区检测

蚁群优化算法（ACO），是一种基于蚂蚁觅食行为的启发式方法，用来解决困难的组合优化问题，并且已经成功的应用到了各种棘手的问题，像二次分配问题（QAP），车辆路径问题（VRP）等。在1996年，Gambardella等人提出了一种修正的蚁群优化算法——蚁群系统（Ant System，AS），已经成功地应用在旅行商问题上。在这之后，科学家们也发明了一些改进的算法，比如精英蚁群系统（Elitist Ant System，EAS），最大最小蚁群系统（MaxMin Ant System，MMAS）以及排序蚁群系统（RankBased Ant System，ASrank）。

运用蚁群优化来做社区检测，首先需要指出如何表达一个解，其次就是如何构建一个解，然后就是信息素的初始化以及更新。下面我们将详细描述该算法。

2.1编码方式

社区就是复杂网络的子图，因而检测社区结构就等价于找出能揭示网络最好分割的一组子图。因此，社区检测问题的解可以明确地表示为：一个n个元素的向量表示图，其连通分量相当于社区。向量的元素和索引对应于图G=（V，A）中的节点。例如，向量中第i个元素等于j，即节点Vi和Vj之间有边相连，也就是说这两个节点在同一个连通分量里面，即处于同一个社区。

该编码框架的优点有很多，最重要的是不需要预先知道复杂网络的社区划分数目。解码的过程需要找出所有的连通分量。所有属于同一个连通分量的节点被划分到一个社区，解码过程是有必要的且可以通过广度优先搜索（breadthfirst search，BFS）或者深度优先搜索（depthfirst search，DFS）在线性时间内完成。解码完成后，会得到一个表示每个节点归属的向量。这种基于基因近邻的编码框架已经应用到了多目标聚类领域。该框架在社区检测的应用中有几个主要的优点，最重要的是，不需要预先知道社区的真实划分数目K，因为在解码过程中能够自动地得到K的取值。

3.1真实世界网络

本节将MOACO算法应用在三个真实世界网络上，分别是Zacharys Karate Club、Bottlenose Dolphins、Books about US politics。以上复杂网络是社会网络分析领域中的经典数据集，将这些数据在并与没有加入多目标策略的ACO算法以及GA、GAloacal算法进行了对比。由表2可以看出，三十次独立运行后，在Zacharys Karate Club网络中，ACO和MOACO的平均模块度值均不如GA和GA-local算法的结果好，而MOACO和ACO的平均模块度相差不大；在Dolphin social network网络中，本文提出的MOACO算法的平均NMI值明显好于其它算法。在Dolphin social network网络中，MOACO算法的模块度Q平均值与ACO算法的结果相差不大，而NMI的平均值要好于ACO算法。

为了验证蚁群规模和迭代次数对算法的影响，以Zacharys Karate Club网络为例进行参数分析，参数α、β、T、ρ、ε的值不变化，算法独立运行三十次求平均模块度值Q和平均NMI值，讨论蚁群规模N对算法结果的影响。

由表3可以看出，随着蚁群规模的增加，平均模块度值呈增长趋势，在蚁群规模为80时，达到了最大值。而由于蚁群优化算法中蚂蚁个体选择路径是随机的，因而平均NMI值没有呈现一定的规律，而当蚁群规模为40时，平均NMI值取得最大值。

表4表示参数α、β、N、ρ、ε保持不变，讨论迭代次数T对算法结果的影响，算法独立运行三十次的算法结果如表4所示。

由表4可知，迭代次数对算法的平均模块度值影响不大，而当迭代次数为150次的时候，平均NMI值取得了最大值。

图2表示调节参数过程中，算法取得的最优结果，即每一次运行的模块度值和NMI值，data1表示平均模块度值，data2表示平均NMI值。最优参数为：迭代次数150次，种群规模40。可以看出模块度值非常稳定。

3.2计算机仿真网络

本节使用经典的GN benchmark复杂网络来检测算法的可行性和有效性。GN基准网络是由Newman等提出。对于该基准网络，每个图包含了128个节点，分为4个由32个节点构成的社区。每个节点平均有Zin条边与同社区内节点连接，Zout条边与社区外节点连接。其中Zin+Zout = 16，作为每个节点的期望的度。随着Zout的增大，所产生的随机网络给社区检测算法带来了更大的挑战。特别是当Zout大于8时，意味着每个节点在社区内的边都要小于社区外的边，这时网络的社区结构就会非常模糊。当Zout≤ 8时，节点外度所占的比例小于内度所占的比例，因此算法应该能检测出网络中存在的社区结构，当Zout = 0时，表明节点的外度为0，此时节点仅与自身社区内的节点相连接，社区结构非常明显。分别对Zout从0到2进行了测试，对每种类型的网络产生一个复杂网络，使用NMI来衡量算法检测的结果和真实网络划分之间的相似性。对于每个网络，计算三十次独立运行的平均值。

由表5可以看出，当GN网络的外度为0时，该算法可以准确地检测出网络划分情况；当GN网络的外度为1和2的时候，该算法得到的结果也还都是有效的。

但是，在蚁群优化方法中，其算法复杂度比较高，所需要的搜索时间很长，而且容易出现所有的蚂蚁所对应的解完全相同这种“停滞现象”。导致了当复杂网络的社区数目较大时，算法不能产生有效解。另外，该算法对计算机生成的仿真网络不能得到有效的结果，这是我们进一步研究的内容。

4小结

基于传统的蚁群优化算法（ACO）算法的缺陷，提出了一种用于复杂网络社区检测的多目标蚁群优化算法MOACO，该算法将继续沿用传统的基于模块度优化的策略，加入了多目标的思想，每次迭代过程中，根据两个目标函数的不同折中，最终得到Pareto解集，选取每一代中优先级最高的那一组解。在三个真实世界网络和GN网络中的外度较小的网络上证明了算法的有效性，并将提出算法与ACO算法进行了比较，NMI平均值要优于ACO算法，模块度Q的平均值与ACO算法相当。缺点是不能处理社区划分类别多的复杂网络，对于结构模糊的GN网络，算法的效果不明显。

参考文献

[1]HONGHAO C， ZUREN F， ZHIGANG R. Community detection using ant colony optimization [C] Evolutionary Computation （CEC）， 2013 IEEE Congress on. IEEE， 2013： 3072-3078.

[2]DORIGO M，BIRATTARI M，STUTZLE T. Ant colony optimization[J]. Computational Intelligence Magazine， IEEE， 2006， 1（4）： 28-39.

[3]SOLNON C， Ghédira K. Ant colony optimization for multi-objective optimization problems[J]. Internation Journal on computer science， 2010.

[4]GONG M， CAI Q，CHEN X， et al. Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition[J]. Evolutionary Computation， IEEE Transactions on， 2014， 18（1）： 82-97.

[5]SRINIVAS N，DEB K. Muiltiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary computation， 1994， 2（3）： 221-248.