View source for 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|graph theory]] and [[Network science|network science]], with applications ranging from parallel computing to social network analysis. The problem generalizes '''[[Graph bisection|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 [[Laplacian matrix|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|multilevel partitioning]]''', which coarsens the graph, partitions the coarse graph, and refines the result on the original graph.

[[Category:Mathematics]]
[[Category:Systems]]