I have been looking for algorithms in Python to create clusters from pairs of data. The data structure is similar to the stackoverflow post: An algorithm to create clusters from data pairs in python, but now nodes have weights or distances on edges and each node is connected with any other nodes, like

[(id_1, id_2, 25),
 (id_1, id_3, 21),
 (id_1, id_4, 5),
 (id_2, id_3, 1),
 (id_2, id_4, 18.5),
 (id_3, id_4, 22)]

I wish to obtain the result like

[(id_1, id_4), (id_2, id_3)]

id_1 and id_4 (id_2 and id_3) are close, but there exist significant distances between the clusters. Thanks!


Try creating a graph with networkx. Then use the function spring_layout to get the (x, y) coordinates of each node, and then using these data apply the clustering algorithm in order to find 2-points clusters. Tell me if this is nearly what you were looking for.


(i,j,distance) gives you a sparse distance or similarity matrix.

You can use almost any clustering algorithm on this.

The obvious first thing to try would be hierarchical agglomerative clustering, as it can easily be implemented both for distances and for similarities.

In your case, the values seem to be distances, and HAC would merge the clusters exactly as desired: it merges the smallest values first.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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