基于MapReduce的图结构聚类算法

来源：软件学报杂志2018年第3期北京时间：

作者：张伟鹏,李振军,李荣华,刘宇鸿,毛睿,乔少杰

单位：张伟鹏，深圳大学 计算机与软件学院, 广东 深圳 51806011,李振军，深圳大学 计算机与软件学院, 广东 深圳 51806002,李荣华，深圳大学 计算机与软件学院, 广东 深圳 51806003,刘宇鸿，深圳大学 计算机与软件学院, 广东 深圳 51806004,毛睿，深圳大学 计算机与软件学院, 广东 深圳 51806005,乔少杰，成都信息工程大学 网络空间安全学院, 四川 成都 61022506

摘要：图结构聚类（SCAN）是一种著名的基于密度的图聚类算法，该算法不仅能够找到图中的聚类结构，而且还能发现图中的Hub节点和离群节点.然而，随着图数据规模越来越大，传统的SCAN算法的复杂度为O（m1.5）（m为图中边的条数），因此很难处理大规模的图数据.为了解决SCAN算法的可扩展性问题，提出一种基于MapReduce的海量图结构聚类算法MRSCAN，这是一种计算核心节点以及两种合并聚类的MapReduce算法.最后，在多个真实的大规模图数据集上进行实验测试，实验结果验证了算法的准确性、有效性以及可扩展性.

关键词：图数据;并行计算模型;MapReduce;图结构聚类

基金资助：国家自然科学基金（61402292，61772091）；国家自然科学基金广东省联合基金（U1301252）；教育部人文社会科学研究规划基金（15YJAZH058）