[petsc-users] Finding mincut after k-means clustering

[Eda Oktay]

Hello everyone,

I am solving a graph partitioning problem. I found an unnormalized
Laplacian matrix of a graph, then since I have 4 processes and I am
using spectral partitioning algorithm, I calculated 4 eigenvectors
corresponding to 4 smallest eigenvalues of this Laplacian matrix.

Then, since I am using the k-means clustering algorithm, I formed a
matrix U whose columns are these eigenvectors. After that, I clustered
each row of U according to the k-means algorithm. Now, I have
different row vectors at different processes, as I want.

In other words, my eigenvectors have 72 elements. So, right now, I
have 72 different row vectors with 4 elements. Those 72 row vectors
were clustered but not in a serial order. For instance, the 4th vector
is in the first process and the 5th one is in the 4th process.

As the last part of my work, I want to find mincut of this
partitioning but I couldn't understand how to do it. If I didn't use
k-means algorithm, I would use MatPartitioningApply but now, since I
clustered row vectors of U according to the index set I obtained from
k-means algorithm, I don't know how to use partitioning routines.
Should I form another matrix by reordering these vectors and then
partition? But then, how can I be sure the vectors stay in the same
process as before? Besides MatPartitioning routines, is there any
routine I can use for this? I thought MatColoring can work but I guess
it won't.

Thanks a lot!

Eda