 2013, Vol. 26 Issue (7): 648-659 DOI: :10.1088/1367-2630/11/3/033015
[11] Huang Faliang, Xiao Nanfeng |
|
|
|
| Overlapping Community Detection in Complex Networks Based on Cluster Prototypes |
| JIANG Ya-Wen,JIA Cai-Yan,YU Jian |
| School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044 |
|
|
|
|
Abstract Community structure is one of the important topological characteristics in complex networks. In real world,community structures in networks are often overlapped. And it is difficult to efficiently detect overlapping communities in a network. Optimizing Qov function directly is a solution for overlapping community detection,however,it is easy to generate a local optimal solution. To solve this problem,the concept of vertex central membership measure is introduced,and based on cluster prototypes of nodes in a network,an efficient framework is proposed to identify overlapping communities. Then the framework is applied to some classic clustering algorithms. The experimental results show that the proposed method avoids generating local optimal solution,and it is more efficient than the other algorithms on synthetic and real-world networks.
|
|
Received: 25 June 2012
|
|
|
|
|
|
[1] Watts D J,Strogatz S H. Collective Dynamics of ‘Small-World’ Networks. Nature,1998,393(6684): 440-442
[2] Barabási A L,Bonabeau E. Scale-Free Networks. Scientific American,2003,288(5): 60-69
[3] Girvan M,Newman M E J. Community Structure in Social and Biological Networks. Proceedings of the National Academy of Sciences,2002,99(12): 7821-7826
[4] Wei Fang,Qian Weining,Wang Chen,et al. Detecting Overlapp-ing Community Structures in Networks. World Wide Web,2009,12(2): 235-261
[5] Palla G,Derényi I,Farkas I,et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature,2005,435(7043): 814-818
[6] Zhang Shihua,Wang Ruisheng,Zhang Xiangsun. Identification of Overlapping Community Structure in Complex Networks Using Fuzzy C-Means Clustering. Physica A: Statistical Mechanics and Its Applications, 2007,374(1): 483-490
[7] Gregory S. An Algorithm to Find Overlapping Community Structure in Networks // Proc of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases. Warsaw,Poland,2007: 91-102
[8] Gregory S. A Fast Algorithm to Find Overlapping Communities in Networks // Proc of the European Conference on Machine Learning and Knowledge Discovery in Databases. Antwerp,Belgium,2008: 408-423
[9] Gregory S. Finding Overlapping Communities Using Disjoint Community Detection Algorithms // Proc of the International Workshop on Complex Networks. Berlin,Germany: Springer-Verlag,2009: 47-61
[10] Lancichinetti A,Fortunato S,Kertesz J. Detecting the Overlapping and Hierarchical Community Structure of Complex Networks. New Journal of Physics,2009. DOI:10.1088/1367-2630/11/3/033015
[11] Huang Faliang,Xiao Nanfeng. Rough Spectral Clustering Algorithm Applied to Overlapping Network Communities Discovery. Journal of Chinese Computer Systems,2012,33(2): 263-266(in Chinese)
(黄发良,肖南峰.用于网络重叠社区发现的粗糙谱聚类算法.小型微型计算机系统,2012,33(2): 263-266)
[12] Ball B,Karrer B,Newman M E J. An Efficient and Principled Method for Detecting Communities in Networks. Physical Review E,2011. DOI:10.1103/PhysRevE.84.036103
[13] Nicosia V,Mangioni G,Carchiolo V,et al. Extending the Definition of Modularity to Directed Graphs with Overlapping Communities. Journal of Statistical Mechanics,2009. DOI:10. 1088/1742-5468/2009/03/P03024
[14] Psorakis I,Roberts S,Ebden M. Overlapping Community Detection Using Bayesian Non-Negative Matrix Factorization. Physical Review E,2011. DOI:10.1103/PhysRevE.83.066114
[15] Zhang Y,Yeung D Y. Overlapping Community Detection via Bounded Nonnegative Matrix Tri-Factorization // Proc of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Beijing,China,2012: 606-614
[16] Gregory S. Finding Overlapping Communities in Networks by Label Propagation. New Journal of Physics,2010. DOI:10.1088/1367-2630/12/10/103018
[17] Xie Jierui,Szymanski B K,Liu Xiaoming. SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process // Proc of the 11th International Conference on Data Mining Workshops. Vancouver,Canada,2011: 344-349
[18] Wu Jianshe,Jiao Licheng,Jin Chao,et al. Overlapping
Community Detection via Network Dynamics. Physical Review E,2012. DOI:10.1103/PhysRevE.85.016115
[19] Ahn Y Y,Bagrow J P,Lehmann S. Link Communities Reveal Multiscale Complexity in Networks. Nature,2010,466(7307): 761-764
[20] Frey B J,Dueck D. Clustering by Passing Messages between Data Points. Science,2007,315(5814): 972-976
[21] MacQueen J. Some Methods for Classification and Analysis of Multivariate Observations // Proc of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley,USA,1967,I: 281-297
[22] Lü Linyuan,Zhou Tao. Link Prediction in Complex Networks: A Survey. Physica A,2011,390(6): 1150-1170
[23] Hu Yanqing,Li Menghui,Zhang Peng,et al. Community Detection by Signaling on Complex Networks. Physical Review E,2008. DOI:10.1103/PhysRevE.78.016115
[24] Newman M E J,Girvan M. Finding and Evaluating Community Structure in Networks. Physical Review E,2004. DOI:10.1103/PhysRevE.69. 026113
[25] Shen Huawei,Cheng Xueqi,Cai Kai,et al. Detect Overlapping and Hierarchical Community Structure in Networks. Physical A: Statistical Mechanics and Its Applications,2009,388(8): 1706-1712
[26] Ng A Y,Jordan M I,Weiss Y. On Spectral Clustering: Analysis and an Algorithm [EB/OL]. [2012-5-5]. http://www.uta.edu/faculty/rcli/Teaching/math5392/papers/ngjw2001.pdf
[27] Scott J. Social Network Analysis: A Handbook. 2nd Edition. London,UK: Sage Publications,2000
[28] Steinhaeuser K,Chawla N V. Identifying and Evaluating Community Structure in Complex Networks. Pattern Recognition Letters,2010,31(5): 413-421
[29] Lancichinetti A,Fortunato S. Benchmarks for Testing Community Detection Algorithms on Directed and Weighted Graphs with Overlapping Communities. Physical Review E,2009. DOI:10.1103/PhysRevE.80.016118
[30] Zachary W W. An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research,1977,33(4): 452-473
[31] Lusseau D,Schneider K,Boisseau O J,et al. The Bottlenose Dolphin Community of Doubtful Sound Features a Large Proportion of Long-Lasting Associations. Behavioral Ecology and Sociobiology,2003,54(4): 396-405
[32] Knuth D E. The Stanford GraphBase: A Platform for Combinatorial Computing. New Jersey,USA: Addison-Wesley Professional,1993
[33] Newman M E J. Finding Community Structure in Networks Using the Eigenvectors of Matrices. Physical Review E,2006. DOI:10.1103/PhysRevE.74.036104
[34] Krebs V. Social Network Analysis Software Services for Organizations,Communities,and Their Consultants [EB/OL]. [2012-05-20]. http://www.orgnet.com/
[35] Gleiser P,Danon L. Community Structure in Jazz. Advances in Complex Systems,2003,6(4): 565-573
[36] Batagelj V,Mrvar A. Pajek Datasets [DB/OL]. [2012-05-20]. http://vlado.fmf.uni-lj.si/pub/networks/data/
[37] Duch J,Arenas A. Community Detection in Complex Networks Using Extremal Optimization. Physical Review E,2005. DOI:10.1103/PhysRevE.72.027104
[38] Guimerà R,Danon L,Díaz Guilera A,et al. Self-Similar Community Structure in a Network of Human Interactions. Physical Review E,2003. DOI:10.1103/PhysRevE.68.065103 |
|
|
|
