高效的社会网络传递性MapReduce并行计算方法  

Efficient Transitivity Computing of Social Networks in MapReduce

作　　者：李国庆[1,2] 程林凤[1] 

机构地区：[1]中国矿业大学理学院,江苏徐州221008 [2]江苏联合职业技术学院,江苏徐州221008

出　　处：《湘潭大学自然科学学报》2015年第2期102-107,共6页Natural Science Journal of Xiangtan University

基　　金：江苏省教育教学改革立项重点课题项目(苏教科院ZCZ32)

摘　　要：社会网络中的传递性对于网络中的社团分析和节点重要性分析都有着十分重要的意义.为了提高社会网络传递性分析中三角计数的性能,提出了一种MapReduce环境下的三角计数并行计算方法.首先,将社会网络的传递性问题转化为计算网络中三角个数的问题.其次,在计算网络中的三角时按照节点之间的度约束对重复的三角进行了过滤,并在MapReduce环境下实现了高效的三角计数并行算法.最后,分析了MapReduce环境下三角计数并行算法的时间和空间复杂性.理论分析和实验表明,该文提出的方法与相关方法相比,不仅降低了算法的内存使用量,也减小了算法的运行时间,因而更适用于大规模社会网络的传递性分析.Research on transitivity of social networks is very important for analysis of community and node importance in social networks.In order to improve the performance of triangle counting for analyzing network transitivity,this paper proposed a parallel triangle counting algorithm in MapReduce environment.Firstly,we transformed the problem of network transitivity into the counting of triangles in a network.Secondly,while computing triangles in a network,we removed repeated triangles according to the degree constraint of nodes in a triangle,and implemented an efficient parallel triangle counting algorithm in MapReduce.Finally,we analyzed the time and space complexity of the proposed algorithm.Theoretical analysis and the experiments show that,our proposed approach has less memory usage and execution time compared with related work,and thus is more suitable for analyzing network transitivity for large-scale social networks.

关 键 词：社会网络 三角 并行计算 聚类系数 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]