How to perform clustering of a large number of nodes?

Question

I have a clustering problem with around 400-500 nodes. The edge between any two nodes has a weight (between 0 and 1, 0: can be considered as there is no edge/connection between these two nodes) as shown in the figure. I haven’t drawn all the edges so as not to make the figure messy. Generally, the edge between the nodes that are far away from each other has low weight.

I need to perform clustering of these nodes. Lets say we want to put the nodes in 7-8 clusters/groups.

The objective is that the sum-weight in each cluster should be maximized. This may also generate clusters where the number of edges connecting two clusters is low.

Problem Statement:

Let $N=500$, $G=8$ and maximum cluster/group size is 70.

Let

binary decision variable $x_{i,g}$ indicate whether node $i\in\{1,\dots,N\}$ appears in group $g\in\{1,\dots,G\}$,

binary decision variable $y_{i,j,g}$ indicate whether edge $(i,j)$ appears in group $g$.

We want to maximize $$\sum_{i<j}\sum_g w_{i,j} y_{i,j,g}$$ subject to \begin{align} \sum_g x_{i,g} &= 1 &&\text{for all $i$} \tag1 \\ \sum_i x_{i,g} &\le 70 &&\text{for all $g$} \\ y_{i,j,g} &\le x_{i,g} &&\text{for all $i<j$ and all $g$} \\ y_{i,j,g} &\le x_{j,g} &&\text{for all $i<j$ and all $g$} \\ \end{align}

As we can see this a binary integer programming problem and has large number of optimization variable. Difficult to solve. Also I cannot afford a solver.

I prefer a less-complex solution.

Answer 1

Here's a simple hill-climbing approximate solver in Python which seems to work quite well:

import numpy as np

def cluster(weights, n_groups, max_size):
    n = weights.shape[0]
    assert n_groups * max_size >= n
    group_weights = np.zeros((n, n_groups))
    groups = np.empty(n, dtype=int)
    group_sizes = np.zeros(n_groups, dtype=int)
    idxs = np.arange(n)
    np.random.shuffle(idxs)
    score = 0
    for i in idxs:
        g = i % n_groups
        groups[i] = g
        group_sizes[g] += 1
        score += group_weights[i,g]
        group_weights[:,g] += weights[i]
    while True:
        #Reassignment phase
        changed = False
        for i in idxs:
            g = groups[i]
            w = np.copy(group_weights[i])
            w[group_sizes == max_size] = -1
            h = np.argmax(w)
            ds = group_weights[i,h] - group_weights[i,g]
            if ds <= 1e-16:
                continue
            changed = True
            groups[i] = h
            group_sizes[g] -= 1
            group_sizes[h] += 1
            score += ds
            group_weights[:,g] -= weights[i]
            group_weights[:,h] += weights[i]
        #Swapping phase
        for i in range(n):
            for j in range(n):
                if j == i:
                    continue
                g = groups[i]
                h = groups[j]
                ds = (group_weights[i,h] - group_weights[i,g]) + (group_weights[j,g] - group_weights[j,h]) - 2 * weights[i,j]
                if ds <= 1e-16:
                    continue
                changed = True
                groups[i] = h
                groups[j] = g
                score += ds
                dw = weights[j] - weights[i]
                group_weights[:,g] += dw
                group_weights[:,h] -= dw
        if not changed:
            break
    return groups, score

if __name__ == "__main__":
    np.random.seed(0)

    N = 500
    max_size = 70
    n_groups = 8
    weights = np.random.uniform(0., 1., (N, N))
    weights = np.tril(weights, -1) + np.triu(weights.T, 1)

    groups, score = cluster(weights, n_groups, max_size)

    print(groups)
    print(score)

Answer 2

You can apply a genetic algorithm to the problem, although (a) I'm not sure it would be considered "less-complex" and (b) it definitely would have a random component, with different runs likely producing different clusters. You would want to use a GA library, but fortunately there are high-quality open-source libraries for most languages. I have a demo coded as an R notebook (using the "GA" R library).

Answer 3

This is the graph partitioning problem. In your formulation, you are trying to maximize the weight of edges that are inside a cluster, instead of minimizing the weight of edges between clusters, but both are equivalent.

There are very good heuristics, some of which are explained on the Wikipedia page. And very good solvers based on these heuristics.

I suggest either Metis or Kahypar. Both are free software and have bindings for multiple languages.

Answer 4

If you would like to maximize intra-cluster weight, firstly, subtract each edge weight from 1. On the resulting graph, solve a Minimum Spanning Tree (MST). If you would like 2 clusters, remove the costliest edge in the MST solution. If you would like 3 clusters, remove the costliest and next costliest edge in the MST solution...If you would like m clusters, remove the m-1 costliest edges in the MST solution. This is a heuristic and relatively easy to implement solution to your problem.