基于线图与PSO的网络重叠社区发现  

Discovering Overlapping Communities Based on Line Graph and PSO

作　　者：黄发良[1,2] 肖南峰[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广州510006 [2]福建师范大学软件学院,福州350108

出　　处：《自动化学报》2011年第9期1140-1144,共5页Acta Automatica Sinica

基　　金：国家自然科学基金(60776816,61171141);广东省自然科学基金重点项目(8251064101000005)资助~~

摘　　要：从优化模块度的角度出发,引入线图理论,给出线图的硬划分与原图的有重叠划分相对应的理论证明,提出了一种基于线图与粒子群优化技术的网络重叠社区发现算法(Communities discovery based on line graph and particle swarm optimization,LGPSO),该方法通过粒子群优化(Particle swarm optimization,PSO)算法寻找网络对应线图的最优划分来发现网络重叠社区,实验结果显示,该方法能够在无先验信息的条件下快速有效地揭示网络的重叠社区结构.From the perspective of optimizing modularity, an overlapping community discovery algorithm, LGPSO, is proposed based on line graph and PSO. The property that a partition of a line graph corresponds to a cover of the corresponding original graph is proved. LGPSO discovers overlapping communities in original graph using PSO to optimize partition of line graph. The experiments on some real-world networks show that the algorithm can fast and effectively discover the intrinsic overlapping communities in networks without any domain information.

关 键 词：社区发现 线图 粒子群优化 复杂网络 

分 类 号：O157.5[理学—数学]