Efficient Parallel Community Detection in Large Edge-Intensive Networks

摘要：

　　Community detection is a classic and very difficult task in social network analysis.A large number of methods have been developed for both efficient and effective community detection.However,much of the existing methods are heavily dependent on the number of links in the network,and thus they often suffer from the computational inefficiency when meeting large edge-intensive networks.In this paper,we present a novel SIMPLifying and Ensembling(SIMPLE)framework for parallel community detection.It employs the random link sampling to simplify the network and obtain basic partitionings on every sampled graphs.Then,the K-means-based Consensus Clustering is used to ensemble a number of basic partitionings to get high-quality community structures.Meanwhile,steps of random sampling and sampled graph partitioning are encapsulated into MapReduce to further improve the efficiency.Experiments on four real-world social networks analyze key parameters and factors inside SIMPLE,and demonstrate the effectiveness of the SIMPLE.

关键词： Social Network Community Detection Random Sampling Consensus Clustering MapReduce

作者: Guangliang Gao Zhan Bu Zhiang Wu Yuan Li Jie Cao

作者单位: College of Computer Sci.and Eng.,Nanjing University of Science and Technology,China Jiangsu Provincial Key Lab.of E-Business,Nanjing University of Finance and Economics,China College of Computer Sci.and Eng.,Nanjing University of Science and Technology,China;Jiangsu Provinci

会议类型: 国际会议

会议名称: 2014 2nd International Conference on Advanced Cloud and Big Data (CBD 2014)(2014年先进云计算和大数据国际会议)

会议地点: 安徽黄山

会议语种:英文

页码: 253-260

在线出版日期: 2014-11-20（万方平台首次上网日期，不代表论文的发表时间）