计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (22): 56-58.DOI: 10.3778/j.issn.1002-8331.2008.22.016

• 理论研究 • 上一篇    下一篇

基于PSO微粒群算法的复杂网络社区结构发现

戴飞飞,唐普英   

  1. 电子科技大学 光电信息学院,成都 610054
  • 收稿日期:2007-10-10 修回日期:2008-01-21 出版日期:2008-07-11 发布日期:2008-07-11
  • 通讯作者: 戴飞飞

Community structure detection in complex networks using Particle Swarm Optimization algorithm

DAI Fei-fei,TANG Pu-ying   

  1. School of Opto-Electronic Information,University of Electronic Science and Technology of China,Chengdu 610054,China
  • Received:2007-10-10 Revised:2008-01-21 Online:2008-07-11 Published:2008-07-11
  • Contact: DAI Fei-fei

摘要: 复杂网络社区结构划分日益成为近年来复杂网络的研究热点,到目前为止,已经提出了很多分析复杂网络社区结构的算法。但是大部分算法还存在一定的缺陷,而且有些算法由于其时间复杂度的过高导致其不适合应用于对大型网络的分析。提出了一种基于PSO微粒群算法的复杂网络社区结构分析方法。此方法无需预先知道组成该复杂网络的社区数量、社区内的节点数以及任何门限值。该算法的可行性用Zachary Karate Club和College Football Network模型进行验证。

关键词: 复杂网络, 社区结构, PSO微粒群算法

Abstract: Community structure identification has been one of the most popular research areas in recent years and there has been many algorithm proposed so far to detect community structures in complex networks in varied topics,where most of the algorithm have some drawbacks,and some of them are not suitable for very large networks because of their time-complexity.In this paper,an algorithm for detecting community structures in complex network is presented,which is based on the Particle Swarm Optimization algorithm.It doesn’t need any priori knowledge about the numbers of communities and any threshold values.The algorithm is tested on the two network data named Zachary Karate Club and College Football.

Key words: complex networks, community structure, Particle Swarm Optimization(PSO) algorithm