MR—GSpar：一种基于MapReduce的大图稀疏化算法.pdfVIP

第40卷 第 1O期 计 算 机 科 学 Vo1．40No．10 2013年 1O月 Computer Science Oct2013 MR—GSpar：一种基于MapReduce的大图稀疏化算法 陈德华 周 蒙 孙延青 郑亮亮 (东华大学计算机科学与技术学院 上海201620) (上海市浦东新区电子政务管理中心 上海 200135)。 摘 要 图的稀疏化是图聚类分析中数据预处理的关键操作，已得到广泛的关注。针对图数据 日益普及、规模不断增 大的现状，提出了一种基于MapReduce的面向大规模图的稀疏化算法，即MR-GSpar算法。该算法在 MapReduce并 行计算框架的基础上，通过对传统的最小哈希(Minhash)算法的并行化改造，使其可在分布式的集群环境中实现对大 规模 图数据的高效稀疏化处理。真实数据集上的实验表明了该算法的可行性与有效性。 关键词 图稀疏化，Minhash，MapReduce框架，MR-GSpar算法 中图法分类号 TP3111 文献标识码 A M R-GSpar：A DistributedLargeGraph SparsificationAlgorithm BasedonM apReduce CHENDe-hua1 ZHOU Meng1 SUNYan-qinga ZHENG Liang-liang (SchoolofComputerScience＆ Technology，DonghuaUniversity，Shanghai201620，China)1 (E-GovernmentManagementCenter，Pudong District，Shanghai200135，China) Abstract Asanimportantdatapre-processingoperation，graphsparsificationhasattractedwideattentionsfrom thear- ellofdatabase．Nowadaysthegraphdataisbecomingpopularandscale．Thusthispaperproposedanefficientparallel graphsparsificationalgorithm ，namelytheMR-GSparalgorithm．TheMR-GSparalgoritmh ispresentedbyreforming thetraditiDnalMinhashalgoritmh intoaparallelanddistributedalgorithm usingMapReduceframework，whichcanat- chiveefficientsparsificationonlarge-scalegraphdatainalargemachineclusterenvironment．ExperimentsONrealdata— setsshow thatthealgoritmh iSfeasibleandeffective． Keywords Graphsparsification，Minhsh，MapReduceframework，MR-GSparalgoritmh 在抽样数据上执行数据挖掘操作，从而在较短时间内获得近 1 引言 似的挖掘结果。因此，在图聚类应用中，通过对图数据进行点 许多现实世界中的复杂网络如蛋白质交互网络、社会网 或边抽样，即经过图的稀疏化处理得到稀疏图，然后在稀疏化 络、传感器和通讯网络、交通运能网络等都可以自然地建模为 之后的图上进行图聚类，这已成为提高图聚类分析效率的有 图结构。在这类图中，结点表示网络中的实体 ，边则表示实体 效方法。