# How to perform clustering of a large number of nodes?

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

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.

• Tried k-means with distance =$1\over W$? Mar 6 at 14:55
• @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!
– KGM
Mar 6 at 15:05
• Your first constraint is $\le$ rather than $=.$ Does that mean you are willing to leave some nodes not assigned to any cluster?
– prubin
Mar 6 at 16:25
• Mar 6 at 17:23
• For fast heuristics, search for "community detection" Mar 6 at 17:25

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


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

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.

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.

• MST can be used for clustering, but it doesn't respect the cardinality constraints ($\le 70$ nodes per cluster). Mar 8 at 17:34
• @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. Mar 8 at 17:37
• The number of clusters is also required to be $8$. Mar 8 at 17:38
• @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. Mar 8 at 17:42
• Yes, the OP meant $g\in\{1,\dots,G\}$ instead of $g\in\{1,\dots,N\}$, and I corrected it. Mar 8 at 18:19