LGP1SA分布式环境下基于模拟退火的大规模图划分算法.PDFVIP

电信 科 学 2016 年第 期 电信 科 学 2016 年第 2 期 研 究与开发 LGP-SA ：分布式环境下基于模拟退火的大规模 图划分算法 许金凤 ，董 一鸿 ，王诗 懿 ，何 贤芒 ，陈华辉 （宁波 大 学信 息科 学与 工程 学院 ，浙 江 宁波 315211） 摘 要 ：针 对 大 规 模 图数 据 的分 布 式 计 算 ，首 先 需 要 进 行 图划 分 。 当前 大 规 模 图划 分 方 法 采 用 顶 点 转 移 策 略来 减 少 分 区 间 的边 割 数 以降低 通 信 开 销 ，但 容 易 陷入 局 部 最 优 ，引入 模 拟 退 火 的方 法 进 行 顶 点 转 移 后 ，极 大 地 避 免 了局 部 最 优 的 陷 阱 ，也 极 大 地 防止 了顶 点 无 效 转 移 ，更 好 地 降低 了通 信 开 销 。 对 比实 验 显 示 ，本 算 法 划 分 大 规 模 图 的边 割 率 有 了极 大 的改 进 ，并 用 PageRank 算 法 验 证 了算 法 的有 效 性 和 可 行 性 。 关 键 词 ：图划 分 ；Giraph ；模 拟 退 火 ；大 规 模 图 ； BSP 中图分 类 号 ： 文献标 识码 ： TP391 A doi： 10.11959／j .issn.1000-080 1.20 16078 LGP-SA ： Graph partition algorithm based on simulated annealing in large-scale graph processing XU Jinfeng， DONG Yihong， WANG Shiyi， HE Xianmang， CHEN Huahui College of Information Science and Engineering， Ningbo University， Ningbo 315211， China Abstract： Distributed computing for large-scale graph data need to partition the graph firstly. The current methods of large-scale graph partitioning is to reduce the edge cut in order to lessen communication overhead by using vertex transfer strategies， but easily to fall into local optimum. Simulated annealing has a great probability to avoid the trap of local optimum and prevent vertices from invalid transfer which was introduced to transfer vertices. This method decreased communication overhead greatly. Comparative e