李国庆， 程林凤

(1.中国矿业大学 理学院，江苏 徐州 221008;2.江苏联合职业技术学院，江苏 徐州 221008)

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

李国庆1,2*， 程林凤1

(1.中国矿业大学 理学院，江苏 徐州 221008;2.江苏联合职业技术学院，江苏 徐州 221008)

社会网络中的传递性对于网络中的社团分析和节点重要性分析都有着十分重要的意义.为了提高社会网络传递性分析中三角计数的性能，提出了一种MapReduce环境下的三角计数并行计算方法.首先，将社会网络的传递性问题转化为计算网络中三角个数的问题.其次，在计算网络中的三角时按照节点之间的度约束对重复的三角进行了过滤，并在MapReduce环境下实现了高效的三角计数并行算法.最后，分析了MapReduce环境下三角计数并行算法的时间和空间复杂性.理论分析和实验表明，该文提出的方法与相关方法相比，不仅降低了算法的内存使用量，也减小了算法的运行时间，因而更适用于大规模社会网络的传递性分析.

社会网络；三角；并行计算；聚类系数

随着“六度分割理论”的提出，社会网络引起了社会各界的广泛关注.社会网络[1]是一门与社会学、心理学、数学、计算机科学等学科相关的交差学科.社会网络分析方法将社会网络表示为矩阵，并用矩阵分析的方法分析社会网络的相关属性和特征[2].社会网络的一个重要特征是节点之间往往呈现社团结构，即社团内部节点间的连接很紧密，而不同社团节点之间的连接很松散.为了衡量……