Deleting loops in a weighted directed graph

Question

This is the next question about my other posts.

Size Limit Clustering Algorithm

I am working on a clustering algorithm. After some unfolding, I now have this set of points at which none of them are in their optimal cluster, but cannot be reassigned individually, since it will violate the restriction.

I am trying to use the graph structure to solve a problem, but have encountered several implementation problems.

I'm a newbie, please let me know if I'm wrong.

In response to @Kittsil

construct a directed graph with clusters as nodes, so that the edge (A, B) exists if the global solution is minimized by some point in A moving towards B. The search for cycles in this graph will allow you to find the potential (where the movement consists of the movement each vertex in the loop).

I revised the graph, adding weight as the sum of the number of points moving from A to B.

Here are some scenarios where I'm not sure how to decide at which point to reassign.

Scenario 1 . For the loop as shown below. There are two points that can be moved from A to B, and three from B to C. In this situation, which item should be selected for reassignment?

Scenario 2 . For the loop as shown below. Let all the weights of the edges be equal to 1. For a point in cluster A, it can be reassigned to either cluster B or D. In this case. How do I reassign?

Scenario 3 As in scenario 2. Let all the weights of the edges be equal to 1. In a larger cycle, there are two small cycles. A point in cluster A can be reassigned for both B and E, how can I decide, in this case reassignment?

Ideas for any scenario are welcome!

Also there are suggestions for the implementation of the algorithm, taking into account the above cases? Better yet with pseudo code. Thanks!

Answer 1

If the weight of the ribs is proportional to the benefit obtained by re-clustering the glasses, then a decent heuristic is to choose the cycle with the highest total weight. I think this applies to all three of your affairs: whenever you have a choice, choose the one that will do the very best.

---

Discussion:

The algorithm described in the Clustering Algorithm with Size Constraints is a greedy algorithm for finding a local minimum. Therefore, there is no guarantee that you will find the best solution no matter how you choose in these scenarios, and any choice will bring you closer to the local minimum.

Due to the connection with similar sorting problems with restrictions, my intuition is that the minimal problem would be NP-hard. If this is not the case, then there is a much better algorithm than the one I described earlier. However, this greedy algorithm seems to be a quick fix for a minimal problem.