摘要
为解决基于模块度的算法时间复杂度普遍较高、精度不足及存在分辨率限制等问题,提出一种基于局部粒子群的社团发现算法LPSO。每个粒子拥有局部适应值f以及飞行方向v,通过判断粒子运动前后的局部适应值f是否增大决定两相邻节点是否属于同一社团,达到发现社团的目的。人工网络的实验结果表明,相较于FN、FUA、LPA、SL、WT这5种经典的社团发现算法,在社团规模较小的LFR网络中,当混合参数u大于0.55的条件时,LPSO算法的社团发现能力要显著高于上述5种算法;真实网络的实验结果表明,LPSO的模块度值与上述5种算法得到的最优结果相当;对分辨率限制问题的实验结果表明,LPSO比FN和FUA具有更强的发现高分辨率社团结构的能力。
To address the problems of existing algorithms based on modularity showing high time-complexity and suffering from a well-known resolution limit problem,an algorithm based on local particle swarm optimization（LPSO）for detecting community structure was constructed.Each particle had a fitness value f and a flight direction v.Whether two adjacent nodes belonged to the same community was dependent on whether the fitness value representing the particle moving from one point to another was increasing.The results of experiments tested in artificial networks show that LPSO has higher precision than FN,FUA,LPA,SL,WT,especially when mixing parameter is more than 0.55 and in LFR networks with small-scale community.The results of experiments tested in real world networks indicate that the modularity value calculated using LPSO has no much difference with the best results.LPSO is better at finding community structure with high resolution than FN and FUA in the research of resolution limit problem.
出处
《计算机工程与设计》
北大核心
2016年第6期1500-1504,共5页
Computer Engineering and Design
基金
国家自然科学基金项目(81173201)
关键词
社团发现
模块度
粒子群
适应值
分辨率限制
community detection
modularity
PSO
fitness value
resolution limit problem
