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

黄发良; 肖南峰

doi:10.3724/SP.J.1004.2011.01140

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

doi: 10.3724/SP.J.1004.2011.01140

黄发良^1,2, ,,
肖南峰¹

1.
华南理工大学计算机科学与工程学院广州 510006;
2.
福建师范大学软件学院福州 350108

详细信息

通讯作者:
黄发良博士研究生.主要研究方向为数据挖掘.E-mail: faliang.huang@gmail.com

计量
- 文章访问数: 2507
- HTML全文浏览量: 85
- PDF下载量: 1087
- 被引次数: 0
出版历程
- 收稿日期: 2010-11-01
- 修回日期: 2011-03-03
- 刊出日期: 2011-09-20

Discovering Overlapping Communities Based on Line Graph and PSO

HUANG Fa-Liang^{1,2
, ,},
XIAO Nan-Feng¹

1.
School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006;
2.
Faculty of Software, Fujian Normal University, Fuzhou 350108

摘要

摘要: 从优化模块度的角度出发,引入线图理论,给出线图的硬划分与原图的有重叠划分相对应的理论证明, 提出了一种基于线图与粒子群优化技术的网络重叠社区发现算法(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.
- Community discovery /
- line graph /
- particle swarm optimization (PSO) /
- complex network

HTML全文

参考文献(1)

[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

施引文献

资源附件(0)

访问统计