求解多目标社区发现问题的离散化随机漂移粒子群优化算法

（1.人工智能与模式识别国际联合实验室（江南大学），江苏无锡 214122；2.无锡职业技术学院物联网技术学院，江苏无锡 214121）

0 引言

数据信息可以被抽象为复杂程度不同的网络，网络中的点代表信息实体，边代表实体间的相关性联系。社区结构是复杂网络中常见的拓扑特征，即同一社区内的节点与节点之间关系紧密，而社区与社区之间的关系稀疏。由此，社区发现得以出现，它作为从网络底层结构中提取有用信息的关键工具之一，对于理解网络的结构特征和组织功能具有十分重要的意义。目前，很多重要的研究任务基于社区发现，如网络病毒传播、链路预测、网络演化分析、图像挖掘等［1-5］。

根据不同的研究视角，社区发现的研究可分为聚类问题和优化问题。聚类算法中包括经典社区划分算法（Girvan-Newman，GN）［6］、Infomap［7］、标签传递算法（Label Propagation Algorithm，LPA）［8］等，Dong［9］提出改进的标签传递算法（Improved Label Propagation Algorithm，ILPA）在重叠社区发现中与其他现有方法相比，精度更高。从优化的角度来看，大多数算法都是基于启发式进化算法逐步优化预定义的目标函数以获得模块化程度最高的社区结构［10-13］。进化算法（Evolutionary Algorithm，EA）等具有较强的全局优化能力的智能优化技术也在社区发现中引起广泛关注，如遗传算法（Genetic Algorithm，GA）［14-15］、微分进化（Differntial Ecaluation，DE）［16］、针对社区发现的蜂群优化（Bee Swarm Optimization for Community Detection，BSOCD）［17］等仿生学算法等。基于进化算法的社区检测方法存在参数多、收敛慢等问题，同时交叉变异过程的复杂性导致了社区结构的不稳定性，考虑到智能粒子群优化（Particle Swarm Optimization，PSO）算法的参数较少，全局收敛能力较强，收敛较快，不少学者将其引入社区发现算法之中［18-20］。Cai 等［21］研究了离散粒子群优化的符号网络社区检测方法，该方法有效且有应用前景，但只是对网络整体结构进行考量，而忽略了局部结构信息。Cao 等［22］提出了压缩形式的粒子群优化社区算法（Improved Simple discrete Particle Swarm Optimization，ISPSO）和改进的离散形式的粒子群优化算法（Improved Discrete Particle Swarm Optimization with Redefined Operator，IDPSORO）的对比，提出了孤立节点的修正策略。Chaitanya 等［23］提出了一种基于动态邻域拓扑的粒子群优化算法的社区检测方法，该算法局部搜索能力较好，但全局搜索性能及鲁棒性较差。

基于优化算法框架的社区发现算法虽然取得了不同程度的成功，但仍存在算法不具备普适性、划分网络社区的难度大、算法预测准确率低等问题。随机漂移粒子群优化（Random Drift Particle Swarm Optimization，RDPSO）［24］算法框架是一种变种的PSO 算法，是对PSO 进行收敛性分析和对金属导体中自由电子进行运动轨迹分析的启发而提出的。RDPSO 算法在连续优化问题上具有良好的表现，但由于其粒子更新的随机性较强，因此在社区发现问题上表现较差。为了克服RDPSO 的不足使其能够更加适用于求解社区发现这类离散优化问题，本文首先通过随机编码方式对社区结构进行编码，然后针对社区发现问题，提出离散化的随机漂移粒子群优化（Discrete Random Drift Particle Swarm Optimization，DRDPSO）算法用于求解多目标社区划分问题，通过核K 均值（Kernel K-Means，KKM）和比例割（Ratio Cut，RC）两个目标函数来控制网络中的社区规模、缓解模块度分辨率。根据多目标求解策略逐步更新Pareto非劣解集，从Pareto非劣解集选取满足需求的目标社区结构。

1 相关工作

1.1 复杂网络的社区定义

复杂网络依据图论可以由二元组G={V，E}表示，其中：V={v1，v2，…，vn}为n维点集，E=｛（i，j）|vi∈V，vj∈V，andi≠j｝代表边集。

