SIMPLE: a simplifying-ensembling framework for parallel community detection from large networks
SIMPLE: a simplifying-ensembling framework for parallel community detection from large networks
复制标题
DOI：
10.1007/s10586-015-0504-2
复制
发表时间：
2016-03
期刊：
影响因子：
--
通讯作者：
Zhiang Wu;Guangliang Gao;Zhan Bu;Jie Cao
中科院分区：
文献类型：
--
作者：
Zhiang Wu;Guangliang Gao;Zhan Bu;Jie Cao
在复杂网络分析中，社区发现是一项经典而又非常困难的任务。随着社交媒体的日益爆炸性增长，将社区检测方法扩展到大型网络中最近引起了相当大的兴趣。在本文中，我们提出了一种新的简化和集成(SIMPLE)并行社区发现框架。该算法利用随机链路抽样简化网络，得到每个抽样图的基本划分。然后，使用基于K-Means的共识聚类对多个基本划分进行集成，得到高质量的社区结构。SIMPLE中的所有阶段，包括随机采样、采样图划分和共识聚类，都被封装到MapReduce中进行并行执行。在六个真实社会网络上的实验分析了SIMPLE中的关键参数和因素，并证明了SIMPLE的有效性和高效性。
Community detection is a classic and very difficult task in complex network analysis. As the increasingly explosion of social media, scaling community detection methods to large networks has attracted considerable recent interests. In this paper, we propose 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. All of phases in SIMPLE, including random sampling, sampled graph partitioning, and consensus clustering, are encapsulated into MapReduce for parallel execution. Experiments on six real-world social networks analyze key parameters and factors inside SIMPLE, and demonstrate both effectiveness and efficiency of the SIMPLE.