作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

基于多层粒子群的社团发现算法

章亮,姚世军,陈楚湘   

  1. (信息工程大学 理学院,郑州 450001)
  • 收稿日期:2015-10-15 出版日期:2016-10-15 发布日期:2016-10-15
  • 作者简介:章亮(1990—),男,硕士研究生,主研方向为社会网络、数据挖掘;姚世军,教授;陈楚湘,副教授、博士。
  • 基金资助:
    国家自然科学基金资助项目(81173201)。

Community Discovery Algorithm Based on Multilayer Particle Swarm

ZHANG Liang,YAO Shijun,CHEN Chuxiang   

  1. (College of Science,Information Engineering University,Zhengzhou 450001,C
  • Received:2015-10-15 Online:2016-10-15 Published:2016-10-15

摘要: 目前基于模块度算法普遍存在时间复杂度较高、结果精度较低以及分辨率限制等问题。为此,提出一种基于多层局部粒子群的社团发现算法。每个粒子拥有一个飞行方向和局部适应值f,并通过局部判断粒子运动前后适应值是否增大决定两节点是否属于同一社团。该算法把单层上发现的社团视为一个超级节点,构建上层网络,得到更粗粒度的社团结构和模块度值。实验结果表明,对于大规模的网络数据,当混合参数u<0.7时,该算法与Infomap算法的效果相当,当u>0.7时,该算法的效果明显较优,能得到正确的社团划分结果,有效缓解分辨率限制的问题。

关键词: 社团发现, 模块度, 适应值, 分辨率限制, 粒子群

Abstract: Current community detection algorithms based on modularity have shortcomings like high time-complexity and low accuracy,they suffer form resolution limit.Therefore an algorithm based on Multilayer Particle Swarm Optimization(MPSO) for detecting community is proposed.Each particle has flight direction and a fitness value f.Whether two adjacent nodes belong to the same community is dependent on whether the fitness value is increasing when the particle move from one node to another.The proposed algorithm treats community as one super node to construct an upper network and get more coarse-grained community structure and higher modularity value.Experimental results show that the proposed algorithm can rival infomap algorithm when the mixing parameter u is less than 0.7 for dealing with large-scale network.When u is greater than 0.7,the proposed algorithm is better.It can get accurate results,and alleviate resolution limit problem effectively.

Key words: community discovery, modularity, fitness value, resolution limit, particle swarm

中图分类号: