期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于线图与PSO的网络重叠社区发现 被引量：9

Discovering Overlapping Communities Based on Line Graph and PSO
下载PDF
导出
摘要 从优化模块度的角度出发,引入线图理论,给出线图的硬划分与原图的有重叠划分相对应的理论证明,提出了一种基于线图与粒子群优化技术的网络重叠社区发现算法(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.
作者 黄发良 肖南峰
机构地区 华南理工大学计算机科学与工程学院 福建师范大学软件学院
出处 《自动化学报》 EI CSCD 北大核心 2011年第9期1140-1144,共5页 Acta Automatica Sinica
基金 国家自然科学基金(60776816,61171141) 广东省自然科学基金重点项目(8251064101000005)资助~~
关键词 社区发现 线图 粒子群优化 复杂网络 Community discovery, line graph, particle swarm optimization （PSO）, complex network
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献15

  • 1黄发良.信息网络的社区发现及其应用研究[J].复杂系统与复杂性科学,2010,7(1):64-74. 被引量：19
  • 2Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the over- lapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814-818.
  • 3Gregory S. Finding overlapping communities using disjoint community detection algorithms. In: Proceedings of the Complex Networks: Complex Net 2009. Berlin, Germany: Springer-Verlag, 2009. 47-61.
  • 4Pinney J W, Westhead D R. Betweenness-based decomposi- tion methods for social and biological networks. In: Proceed- ings of the International Conference Interdisciplinary Statis- tics and Bioinformatics. Leeds, UK: Leeds University Press, 2006. 87-90.
  • 5Shen H, Cheng X, Cai K, Hu M B. Detect overlapping and hierarchical community structure in networks. Physica A: Statistical Mechanics and Its Applications, 2008, 388(8): 1706-1712.
  • 6Ahn Y Y, Bagrow J P, Lehmann S. Communities and hi- erarchical organization of links in complex networks. 2009, arXiv: 0903.3178.
  • 7Wang X, Jiao L, Wu J. Adjusting from disjoint to overlap- ping community detection of complex networks. Physica A: Statistical Mechanics and Its Applications, 2009, 388(24): 5045-5056.
  • 8Kennedy J, Eberthart R. Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks. Perth, Australia: IEEE, 1995. 1942-1948.
  • 9Liao C J, Tseng C T, Luarn P. A discrete version of particle swarm optimization for flowshop scheduling problems. Com- puters and Operations Research, 2007, 34(10): 3099-3111.
  • 10Pan Q K, Tasgetiren M F, Liang Y C. A discrete parti- cle swarm optimization algorithm for the no-wait flowshop scheduling problem. Computers and Operations Research, 2008, 35(9): 2807-2839.

二级参考文献73

  • 1杨楠,弓丹志,李忺,孟小峰.Web社区发现技术综述[J].计算机研究与发展,2005,42(3):439-447. 被引量：35
  • 2Luce R D,Perry A D. A method of matrix analysis of group structure[J]. Psychometrika,1949,14(2) : 95 -116.
  • 3Alba R D. A graph-theoretic definition of a sociometric clique[ J]. J Math Sociol, 1973,3 (1) : 113 -126.
  • 4Luce R D. Connectivity and generalized cliques in sociometric group structure[J]. Psychometrika, 1950, 15 (2) :169 -190.
  • 5Mokken R J. Cliques, clubs and clans[J]. Quality and Quantity, 1979,13(2) : 161 - 173.
  • 6Seidman S B, Foster B L. A graph-theoretic generalization of the clique concept[ J]. J Math Sociol. 1978, 6:139 -154.
  • 7Seidman S B. Network structure and minimum degree[ J]. Soc Netw, 1983,5:269 -287.
  • 8Luccio F, Sami M. On the decomposition of networks into minimally interconnected networks[ J]. IEEE Trans Circuit Theory, 1969, 2(16) : 184 -188.
  • 9Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. PNAS, 2004, 101 (9): 2658 - 2663.
  • 10Hu Y Q, Chen H B, Zhang P, et al. Comparative definition of community and corresponding identifying algorithm[J]. Phys Rev E, 2008, 78(2) :026121.

共引文献33

同被引文献166

  • 1潘峰,陈杰,甘明刚,蔡涛,涂序彦.粒子群优化算法模型分析[J].自动化学报,2006,32(3):368-377. 被引量：67
  • 2李宁,孙德宝,邹彤,秦元庆,尉宇.基于差分方程的PSO算法粒子运动轨迹分析[J].计算机学报,2006,29(11):2052-2060. 被引量：48
  • 3NEWMAN M E J. Fast algorithm for detecting community structure in networks[ J]. Physical Review E, 2004, 69(6) : 66 - 76.
  • 4HARRIS M, OWENS J, SENGUPTA S, et al. CUDPP: CUDA data parallel primitives library[ EB/OL]. [ 2010- 10- 10]. http://www. gpgpu, org/developer/cudapp/.
  • 5HE B, LU M, YANG K, et al. Relational query co-processing on graphics processors[ J]. ACM Transactions on Database System, 2009, 34(4) : 1 -39.
  • 6AILA T, LAINE S. Understanding the efficiency of ray traversal on GPUs[C]// HPG '09: Proceedings of the Conference on High Performance Graphics. New York: ACM Press, 2009:145 - 149.
  • 7TZENG S, PATNEY A, OWENS J D. Task management for irreg- ular-paralle workloads on the GPU[ C]//HPG '10: Proceedings of the Conference on High Performance. Piscataway, NJ: IEEE Press, 2010:29-37.
  • 8PHARR M, FERNANDO R. GPU Gems 2 [ M]. Boston: Addison Wesley, 2005:493 - 495.
  • 9SILBERSTEIN M, SCHU A. GEIGER D, et al. Efficient compu- tatlon of sum-products on GPUs through software-managed cache [ C]//Proceedings of the 22nd Annum International Conference on Supercomputing. New York: ACM Press, 2008:173 - 179.
  • 10ROSVALL M. Information horizons in a complex world [ D ]. Umea : Umea University, 2006.

引证文献9

二级引证文献63

自动化学报
2011年 第9期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部