基于局部迭代的MapReduce模型的图结点的权威值计算方法

摘要

本发明提供一种基于局部迭代的MapReduce模型的图结点的权威值计算方法，包括：数据预处理与子图划分，采取随机的划分方式和基于社团结构的划分方式来进行子图的划分；迭代执行MapReduce任务进行PageRank计算，Map阶段对各个子图进行独立的基于内存的PageRank计算，Reduce阶段reduce函数将各个子图产生的新的权威值按照结点ID进行归约求和，得到最终的结点的权威值；算法收敛检测。本方法既保留了内存算法的高效性，又得益于MapReduce处理海量数据的可扩展性，高可用性和容错性。

主权项

一种基于局部迭代的MapReduce模型的图结点的权威值计算方法，其特征在于，包括下述步骤：步骤a，数据预处理与子图划分，采取随机的划分方式和基于社团结构的划分方式来进行子图的划分；步骤b，迭代执行MapReduce任务进行PageRank计算，Map阶段对各个子图进行独立的基于内存的PageRank计算，Reduce阶段reduce函数将各个子图产生的新的权威值按照结点ID进行归约求和，得到最终的结点的权威值；步骤c，算法收敛检测，当数据集中的超过给定阈值的结点的权威值不再发生变化时，即算法收敛。