基于多目标优化的符号网络社区检测算法

谭玉玲，肖媛娥

基于多目标优化的符号网络社区检测算法

*谭玉玲1，肖媛娥2

（1. 罗定职业技术学院信息工程系，广东，罗定 527200；2. 井冈山大学网络信息中心，江西，吉安 343009）

符号网络可以描述实体之间的多种关系，对符号网络中的社团检测可以挖掘出其中的有效信息。同时考虑连接密度和连接符号，将社团发现问题建模为一个多目标优化问题，基于MOEA/D框架，提出一种改进的符号网络社团发现算法，设计了基于字符串的编码方式、预分区策略、交叉合并策略、变异方式等。实验结果表明，本算法可以有效检测出社团结构。

复杂网络；符号网络；社团结构；多目标优化

0 引言

现实生活中存在很多的复杂网络，对复杂网络进行社团结构挖掘可以揭示复杂网络的特性，具有重要的研究价值。传统的社区检测算法大致可分为图划分方法、基于层次聚类的算法、基于进化的算法等，主要是针对无符号网络进行的[1]。在实际应用中，很多网络是具有正负关系的，即符号网络，如社交网、人际关系网等。有符号网络是由正关系和负关系构成的。因为人和组织之间的关系具有双面性，具有正值的有符号网络的连接可以被描述为“友好”、“喜欢”等，而具有负值的连接被描述为“敌对”、“不喜欢”等[2]。因此，要将无符号网络的社区的定义扩展到有符号网络中，必须同时考虑连接密度和连接符号这两个指标[3]。

在基于多目标的社区检测方面，文献[4]引入社区分数(CS)作为目标函数，采用进化算法进行优化；文献[5]引入了社区适应度(CF)，采用NSGA-II算法同时优化CS和CF两个目标函数；文献[6]提出了同时优化连接度和分隔度两个目标函数，采用MOEA/D多目标框架优进行优化，取得了良好的结果。在符号网络的多目标研究方面，文献[7]DWI-SN算法和文献[8]SNMOGA算法分别利用MOEA/D和NSGAII的框架来挖掘有符号网络中的社区; 文献[9]提出了可同时适合于无符号网络和符号网络的社区检测算法。然而该算法在相似性指标的选取的环节中考虑的条件因素不够完善，导致社区划分后拟合结果不够精确。

在本研究中，采用MOEA/D框架[10]，选择了新的相似性度量指标，设计出新的节点更新预分区策略，同时，在预分区后设计了交叉合并操作符合并社区，用特殊突变算子对边界节点进行重新划分，提高了社区划分的精准度。

1 复杂网络社区检测的多目标优化模型

对于有符号网络，要求社区内部的正边缘和社区内部的负边缘都是紧密相连的。一般采用社区内部的正边缘密度和负边缘密度来评价社区内部和社区之间的连通程度[7-9]。因此，采用一种边缘密度(Edge Density, ED)的函数，用于度量有符号网络的社区连通程度：

此外，要优化的第二个目标是有符号的模块度SQ。SQ可定义为：

因此，符号网络的多目标优化模型如下：

2 算法具体设计

2.1 编码方法

本算法选用基于字符串的编码模式[11]。该编码方式很容易获取相应的网络分区，然后为每个节点设置出不同的标签，通过其邻居的标签对其标签进行更新，最后使用相同的标签更新属于相同社区的节点。在本算法中，社区划分的过程即为标记进化的过程。假设我们有不同的8个节点，节点间的关系、更新进化的过程和解码的过程如图1所示。

图1 解的编码和更新过程

首先通过邻居标签自身标签进行更新，划分集群后进行解码，最终网络中产生了两个划分好的社区。

2.2 种群预划分

在种群初始化阶段之后，对网络进行预分区的处理。用节点相似性函数，对输入网络的邻矩阵进行处理，得到一个相似矩阵。为了获得节点的聚集，进一步在相似矩阵的基础上规划了New-k节点更新预分区策略[12]。

1）节点相似函数

对于有符号网络，可以计算其公共邻居数量，选用了Jaccard指数作为节点相似性的度量指标[12]，在上述计算的基础上添加一个惩罚项，构造出新的相似性度量方法：

选用Jaccard指数作为节点相似性的度量指标计算出任意两个节点的相似性，并得到相似性矩阵，然后根据提出的基于结构平衡理论的相似性函数设计变异算子。

2）New-k节点更新预分区策略

