# Can anybody tell me which implementation of min cut is used in Cluto? Thanks

Hi, everybody

I have an question about graph clustering algorithm used in Cluto.

In the manual, it says it first uses a nearest-neighbor graph(convert a graph in the format described in the manual into a more concise form), then it uses min-cut algorithm.

1)Does it means it used min-cut to cut the whole graph into two parts, and then cuts one of the two parts further using min-cut again, and so on?

2)Which algorithm is used to implement min-cut in Cluto?

algorithm based on "max-flow" or "a simple min cut algorithm"?

3)Is there any source code or any material or papers talking about each algorithm implemented in Cluto?

Thanks

Submitted by lilu29 on Sat, 2008-06-21 20:21

## RE: I have read all related

I have read all related papers posting on this site.

None of them talks about the graph clustering algorithm used in Cluto?

## RE: The graph partitioning

The graph partitioning algorithms implemented in Cluto are based on the multilevel partitioning algorithms in Metis. The clustering is computed via a recursive bisection procedure.