基于哈希存储器的大图生成器.pdfVIP

专题 第 8 卷  第 11 期  2012 年 11 月 基于哈希存储器的大图生成器 1 2 李亚韬 　邵　斌 1香港科技大学 关键词 ：大数据　大图　哈希存储器 2微软亚洲研究院 绪论 个矩形 （初始为整个矩阵）。当这个矩形中包含多 现实世界中的大规模图 （简称大图）数据，例 于一个元素的时候，RMAT算法继续迭代，在每一 如网页链接拓扑和社交网络，规模都在十亿节点级 步迭代中将当前矩形等分成四个象限，并按照一个 别或以上。然而，获取真实大规模数据的代价是高 随机数与给定的四个参数 （分别对应选取四个象限 昂的。除了少数商业公司，大部分研究者无法获得 的概率）来缩小当前矩形到某个象限。由于每一次 真实的大图数据。一个具有能快速生成某种近似真 缩小矩形的长宽都会减半，每一次生成边的复杂度 实数据特性的大图生成器将对研究人员实现和验证 是O (l o g(V| |)) 。设四个象限的概率参数分别为p 1 、 大图算法提供巨大帮助。 p 、p 、p ，满足p p ，p p 便可得到符合幂律分 2 3 4 3 2 4 1 以前的研究工作专注于提出特定的生成算法， 布的图结构。 使得生成图具有某种特性 （例如拓扑结构与社交网 目前基于各种图生成模型，存在一些流行的图 络类似，度分布符合幂律 （power-law ）模型）。目 生成器系统，比如GTGraph[3] 、NetworkX[4] 、Graph- 前图研究中常用的生成器模型有Er dö s-R ényi 、BA Stream[5]和Gephi[6]等。GTGr aph支持流行的RMAT 和RMAT等。在Er dö s-Rényi模型[1] 中，任意两个节 模型，N et w or k X则可以支持多种图生成器模型。 2 点间存在边的概率为p 。因为有|E |=V| | p ，V 表示图 GraphStream侧重于小规模图的可视化，而Gephi则侧 · 的节点数，所以可以通过控制总边数|E |来控制p 。 重于图数据的交互探索。这些图生成系统都是单机 如果用邻接矩阵来表示一个图，那么实际上在该模 系统，无法胜任十亿和百亿节点规模大图的生成。 型下的一次生成相当于在邻接矩阵中随机挑选|E |个 本文作者设计了一种在分布式环境下具有良 元素。虽然该模型非常朴素，且不具有真实数据的 好扩放性的生成器系统，实现了大图的高速生成。 特性，但由于思想简单，容易在其基础上推导公式 在传统的生成器方案中，需要对生成的边表做排序 求解问题，所以该模型被广泛采用。R M A T模型[2] （通常是在磁盘上做外排序）。对海量边集进行排 是近来最为流行的图生成模型之一。它算法简单， 序的时间开销很大，用传统方法生成一张十亿节 并且生成图具有很多真实数据特性。RMAT模型生 点、百亿边的大图通常需要几十个小时。作者设计 成的图符合幂律分布，少量节点拥有大量边而绝大 的生成器系统的优点是回避了耗时的外排序过程， 多数节点的边数都很小。RMAT 图具有若干可调参 并且在分布式环境下实现了高效的多机并行生成。 数，根据参数的不同可以生成类似社交网络或网络 拓扑等类型的合成图。如果将图视为一个邻接矩 基于哈希的分布式存储器 阵，RMAT算法迭代地在该矩阵中