为了有效地管理预划分后的种群，本文采用了一种基于相似矩阵的交叉算子——交叉合并算子和变异算子。

2.3 基于本地节点集的交叉合并算子

2.4 基于相似矩阵的变异算子

该算子的设计中一方面消除了相似向量中的零元素，减少了噪点的干扰，避免了搜索空间中的无用搜索；另一方面，不仅简单地将相似性最高的邻居节点标签配给到待定节点，而且根据相似性值的比例来选择这种方法，使得相似性较小的节点有机会更新待定节点。该算法避免了过度收敛，提升了算法在搜索空间中的局部搜索能力。由于在内部节点上操作没有意义，变异算子只在边界节点上运行。

2.5 算法的总体框架

本文设计的基于多目标优化的符号网络社区检测算法如下：

算法输出：最佳网络社团分区；

步骤1初始化；

1.2）初始化随机生成的第一代种群pop，采用上述算法处理种群；

步骤2 更新：

2.1）迭代次数= 1；

2.2）当（迭代次数<= maxgen）；

2.3）for i = 1：popsize；

2.5）if rand_number

2.7）else if rand_number

2.9）end if；

2.12）for j= l：length(child)；

2.14）end for；

2.15）end for；

2.16）迭代次数 = 迭代次数 + 1；

2.17）end while；

3 实验结果与分析

3.1 评价指标

为了评估所提出的算法的优越性和劣势，选择了归一化互信息（NMI）[13-14]作为评估指标。假设A是真实网络分区，B是检测到的算法分区。混淆矩阵由分区A和B共同构成。NMI的表述为：

3.2 参数设置

为验证本文所提算法N-GMOEA-net的有效性，与MODPSO[7]，SNMOGA[8]和MEAs-SN[9]算法进行对比。MODPSO是一种用于网络社区发现的多目标离散粒子群优化算法，能处理小规模有符号网络。SNMOGA是一种基于NSGAII的多目标符号网络社区检测算法。MEAs-SN是一个基于MOEA / D框架的网络社区检测算法。为了验证算法的优越性，上述算法均采用相关文献中推荐的参数进行配置，见表1。

表1 算法的参数设置

Table 1 Parameter settings of the algorithm

算法PopmaxgenPcPmNT MOGA-net3001000.80.2× MODPSO100100×0.140 MEAs-SN1001000.71.020 SNMOGA1001000.80.2×

其中，算法中不需要的参数用“×”表示。其中Pop为随机生成的第一代种群，Maxgen为终止进化的迭代次数，Pc为交叉发生的概率，Pm为变异发生的概率，NT为每个权重向量邻居权重向量的数量。

3.3 人工网络和合成网络上的实验结果

为了验证本算法的性能，使用两个人工网络和两个真实网络进行测试。其中两个有符号网络分别使用IS1和IS2表示，另外两个有符号网络分别为Slovene Parliamentary Party Network (SPP)和Gahuku-Gama Subtribes network(GGS)[9,15]。这些网络的相关特征见表2。

表2 四个小规模符号网络的信息

Table 2 Information on four small-scale symbol networks

网络节点数边缘数正向边缘负向边缘真实社区数 IS1284230123 IS2284930193 SPP104518272 GGS164829293

在这之中，这四种算法的聚类结果见表3。

表3 小规模有符号网络的检测结果

Table 3 Test results of small-scale signed network

网络指标 MODPSOMEAs-SNSNMOGA本文算法 IS1NMI1.00000.48301.00001.0000 0.98770.48301.00001.0000 0.03880.00000.00000.0000 IS2NMI0.92230.42991.00001.0000 0.88110.42991.00001.0000 0.02410.00000.00000.0000 SPPNMI1.00001.00001.00001.0000 0.98471.00001.00001.0000 0.04830.00000.00000.0000 GGSNMI1.00000.68831.00001.0000 1.00000.52761.00001.0000 0.00000.18660.00000.0000

由于这四种网络的规模小、结构易于识别，除MEAs-SN算法外，其他算法在准确性方面表现良好。其中本算法和SNMOGA给出了完全正确的网络分区。而MODPSO的性能略低于SNMOGA和本文算法。

3.4 有符号现实网络生成的实验结果

图3 SLFR比较结果-

图4 SLFR比较结果-

根据以上SLFR网络的实验结果可知，本文提出的算法在精度和稳定性方面明显优于SNMOGA和MEAs-SN。

