graph_partition.md

Graph partition

General

The graph partitioning problem asks for a division of a graph's node set into k equally sized blocks such that the number of edges that run between the blocks is minimized. The size of each block is a configurable parameter.

Application of the algorithm

Road network	Graphics process	Scocial Network

Graph partition is the first step to distribute processing graph data.

Ideal partition result

Basic Algorithm

• Kernighan Lin Algorithm

• Max Flow Min Cut

Solutions for Route network

• METIS

• PUNCH

• Inertial Flow

• KAHIP

Distribute Partition

• pregel

• Google - Affinity Clustering: Hierarchical Clustering at Scale

• Facebook - Balanced Label Propagation for Partitioning Massive Graphs

More information

• Graph Partitioning and Clustering in Theory and Practice by Christian Schulz from KIT