一种基于非支配排序遗传算法的社区发现算法

发布时间：2021-11-21 04:12

　　在将复杂网络的社区发现问题建模为多目标优化问题时,采用带精英策略的非支配排序遗传算法（NSGA-Ⅱ）的方法来寻找问题最优解。该算法解决了拓展后的模块度密度问题中的分辨率限制参数调整问题,以及优化模块度密度函数的分辨率限制问题,使得算法运行一次可得到一组不同的划分结果,以便决策者根据需要进行选择。另外,遗传算法的交叉和变异算子加入了网络顶点的邻域信息,符合真实网络的特性,且基于图的编码方式保证了社区数目的自适应性。实验结果证明,采用基于非支配排序遗传算法的社区发现算法能有效的发现出社区结构。 

【文章来源】：信阳农林学院学报. 2020,30(03)

【文章页数】：6 页

【部分图文】：

基于NSGA-II的社区发现算法在真实世界网络上所得PF

空手道俱乐部网络是由社会学家Zachary用了两年时间在大学空手道俱乐部中观察34名俱乐部成员之间的社会关系网络[9-10]。最后，一个社区变成了两个社区，如图1所示。这主要是因为空手道教练辞职后有部分队员与教练一同离开，形成了新的社交关系网络。USA大学生足球联赛俱乐部社交网络数据集是Newman和Girvan两人观察的2000年秋 季USA大学生足球联赛常规赛季 的比赛网络数据[11-12],根据赛区划分将球队分成115个节点,因此,网络中每个节点表示一个球队,两个节点之 间进行的比赛由 网络中的连接线表示。每个节点在常规赛季中平均要有11条连接线,包括7条赛区 内的连接和4条赛区间的连接。该社交网络数据集中共有115个球队和616场比赛,所有的球队被划分成12个赛区,也就是12个社区。

为了进一步证明本算法的有效性,这里随机选取算法在karate网络上所得解并给出其对应的社区划分情况,如图3。图3(a)与(b)得到了与真实划分一致的解,(c)中所得划分得到了三个社区,其中将原有的一个大社区分为了两个,(d)所得划分与(c)类似,同样是将大的社区划分为两个小社区。如此一来,我们可以根据决策者的需要选取合适的划分,这也是采用多目标算法进行优化社区发现的最主要的优点。图3 随机选取Karate网络PF中的解对应的社区划分情况

【参考文献】：
期刊论文
[1]基于特征向量局部相似性的社区检测算法[J]. 杨旭华,沈敏.  计算机科学. 2020(02)
[2]基于贪婪局部路径重连的随机并行社区检测[J]. 单康康,郭晔,陈文智.  计算机工程. 2019(06)



本文编号：3508748