基于并行计算的高效图稀疏化处理算法-论文.pdf

《基于并行计算的高效图稀疏化处理算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第28卷第2期四川理工学院学报(自然科学版)Vo1．28No．2Q±旦生量!：!翌垡曼!!!!垒兰竺!!竖!苎型!：!兰!里2垒旦文章编号：1673-1549(2015)02-0045-07DOI：10．11863／j．suse．2015．02．11基于并行计算的高效图稀疏化处理算法李融(温州广播电视大学，浙江温州325000)摘要：针对目前的图聚类分析方法存在的不足，在分析研究MapReduce架构理论、最小哈希算法以及图聚类分析中的数据抽样和稀疏化处理机制的基础上，提出了一种基于并行计算的高效的图稀疏化处理算法。该方法以MapR

2、educe架构理论为基础，通过Minhash算法进行并行化分析，利用MapRe—duce框架结构对图聚类分析稀疏化操作过程中的多个任务进行了高效的推算分析与处理，并在Hadoop计算环境下，通过模拟实验对提出的高效图稀疏化处理算法的性能进行了测试。测试结果表明：基于并行计算的高效图稀疏化处理算法可行，能对图聚类数据信息进行快速稀疏化处理。关键词：MapReduce；Minhash；图聚类分析；数据抽样；并行计算中图分类号：TB115文献标志码：A出现，如何高效地进行图聚类分析与处理，以此来挖掘引言图数据中的潜在有效数据信息，已成为人

3、工智能、数据日益复杂的网络交互体系可以通过建模以图模型挖掘等领域的热点研究方向之一。的形式表示，如社交网络、通信网络、交通运输网络国内外研究人员对图聚类算法进行了广泛的研究，等]。在图模型中，每个结点表示对象实体，每条边表提出了很多的图聚类算法，包括经典聚类算法(如划分示对象实体之间的关联。例如，可以把社交网络体系以式聚类算法)、层次式图聚类算法、基于密度的图聚类算一个无向图模型的形式表示，图模型中每个结点表示一法、最小生成图树聚类算法等。个社交群体或一个个体，每条边表示两个社交群体之间数据抽样是图聚类分析与处理机制中的一种高或两个

4、个体之间的关联，这种关联可以是同事关系或朋效数据处理方式。数据抽样首先从整体数据集合中抽友关系等J。近几年，随着网络科学与信息化技术的不取局部样本，然后对样本数据进行数据挖掘、处理与分断发展以及新浪微博、微信等虚拟网络应用产品的不断析。数据抽样可以实现时间与挖掘处理结果的高性能推广，图数据信息的处理量呈逐年上升趋势，给图数据比以及提高图聚类分析与处理的有效性。在图聚类分的挖掘、分析及应用带来了极大的挑战。析与处理过程中，首先对图模型中的结点和边分别进行图聚类是图数据挖掘、分析及应用过程中可能会用数据抽样(图稀疏化处理)，然后对图稀疏

5、化处理的结果到的一个关键技术。图聚类通过将图模型中的每个结进行图聚类分析。点按照聚簇进行分类，可以提高同类别聚簇图结点对象作为图聚类分析与处理机制中较为重要的一个环实体的关联紧密性、降低不同类聚簇图结点对象实体的节，图稀疏化处理机制已被应用于多个研究方向。针关联紧密性。随着超大规模图数据信息与处理机制的对小规模、小区域范围的图模型数据信息，现有的图稀收稿日期：2015．02—14作者简介：李融(1977一)，男，浙江温州人，讲师，硕士，主要从事计算机应用与教育技术方面的研究，(E—mail)1697986428@qq．corn四川理

6、工学院学报(自然科学版)2015年4月疏化处理机制主要包含L-spar9]、k-最近邻图n叫等几种其中，Jaccard参数值是、两个数据集合的对比数值。方法。这些方法在对小规模、小区域范围的图模型数据从式(1)中可知，两个数据集合相似度越高，其Jaccard信息进行处理时，能够得到很好的处理效果，但是在对参数值就越大。然而在数据集合较大时，Jaccard参数值较大规模、较大区域范围的图模型数据信息进行处理和会受到交并集合的规模大小影响，其效率无法得到提应用于分布式集群计算环境时，处理效果比较差。升。随着图模型应用产品的不断发展和应用

7、规模的不Minhash算法就是依据Jaccard参数值的相关知识，断扩大，图模型的数据信息变得越来越复杂，依靠单一先利用Hash函数(以日表示)计算、数据集合的总的计算环境对图数据进行处理已不能满足数据分析与体元素数量，然后获取结果信息，即Minhash(A)与处理的需要。针对这种情况，能够通过与大规模计算机Minhash(B)：服务终端相关联来对大规模数据进行分析与处理的P，[minh。s(A)=mnhnsh(8)3={—∈宝斗(2)MapReduce并行计算理论框架得到了广泛应用。所以，在此算法中，其相似度问题则巧妙地变换成多个

8、哈希算法，是根据设定的哈希函数H(key)和处理冲数据集合的等值概率数学问题，从而改进了数据集合相突方法将一组关键字映像到一个有限的地址区间上，并似度计算效率。以关键字在地址区间中的像作为记录在表中的存储位1．2并行计算理论置，这种表