...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Knowledge-Based Systems >A feasible graph partition framework for parallel computing of big graph
【24h】

A feasible graph partition framework for parallel computing of big graph

机译：大图并行计算的可行图分区框架

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

With the emerging of large scale complex networks, graph computation, such as community detection, meets new technology challenges of extremely large computational cost. In order to deal with these challenges, the parallelism is becoming necessary. Graph partition is a fundamental problem of parallel computing for big graph data. The challenges of graph partition include large numbers of communications between partitions, extreme replication of vertices, and unbalanced partition. In this paper, we propose a feasible graph partition framework for parallel computing of big graph. The framework is based on an objective optimization problem to reduce the bandwidth, memory and storage cost on condition that the load balance could be guaranteed. In this framework, three greedy graph partition algorithms are proposed. By running the algorithms on the different kinds of graphs, including real-world graphs and synthetic graphs, the experimental results show that our algorithms surpass the state of the art heuristic algorithms. For example, running time is reduced more than 21.56% and the communication cost is decreased by more than 17.90% for weighted graph. The adequate experiments verify that our algorithms are capable of solving the problem of graph partition with different needs. (C) 2017 Elsevier B.V. All rights reserved.
机译：随着大规模复杂网络的兴起，诸如社区检测之类的图形计算面临着巨大的计算成本的新技术挑战。为了应对这些挑战，并行性变得很有必要。图分区是大图数据并行计算的基本问题。图分区的挑战包括分区之间的大量通信，顶点的极端复制以及不平衡的分区。本文提出了一种可行的大图并行计算图分区框架。该框架基于客观的优化问题，可以在保证负载平衡的情况下减少带宽，内存和存储成本。在此框架下，提出了三种贪婪图划分算法。通过在不同类型的图形（包括真实图形和合成图形）上运行算法，实验结果表明，我们的算法超越了最新的启发式算法。例如，加权图的运行时间减少了21.56％以上，通信成本减少了17.90％以上。充分的实验验证了我们的算法能够解决具有不同需求的图分区问题。 （C）2017 Elsevier B.V.保留所有权利。

著录项

  • 来源
    《Knowledge-Based Systems》 |2017年第15期|228-239|共12页
  • 作者

    Liu X.; Zhou Y.; Guan X.; Shen C.;

  • 作者单位

    Xi An Jiao Tong Univ, Minist Educ, Key Lab Intelligent Networks & Network Secur, 28 Xianning West Rd, Xian 710049, Shaanxi, Peoples R China;

    Xi An Jiao Tong Univ, Minist Educ, Key Lab Intelligent Networks & Network Secur, 28 Xianning West Rd, Xian 710049, Shaanxi, Peoples R China;

    Xi An Jiao Tong Univ, Minist Educ, Key Lab Intelligent Networks & Network Secur, 28 Xianning West Rd, Xian 710049, Shaanxi, Peoples R China|Tsinghua Univ, Ctr Intelligent & Networked Syst, 28 Xianning West Rd, Xian 710049, Shaanxi, Peoples R China|Tsinghua Univ, TNLIST Lab, 28 Xianning West Rd, Xian 710049, Shaanxi, Peoples R China;

    Xi An Jiao Tong Univ, Minist Educ, Key Lab Intelligent Networks & Network Secur, 28 Xianning West Rd, Xian 710049, Shaanxi, Peoples R China;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    Graph partition; Parallelism; Big graph; Objective optimization; Greedy algorithm;

    机译：图分区并行大型图目标优化贪心算法;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号