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

来源：电子与信息学报杂志2015年第2期北京时间：

作者：陈季梦, 陈佳俊, 刘杰, 黄亚楼, 王嫄, 冯霞

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

关键词：社交网络, 有向网络聚类, 并行算法, MapReduce

基金资助：国家自然科学基金(61105049, 61300166)，中国民航信息技术科研基地开放课题基金(CAAC-ITRB-201303, CAAC-ITRB-201204)，天津市科技计划项目(13ZCZDGX01098)和天津市自然科学基金(14JCQNJC00600)资助课题