Balanced Graph Communities With Node Weights

Question

I'm looking for where best to start on the following problem.

I have a graph of N nodes and each node as a weight. I need to group all nodes into X groups such that the sum of weights in each group are approximately even and that each group is a connected component of the original graph.

After some simple searching I came across the lukes partitioning algorithm implemented in python.

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.community.lukes.lukes_partitioning.html#networkx.algorithms.community.lukes.lukes_partitioning

This is approximately what I am looking for but performance feels slow for the size of the graph I am working with.

Do you have any potentially better ideas that worked for you?

Answer 1

Thank so much for the pastebin link, I managed to write my own code as well. Its not nearly as neat and efficient as Stevens.

https://pastebin.com/a21v2Nxz

I still think you are miss understanding my problems with the algorithm

I entirely believe it will colour each node without stopping

My main issue is its not guaranteed or even likely the colouring will be balanced.

Imagine a line graph with uniform weightage, and your random choice of starting classes is the first k nodes on the line graph.

Hopefully I am correct in saying that the only colour capable of growing in size in that situation is the which ever colour is the final colour (i.e. the kth colour on the line graph)

A situation like the simple graph below, where there are 4 coulours and n nodes in the line graph.

red - blue - green - yellow - null - null - ... - null

The solution to this problem I figured was a montecarlo like approach. The algorithm runs fast enough that you can do it many times, and choose which one is the best of all the attempts. That's the main addition to my code

Answer 2

If the graph is a complete graph, this problem reduces to the 'multiway partition problem', which is NP-hard. If G is a tree, the problem can probably be solved efficiently with dynamic programming.

In the general case, I believe that making the partitions roughly equal in sum is harder than having all partition classes to be connected.

Since the order of your graph is very large, I would suggest a greedy approximation algorithm (explained with the terminology of 'colorings' in stead of partitions):

• Start by choosing $X$ vertices at random. These are the initial color-classes.

• As long as there are uncolored vertices, color a new vertex that produces the minimal-weight color class. That is: among all uncolored vertices $v$ that are adjacent to a colored vertex: consider coloring $v$ with a color of any of its neighbors. Choose this $v$ and the color in such a way that the resulting color class has minimal weight among all considered choices.

  Or more formally; for each uncolored node consider the function: $f(v) = \min_{C_i \sim v}{weight(C_i) + weight(v)}$ Then choose $v$ with minimal $f$ and color it in the appropriate color.

Implementing this naively gives an $O(n^3)$ algorithm which should be doable for your $10000$ nodes. But with the appropriate data structures, better time complexities are possible.

Afterwards you could run a meta-heuristic to improve the solution locally, if you want to. I would suggest to keep the connectedness in tact at all time. That is: choose to recolor vertices on the boundary between color classes.