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

[Jed Brown]

Are you just looking for metrics related to the partition you've
created, or are you wanting to redistribute some other data according to
the partition?

Eda Oktay <eda.oktay at metu.edu.tr> writes:

> 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