Graph partition

Graph partition is the problem of dividing the vertices of a graph into disjoint subsets (or partitions) such that some objective function — typically the number of edges crossing between subsets — is minimized. It is one of the foundational problems in graph theory and network science, with applications ranging from parallel computing to social network analysis. The problem generalizes graph bisection by relaxing the equal-size constraint and extends to k-way partitioning where the graph is divided into more than two subsets.

Spectral methods, using the eigenvectors of the graph Laplacian, provide one of the most successful approaches to graph partition. These methods solve a continuous relaxation of the discrete problem and round the solution to obtain a partition. More scalable approaches use multilevel partitioning, which coarsens the graph, partitions the coarse graph, and refines the result on the original graph.