假设C={C1，C2，…，Ck}是图G中的k个子集，Ci需要满足下列条件：

1）Ci⊂V且Ci≠∅，其中i=1，2，…，k；

社区发现优化问题是将图G中的点集V分成若干个子集，每个子集代表一个社区。复杂网络的定义依据其内部的结构信息，有在对节点度的度量下将社区分为强社区和弱社区［25］，也有针对复杂网络中边概率的比例对其进行分类［26］。

1.2 RDPSO算法

RDPSO 算法可描述为一个由M个N维粒子在空间上的不断向最优方向聚集搜索的过程。粒子在下一时刻的位置可表示为其中i表示第i个粒子，t为当前迭代步，而其在下一时刻的速度定位为RDPSO 中粒子的速度和位置更新公式定义如下：

其中：α⋅|为随机速度；α为热敏系数，控制随机速度的大小，一般随时间线性下降；Mt j为当前时刻的个体平均最优位置。可由式（3）得出：

而式（1）中的β⋅则是定向速度，其中β被称为漂移系数，用于控制粒子向学习倾向点的速度，可定义为：

在搜索过程中，粒子始终朝着学习倾向点聚集，而随机速度又给予算法很强的逃离局部最优区域的能力。因此，算法不仅具有全局搜索能力且收敛性较强。

2 多目标社区发现问题

2.1 问题描述

多目标优化问题的目的是通过同时优化多个目标函数寻找满足约束条件的最优决策解集。一般来说多目标优化问题中的各个目标函数是相互冲突的，因此多目标优化问题的难点在于找到一组合理的解集。一个含有D个决策变量、N个目标函数以及m+k个约束条件的多目标约束优化问题可以描述为：

其中：y是由多个目标函数构成的目标函数向量；fn(x)为第n个目标函数；x为决策向量。另外，其可行解域通过hi(x) ≤0和gj(x)=0 约束函数确定，xd_min和xd_max是各个决策变量的上下限。

2.2 目标函数

文献［27］指出核K均值（KKM）是社区内部节与其内部紧密度的平均值；与此相反，比例割（RC）则为所有社区内部的节点与其他外部间连接的平均值。最小化RC 则会使社区节点数量增加，使得网络的社区数量减少，与其他社区间的连接稀疏，所以这两个函数能有效平衡社区规模，提高划分准确度。文献［28］指出模块度的分辨率限制是由于其不包含社区的节点数量信息，并且该方式下社区的划分对网络的连接关系是高度敏感的。而这两个函数与网络中的子图密度有关，但对网络中的连接总数的敏感性不强。因此，KKM 可以看作是群落内部联系密度的总和，RC 可视为群落间联系密度的总和。

由于复杂网络的社区发现的本质是社区间连接稀疏、社区内连接密切，因此可以采用社区间与社区内部的两个不同标准需求来对社区进行划分，即可以采用优化算法同时优化KKM和RC两个目标函数。

在无向图G中，其邻接矩阵为A，若将图G划分为m个社区，即C={C1，C2，…，Cm}，其目标函数KMM和RC可定义为：

其中：n是网络节点总数，m为社区个数。而是集合Ci的补集节点，|Ci|是其社区i的节点个数。

2.3 更新Pareto外部存档库

Pareto 外部存档库是用来保存算法在粒子更新过程中获取的非占优粒子群（非占优解），它也可以被认为是一个目标解的存储空间。在计算目标函数之后，当前粒子群需要和历史种群中的其他个体进行比较确定其是否为非占优粒子。而存档库的空间大小是具有一定数量限制，即种群中的非占优解的个数是有限的。

Pareto 外部存档的更新过程为：在每次更新中，将当前粒子群根据Pareto 支配原则，计算Archive 集并获取此时的非劣解集；再将此时的非劣解集与当前Pareto 外部存档进行第二轮支配关系比较，更新Pareto 外部存档；最后，判断其存档数是否超过阈值。需要指出的是，本文通过拥挤度的计算来删除超出阈值范围的非占优解，保持外部存档的数目。Pareto外部存档更新步骤如下：

