1
$\begingroup$

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.enter image description here

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.

$\endgroup$
8
  • $\begingroup$ Tried k-means with distance =$1\over W$? $\endgroup$
    – Sutanu
    Mar 6 at 14:55
  • $\begingroup$ @Sutanu in my case this relation does not hold true for al the pairs. Also, k-means is kind of random, different runs give different clustering results! $\endgroup$
    – KGM
    Mar 6 at 15:05
  • $\begingroup$ Your first constraint is $\le$ rather than $=.$ Does that mean you are willing to leave some nodes not assigned to any cluster? $\endgroup$
    – prubin
    Mar 6 at 16:25
  • $\begingroup$ Related: or.stackexchange.com/questions/6428/… $\endgroup$
    – RobPratt
    Mar 6 at 17:23
  • $\begingroup$ For fast heuristics, search for "community detection" $\endgroup$
    – RobPratt
    Mar 6 at 17:25

4 Answers 4

1
$\begingroup$

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)
$\endgroup$
1
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ MST can be used for clustering, but it doesn't respect the cardinality constraints ($\le 70$ nodes per cluster). $\endgroup$
    – RobPratt
    Mar 8 at 17:34
  • $\begingroup$ @RobPratt Well, in the worst case, one could satisfy the cardinality constraint also by removing all edges -- you would end up with singleton clusters. So, in this case, (since it is anyway only a heuristic solution), the OP should keep removing edges up until the time when cardinality constraint is met. $\endgroup$
    – Tryer
    Mar 8 at 17:37
  • 1
    $\begingroup$ The number of clusters is also required to be $8$. $\endgroup$
    – RobPratt
    Mar 8 at 17:38
  • $\begingroup$ @RobPratt Ah yes, it would not work in such case. You are correct in that situation. The OP, as it stands now, does not fully clarify the relationship between g and G. Indeed, purely by looking at the math programming model where G does not feature, one could interpret it as allowing the number of clusters to be endogenously determined. $\endgroup$
    – Tryer
    Mar 8 at 17:42
  • $\begingroup$ Yes, the OP meant $g\in\{1,\dots,G\}$ instead of $g\in\{1,\dots,N\}$, and I corrected it. $\endgroup$
    – RobPratt
    Mar 8 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.