图分割理论 (Graph Partitioning)
定义与分类
粗略地按照分割的内存开销大小分类，可以分为离线(offline)和流式(streaming)两类分割算法。
- Offline将整个图数据一次性载入内存中然后根据图的结构进行切分
- Streaming 按批次读取图数据，实时地将图的边或结点分配到子图
按照分割方式可以分为点分割(edge-cut/vertex partition)和边分割(vertex-cut/edge partition)。
- Edge-cut后所有子图节点总数和原图节点数量相同，被剪掉的边不会出现在任何子图中
- Vertex-cut后被剪的节点会出现在所有与其相连的边所在的子图中，上图的Vertex-cut示例中间被剪节点出现在3个子图中
目标与约束
图分割的两个主要目标是：负载均衡(load balancing)和最小化切边或切点(minimum cuts). 负载均衡一般作为约束表述，最小化切边或切点是需要最优化的对象。
Edge-Cut/Vertex Partition
将所有的点集$V$分割为互不相交的k个子点集$\{V_1, V_2, \cdots,V_k\}$，约束条件：
$$ \max_{i\in[i,k]}|V_i|\leq{(1+\alpha)|V_i|\over k} $$
参数$\alpha$控制平衡率。
Vertex-Cut/Edge Partition
将所有的点集$E$分割为互不相交的k个子点集$\{E_1, E_2, \cdots,E_k\}$，约束条件：
$$ \max_{i\in[i,k]}|E_i|\leq{(1+\alpha)|E_i|\over k} $$