步骤1 初始化外部存档P、网格等分数S；

步骤2 计算t时刻目标空间的边界和

步骤3 计算网格的模

步骤4 统计网格信息、粒子的拥挤度概率；

步骤5 保存高拥挤概率中粒子的索引值；

步骤6 输出外部存档P中的待删除检索值。

2.4 最佳社区的确定

在多目标社区发现优化问题中，最佳社区的确定并不是由种群的全局最优位置决定的，而是利用最终的Pareto 外部存档库P进行选择最优需求的解。因此，本文使用社区模块度Q与归一化互信息（Normalizaed Mutual Information，NMI）的最大值对算法获得的社区进行评价，这两个评价指标的定义如下：

3 DRDPSO算法

3.1 粒子的编码方式

为了更好地求解社区发现优化问题中，粒子的每一维即复杂网络中的点会被重新编码。

求解社区优化问题一定程度上依赖于粒子的初始值，常见的粒子的编码方式有两种：1）每个粒子的位置值为［1，n］内的随机整数，但该方式具有较强的随机性、易使划分的社区结构不稳定；2）使用LAR（Locus-based Adjacency Represent）方式，即粒子的编码值根据邻居节点的编号取值，粒子能获取较好的初始值，但该方式复杂度较高［29-30］。

为降低解码过程的复杂度，DRDPSO 算法采取随机编码的方式对社区网络的节点进行编码。但如果仅仅将对粒子值赋值为｛1，2，…，n｝，容易使算法划分网络得到的社区结构单一、缺乏多样性，并且社区质量较差。为此，首先对粒子初始位置值进行预处理操作。因此，在DRDPSO 算法中引入了粒子预处理操作［31］，算法复杂度相对较低且它可以发现网络中潜在的社区结构，这有助于提高算法的准确性。

3.2 粒子的预处理

粒子预处理是对粒子xi，t(t)作如下计算：

其中：函数f返回的是节点t的邻居节点所属社区的最多数的社区编号；k为节点t所拥有的邻居节点的数目。通过对粒子进行预处理操作，即基于邻居节点的成员关系决定粒子的位置，因此可以将那些具有更紧密连接的节点划分为相同的社区。

3.3 粒子的离散化定义

RDPSO 是针对连续性优化问题设计的，对于社区发现这种离散型的优化问题不适用，需将RDPSO 算法的粒子更新状态重新进行离散化定义。本文将“⊗”“⊖”“⊕”和“⊙”离散操作符取代RDPSO 算法中的连续计算符，其DRDPSO 算法中粒子的离散化定义如下：

其中，粒子的速度通过二进制化可重新定义如下：

其中fi为均匀分布产生的0-1的随机数。

而根据式（15）的离散计算方式和速度更新结果，粒子的位置做出相应的改变：

其中：lw，v表示社区w、社区v的连接情况；dw、dv分别为社区w、社区v的总度数；m为边数。

3.4 DRDPSO求解多目标社区优化问题

在搜索过程中，首先DRDPSO 算法通过预处理和离散化的编码方式将该网络的数据集转化为对应的种群各个粒子的初始值。紧接着，初始化算法的相关参数，构建初始的网络社区模型，并计算目标函数得到每一个可行解的适应值。进一步，依据Pareto 支配原则，获取具有一定数量的非占优解并保存在外部存档库中。最后，依据式（6）～（7）更新粒子种群。需要注意的是，在更新外部存储库中的非占优解时需要将其拥有高拥挤距离的个体删除以减少计算时间。当满足终止条件时，最优解将从非占优解集中选择出。

DRDPSO算法求解多目标社区优化问题的算法如下：

输入：n个节点的复杂网络G={V，E}、种群大小pop、最大迭代次数itermax、外部存档容量rp；

输出：满足需求的最优社区划分C={C1，C2，…，Cm}。

DRDPSO算法流程如图1所示。

图1 DRDPSO算法流程Fig.1 Flowchart of DRDPSO algorithm

4 实验与结果分析

