How to sample connected $K$-partitions of a graph

Marina Meila

A connected undirected graph $G=(V,E)$ is given. This paper presents an algorithm that samples (non-uniformly) a $K$ partition $U_1,\dots U_K$ of the graph nodes $V$, such that th…