图分割 Graph Partition 学习笔记1

前言

  最近在学习图论划分的方法，碰巧搜索到了这个算是对我而言全新的一个体系，在这里将逐步记载自己的学习资料和进度，希望和大家一起探讨~

一、graph-partition是什么？

  图分割是将一个大图均匀的分成一系列的子图去适应分布式应用，每个子图存储在一台机器上，子图之间可以并行化执行，如果当前子图需要其他子图的信息就需要通讯开销，而图分割的质量影响着每台机器存储代价和机器之间通讯代价。

  粗略地按照分割的内存开销大小分类，可以分为离线offline和流式streaming两类分割算法。offline是将整个图数据一次性载入内存中然后根据图的结构进行切分；streaming是按批次读取图数据，实时的将图的边或者结点分配到指定的子图中。对于大规模图数据来说，单机的内存无法满足分割算法的需求，这个时候流式分割显得尤为重要。

二、具体分类

  按照对图数据的切分方式分类，可以分为边分区/点分割（vertex-partition or edge-cut）和点分区/边分割（edge-partition or vertex-cut）有几个定义要注意下：

• edge-cut（边分割）= vertex-partition（点分区）
• vertex-cut（点分割）= edge-partition（边分区）

  如下图所示，点分区/边分割是将图的节点分配到各个子图中，维持结点之间子图的完整性，这个时候可能造成某些节点之间的边被切掉(edge-cut)；同理边分区/点分割是将图的边分配到各个子图中，每组分配的边构成子图，这个时候造成某些结点的冗余（vertex-cut）。对于服从幂律分布power-law的图数据，某些结点的边可能特别多，如果执行点分割会造成大量边的缺失以及边的负载不均匀；而边分割可以处理这类问题。

三、graph-partition的意义

• 将一个图划分为若干子图以便在分布式系统中运行
• 图划分的优化目标包括两项：负载均衡和最小割 (cut)，二者都是为了提高在分布式系统中运算的性能。其中，负载均衡是为了使分布式系统中的多台计算机有相近的任务负荷，避免少数计算机负载过高。最小割则是为了减少计算机之间的通信代价。同时优化两个目标目前已知是NP困难问题。

参考链接

  图分割Graph Partitioning技术总结
  图流划分算法综述
  【知识】如何区分图论中的点分割和边分割