实验采用的网络数据集分别为生成网络与真实网络。在生成网络中，利用3种类型的网络验证相关算法：GN、LFR1和LFR2。其中：GN 是Lancichinetti 等［33］在经典基准网络上提出的扩展网络；LFR1、LFR2分别是不同大小规模的LFR标准基网络类型。在表1中给出了生成这些网络的一些参数，其中：N是合成网络的节点数；Kavg为平均节点度数；Kmax为节点度数上限；Cmin和Cmax是社区规模的最小值和最大值；另外γ称为最小参数，它控制社区内外的连接部分。这里生成了10个网络，通过控制最小参数在0.0～0.5的区间内每隔0.05生成一个网络。

表1 生成网络参数值Tab.1 Parameter values of generated networks

在真实网络中，包含具有真实社区结构的空手道俱乐部Zachary’s Karate Club Network 数据集、海豚Dolphins Social Network 数据集、美国大学橄榄球联盟American College Football 数据集，分别用Karate、Dolphin、Football 表示。表2 中呈现了这3个真实数据集的相关信息。

从图5可以看出，随流速的增加，树脂对花色苷的解吸效果越来越差，可能是流速过快导致乙醇不能与被吸附的花色苷充分作用而将其从树脂上洗脱出来。但是流速太慢会导致解析的时间延长，故选择 1 mL/min作为洗脱流速。

表2 真实网络数据集特征描述Tab.2 Feature description of real network datasets

由于GN［6］、Louvain［13］、Infomap［7］、IDPSO-RO［22］、BSOCD［17］等算法效率比较高，可覆盖所有类型的网络，且发现的社区质量也比较好，因此将其与提出的DRDPSO 算法进行实验数据比较。实验中，针对生成网络，每种规模各生成10 个网络进行实验对比分析，同时针对三种真实网络进行实验分析，记录GN、Louvain、Infomap、IDPSO-RO、BSOCD、DRDPSO 算法取得的Q与NMI值。

实验参数设置为：种群大小pop为200；最大迭代次数itermax为100；外部存档容量rp为50；网格等分数S为10。

实验环境为：Intel Core i7 CPU 2.5 GHz，内存为8 GB，Python 3.6中，并使用networkx API。

4.1 生成网络的实验结果与分析

4.1.1 GN网络结果的分析

在GN 网络中分析这6 种算法获得的相应社区其Q与NMI值的情况，如表3、4所示。

表3 记录了各算法获得最大模块度Qmax值以及平均模块度Qavg值。除了A3（Infomap 算法），其他算法的最大模块度值处于整体下降趋势，如图2 所示。而在0.45 ≤γ≤0.5 对应的网络中，DRDPSO 的Qmax，Qavg相对较大，证明DRDPSO 算法是一种模块度优化较强的算法，其获得社区结构质量相较其他网络更好。

表3 不同算法在GN网络上的Q 值Tab.3 Q values of different algorithms on GN network

表4 各算法在GN网络上的NMI值Tab.4 NMI values of different algorithms on GN network

图2 不同算法最大模块度Q 值趋势Fig.2 Maximum modularity Q value trend of different algorithms

表4 中记录了各算法最大标准化互信息NMImax与平均标准化互信息NMIavg值。由于网络中最小参数越小，网络中相对存在的社区结构也越清晰，因此当0.05 ≤γ≤0.35，对应的网络中绝大数算法都能发现其正确的社区。在γ=0.45 的网络中，IDPSO-RO 其NMImax=0.469 4，但NMIavg=0.073 1。而在γ=0.5，对应的网络中几乎就侦测不出其社区结构。因此，整体上IDPSO-RO 在0.45 ≤γ≤0.5 对应的网络其划分的准确率并不高。另外，其他算法侦测其社区的结构相对之下都较为稳定。

通过上述分析，可以发现DRDPSO在GN这种网络规模中能获取更精确划分的社区，社区的划分质量也相对较好。当最小参数增大时，其他算法在GN 网络上划分得到的社区的结果劣于DRDPSO。

综上，DRDPSO 在LFR1上的各个网络中得到的划分社区的效果还是比较理想的，随着参数的增大，其正确划分的社区的精度高的且社区的质量较好。

4.1.2 LFR1网络结果的分析

在LFR1 网络中这里分析6 种算法获得的相应的社区模块度与NMI值的情况，如表5、6中。