图6 SLFR比较结果-

4 结论

本文设计了一种用于符号网络社区检测的多目标优化算法，详细介绍了其关键实现技术。实验结果表明，本文算法具有较高的检测效率。下一步将探索一种混合算法，可以同时适用于非符号网络和符号网络的社区检测。

[1] Cai Q, Ma L J ,Gong M G .A survey on network community detection based onevolutionary computation[J]. Int. J. Bio-Inspired Computation, 2016,8(2):84-98.

[2] Shang R H, Zhang W T, Jiao L C. Circularly searching core nodes based label propagation algorithm for community detection[J] Int. J. Pattern Recognit. Artif. Intell. 2016,30 (8): 1659024.

[3] Gong M G, Ma L J, Zhang Q F, et al. Community detection in networks by using multi-objective evolutionary algorithm with decomposition[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(15): 4050-4060.

[4] Pizzuti C. A multi-objective genetic algorithm to find communities in complex networks[J]. IEEE Transactions on Evolutionary Computation, 2012, 16(3): 418-430.

[5] Amelio A, Pizzuti C. An evolutionary and local refinement approach for community detection in signed networks[J]. International Journal on Artificial Intelligence Tools, 2016, 25(4): 1650021.

[6] 王聪,柴争义.基于多目标进化的复杂网络社区检测[J].计算机技术与发展,2020,43(6):112-116.

[7] Gong M G, Cai Q, Chen X, et al. Complex network clustering by multi-objective discrete particle swarm optimization based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(1): 82-97.

[8] Liu C L, Liu J, Jiang Z Z. A multi-objective evolutionary algorithm based on similarity for community detection from signed social networks[J]. IEEE transactions on cybernetics, 2014, 44(12): 2274-2287.

[9] Shang R H, Liu H, Jiao L C. Multi-objective clustering technique based on k-nodes update policy and similarity matrix for mining communities in social networks[J].Physica A, 2017,486:1-24.

[10] Zhang Q, Li H. Moea/d: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Trans. Evol. Comput, 2007, 11(6):712-731.

[11] 李赫,印莹,李源,等.基于多目标演化聚类的大规模动态网络社区检测[J].计算机研究与发展,2019,65(2):10-15.

[12] Amelio A, Pizzuti C. An evolutionary and local refinement approach for community detection in signed networks[J]. International Journal on Artificial Intelligence Tools, 2016, 25(4): 1650021.

[13] 张清琪,刘漫丹.复杂网络社区发现的多目标五行环优化算法[J].计算机科学,2020,98(4):15-20.

[14] Zhang Y F, Liu Y Y , Ma X M. Community detection in signed networks by relaxing modularity optimization with orthogonal and nonnegative constraints[J].Neural Computing and Applications,2019,12(5): 116-122.

[15] Chen J R, Liu D W.Hao F ,et al. Community detection in dynamic signed network: an intimacy evolutionary clustering algorithm[J].Journal of Ambient Intelligence and Humanized Computing, 2020, 62(6):126-138.

SIGNED NETWORK COMMUNITY DISCOVERY ALGORITHM BASED ON MULTI-OBJECTIVE OPTIMIZATION

*TAN Yu-ling1，XIAO Yuan-e2

（1. Department of Information Engineering, Luoding Vocational and Technical College, Luoding, Guangdong 527200, China;2.Network Information Center , Jinggangshan University , Ji’an , Jiangxi 343009,China）

The signed network can describe a variety of relationships between entities, and the community detection in the signed network can dig out the effective information. At the same time, considering connection density and connection symbols, the community discovery problem is modeled as a multi-objective optimization problem. Based on the MOEA/D framework, an improved signed network community discovery algorithm is proposed, and a string-based encoding method and pre-partitioning strategy are designed. Also cross-merger strategy, mutation method are designed. The experimental results show that the algorithm can effectively detect the community structure.

complex network; signed network; community structure; multi-objective optimization

1674-8085（2022）01-0070-08

TP181

A

10.3969/j.issn.1674-8085.2022.01.012

2021-03-03；

2021-05-25

广东省高职高专云计算与大数据专业委员会2019年度课题（GDYJ SKT19-05）；教育部科技发展中心“天诚汇智”创新促教基金课题（2018E01020）

*谭玉玲(1976-)，女，广东罗定人，副教授，硕士，主要从事智能算法和复杂网络研究(E-mail:super_paper@126.com).