基于MapReduce并行架构的大数据社会网络社团挖掘方法  

Community Detection in Big Social Networks Based on MapReduce Framework

作　　者：邓波[1] 张玉超[1] 金松昌[2] 林旺群[1] 

机构地区：[1]北京系统工程研究所,北京100101 [2]国防科学技术大学计算机学院,长沙410073

出　　处：《计算机研究与发展》2013年第S2期187-195,共9页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2013AA01A215)

摘　　要：随着社会网络数据规模的急剧上升,传统的社会网络社团挖掘方法无法有效应对大数据社会网络场景.基于MapReduce并行计算框架,提出了一种针对大数据社会网络的社团挖掘方法.借助于信息压缩理论模型,该方法首先对给定的社会网络进行二进制信息编码,然后按照信息描述长度理论并行计算社会网络中给定编码方案的信息描述长度,从而将社会网络社团并行挖掘问题转化为并行搜索社会网络中最小信息描述长度所对应的编码方案问题.通过采用并行随机迭代方式搜索大数据社会网络编码状态空间中的最佳编码方案,提出的大数据社会网络社团挖据方法具有自动发现最佳社团数量、算法复杂度低、计算精度高和高可扩展性等特点.与同类方法进行实验对比,从算法的计算精度和计算性能两方面验证了所提方法的有效性.With the social data size increasing greatly in many real applications such as online social websites,the traditional community detection methods can not deal with the big social network effectively.In this paper,we propose a community detection method based on MapReduce framework for big social network applications.We first encode the whole graph,which represents the big social network,with binary code by the information compression model.Then,according to the minimal information description theory,we parallel to compute the total bits required for describing the whole graph under a given encoding scheme.This process transfers community detection into the problem of parallel searching the minimal information schema in the state space of the given graph.Finally,we propose an effectively community detection method through parallel and iterative searching the optimal encoding scheme,which corresponding to the optimal partition of the graph.Our method can not only automatically discover the number of communities,but also perform excellently on complexity, accuracy and scalability.Compared with the similar approaches,we demonstrate the effectiveness of our method from two aspects including accuracy and efficiency.

关 键 词：大数据社会网络 MAPREDUCE 社团 信息压缩 随机游走 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]