在表5 中，可以看出γ=0.2 对应的网络中，其IDPSO-RO获得社区的质量均高于其他算法；在γ=0.35、γ=0.45 的网络中，DRDPSO 划分的社区质量最好；在γ=0.4 的网络中，Louvain算法划分的社区质量最好。

在表6 中，DRDPSO 算法在0.05 ≤γ≤0.35 对应的网络中的NMImax=1，并且在0.05 ≤γ≤0.45 对应的网络中NMImax、NMIavg的值也均高于其他算法，而γ=0.5 的网络中DRDPSO算法的NMImax、NMIavg的值略优于其他算法。

综上，DRDPSO 在LFR1上的各个网络中得到的划分社区的效果较为稳定，且随着参数的增大其正确划分社区的精度较为稳定，社区的质量也比较好，鲁棒性较高。

表6 各算法在LFR1网络上的NMI值Tab.6 NMI values of different algorithms on LFR1 network

4.1.3 LFR2网络结果的分析

表7 和表8 记录了6 种算法在LFR2 网络中获得的相应社区其模块度Q与NMI值的情况。在表7中，可以看出DRDPSO在LFR2 的10 个网络中，获得Qmax、Qavg值相对较高，在模块度上获取的社区结构质量稍高一些。

表8 记录了各算法在该网络中得到的指标的情况，可以清晰地发现DRDPSO 算法其划分的社区的精确率在LFR2 网络上比其他算法都高，尤其是在0.05 ≤γ≤0.45 的网络中其均有NMImax=1、NMIavg=1，在γ=0.5 的网络上其NMI指标值比其他算法都高。

综上所述，DRDPSO 相较于其他几种算法能更准确地划分LFR2网络。

表7 各算法在LFR2网络上的Q 值Tab.7 Q values of different algorithms on LFR2 network

表8 各算法在LFR2网络上的NMI值Tab.8 NMI values of different algorithms on LFR2 network

4.2 真实网络的实验结果与分析

4.2.1 真实网络中Pareto 前沿值

图3 给出了DRDPSO 算法在Karate、Dolphin 与Football 网络中获取的Pareto 前沿值。每幅图的横坐标为KKM函数值，纵坐标为RC函数值。另外，在每幅图中有两个箭头，分别对了Qmax与NMImax值时所对应的两目标函数。因此，可以看出Qmax与NMImax时，其KKM与RC值是不同的。

4.2.2Q与NMI的实验结果与分析

表9、10 分别给出了各个算法在Karate、Dolphin 上的各项评价指标数据。通过分析算法在Karate 网络上得到的实验结果，可以发现DRDPSO 算法获得的Qmax，NMImax均优于其他对比算法。

图3 DRDPSO在Karate、Dolphin、Football网络中获取Qmax与NMImax时的Pareto前沿值Fig.3 Pareto front values when DRDPSO obtaining Qmaxand NMImaxin Karate，Dolphin and Football networks

表11 中记录了6 种算法在Football 数据集上的各项评价指标的取值。DRDPSO 在社区划分的精确度为NMImax=0.962 9，因此可以同样得出DRDPSO 在Football 网络中划分的社区最好。

表9 各算法在Karate数据集上的评价值Tab.9 Evaluation values of different algorithms on Karate dataset

表10 各算法在Dolphin数据集上的评价值Tab.10 Evaluation values of different algorithms on Dolphin dataset

表11 各算法在Football数据集上的评价值Tab.11 Evaluation values of different algorithms on Football dataset

5 结语

本文提出了一种针对复杂网络多目标社区发现问题的离散化随机漂移粒子群（DRDPSO）算法，在多个生成网络数据集及真实网络数据集上进行了实验。实验结果表明，在两个最佳社区评价指标下，DRDPSO 算法表现均优于其他对比算法，能够更好更有效地挖掘网络社区结构，并能够在较大规模的网络中具有更强的社区划分性能。接下来，我们会对该算法在概率度量空间中进行收敛性及粒子轨迹分析，同时，将利用多目标框架优化拓扑与属性特征函数改进本文提出的算法，并应用到具有属性信息的复杂网络社区中。