陈季梦陈佳俊刘 杰*黄亚楼王 嫄冯 霞

①(南开大学计算机与控制工程学院 天津 300071)

②(南开大学软件学院 天津 300071)

③(中国民航大学民航信息技术科研基地 天津 300300)

基于结构相似度的大规模社交网络聚类算法

陈季梦①陈佳俊②刘 杰*①黄亚楼②王 嫄①冯 霞③

①(南开大学计算机与控制工程学院 天津 300071)

②(南开大学软件学院 天津 300071)

③(中国民航大学民航信息技术科研基地 天津 300300)

针对社交网络的有向交互性和大规模特性，该文提出一种基于结构相似度的有向网络聚类算法(DirSCAN)，以及相应的分布式并行算法(PDirSCAN)。考虑社交网络中节点间的有向交互性，将行为结构相似的节点聚集起来，并进行节点功能分析。针对社交网络规模巨大的特点，提出MapReduce框架下的分布式并行聚类算法，在确保聚类结果一致的前提下，提高处理性能。大量真实数据集上的实验结果表明，DirSCAN比无向网络聚类算法(SCAN)在F1上可提高2.34%的性能，并行算法PDirSCAN比DirSCAN运行速度提升1.67倍，能够有效处理大规模的有向网络聚类问题。

社交网络；有向网络聚类；并行算法；MapReduce

1 引言

随着博客、微博等社交媒体的兴起，以用户为节点、以用户关系为边的社交网络迅猛增长。用户的兴趣、行为、功能等关系使社交网络中存在多个社区或簇。为了发现网络中隐藏的簇结构，传统的网络聚类方法主要基于链接的稠密度(linkdensity)，使得簇内节点距离较近，簇间节点距离较远，如经典的Newman快速算法[1]和Kernighan-Lin算法[2]。然而，以上算法忽略了社交网络有向交互性和节点具有不同功能。……