Run
Uniformly random: cut weight (expected 0.500)
Our algorithm: cut weight (expected 0.641)
Shearer's algorithm: cut weight (expected 0.594)
Wrong threshold: cut weight (expected 0.359)
In these illustrations, the two sides of the cut are indicated with two different colours. Coloured edges connect two nodes of the same colour. Missing edges are cut edges. The sparser the graph looks, the better the cut is.