Research on Dynamic Graph Partitioning Algorithms: A Survey
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Graph partitioning is the primary work of large-scale distributed graph processing, which plays a fundamental role in storage, query, processing, and mining of graph applications. Since graph data in the real world are always dynamic, the research of dynamic graph partitioning is a hot topic. This study systematically introduces the current algorithms for dynamic graph partitioning, which including streaming graph partitioning algorithm, incremental graph partitioning algorithm, and graph repartitioning algorithm. Firstly, the study introduces three different partitioning strategies, two different dynamic sources of graph and dynamic graph partitioning problem. Then, three different streaming graph partitioning algorithms are introduced, including hash algorithm, neighbor distribution-based algorithm, and novel algorithm. Secondly, two different incremental graph partitioning algorithms, single element incremental graph partitioning, and batch incremental graph partitioning are introduced. Thirdly, the repartitioning algorithm for graph structure and the repartitioning algorithm for graph computation are introduced, respectively. Finally, based on the analysis and comparison of the existing methods, the main challenges of dynamic graph partitioning are summarized and the corresponding research problems are proposed.

    Reference
    Related
    Cited by
Get Citation

李贺,刘延娜,袁航,杨舒琪,韵晋鹏,乔少杰,黄健斌,崔江涛.动态图划分算法研究综述.软件学报,2023,34(2):539-564

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:December 11,2021
  • Revised:May 09,2022
  • Adopted:
  • Online: July 22,2022
  • Published: February 06,2023
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063