Discovering Overlapping Communities Based on Line Graph and PSO
-
摘要: 从优化模块度的角度出发,引入线图理论,给出线图的硬划分与原 图的有重叠划分相对应的理论证明, 提出了一种基于线图与粒子群优化技术的网络重叠社区发现算法(Communities discovery based on line graph and particle swarm optimization, LGPSO), 该方法通过粒子群优化 (Particle swarm optimization, PSO)算法寻找网络对应线图的最优划分来发现网络重叠社区, 实验结果显示,该方法能够在无先验信息的条件下快速有效地揭示网络的重叠社区结构.Abstract: 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.
-
Key words:
- Community discovery /
- line graph /
- particle swarm optimization (PSO) /
- complex network
-
[1] Huang Fa-Liang. Studies on community detection and its application in information network. Complex Systems and Complexity Science, 2010, 7(1): 64-74(黄发良. 信息网络的社区发现及其应用研究. 复杂系统与复杂性科学, 2010, 7(1): 64-74)[2] Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814-818[3] Gregory 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[4] Pinney J W, Westhead D R. Betweenness-based decomposition methods for social and biological networks. In: Proceedings of the International Conference Interdisciplinary Statistics and Bioinformatics. Leeds, UK: Leeds University Press, 2006. 87-90[5] Shen 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[6] Ahn Y Y, Bagrow J P, Lehmann S. Communities and hierarchical organization of links in complex networks. 2009, arXiv: 0903.3178[7] Wang X, Jiao L, Wu J. Adjusting from disjoint to overlapping community detection of complex networks. Physica A: Statistical Mechanics and Its Applications, 2009, 388(24): 5045-5056[8] Kennedy J, Eberthart R. Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks. Perth, Australia: IEEE, 1995. 1942-1948[9] Liao C J, Tseng C T, Luarn P. A discrete version of particle swarm optimization for flowshop scheduling problems. Computers and Operations Research, 2007, 34(10): 3099-3111[10] Pan Q K, Tasgetiren M F, Liang Y C. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Computers and Operations Research, 2008, 35(9): 2807-2839[11] Jin Y X, Cheng H Z, Yan J Y, Zhang L. New discrete method for particle swarm optimization and its application in transmission network expansion planning. Electric Power Systems Research, 2007, 77(3-4): 227-233[12] Kennedy J, Eberhart R C, Shi Y. Swarm Intelligence. San Francisco: Morgan Kaufmann, 2001[13] Duan Xiao-Dong, Wang Cun-Rui, Liu Xiang-Dong, Lin Yan-Ping. Web community detection model using particle swarm optimization . Computer Science, 2008, 35(3): 18-21(段晓东, 王存睿, 刘向东, 林延平. 基于粒子群算法的Web社区发现. 计算机科学, 2008, 35(3): 18-21)[14] Girvan M, Newman M E J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 2001, 99(12): 7821-7826[15] Nicosia V, Mangioni G, Carchiolo V, Malgeri M. Extending the definition of modularity to directed graphs with overlapping communities. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2009(3): 1-22
点击查看大图
计量
- 文章访问数: 2445
- HTML全文浏览量: 73
- PDF下载量: 1079
- 被引次数: 0