An algorithm to create clusters from data pairs in python

Question

I am looking for a smart algorithm or pythonic approach to create clusters from pairs of data.

The input data is structured like this:

[
 (productA,ProductB),
 (productB,ProductC),
 (productC,ProductD),
 (productA,ProductD),
 (productD,ProductB),
 (productC,ProductA),

 (productE,ProductF),
 (productF,ProductG),
 (productG,ProductH),
 (productG,ProductE),
]

and it should be clustered to:

[
(productA,productB,productC,productD),
(productE,productF,productG,productH)
]

How can this be achieved? (The order of the products within the two clusters does not matter)

Any ideas are greatly appreciated!

A cluster is the transitive closure over all products linked via some (directional) pair? Is the relation symmetric? — dhke

unutbu unutbu · Accepted Answer · 2016-01-26T19:10:43

Using networkx, you could build a graph and find the connected components:

import networkx as nx

data = [
 ('productA','productB'),
 ('productB','productC'),
 ('productC','productD'),
 ('productA','productD'),
 ('productD','productB'),
 ('productC','productA'),
 ('productE','productF'),
 ('productF','productG'),
 ('productG','productH'),
 ('productG','productE'),
]

G = nx.Graph()
G.add_edges_from(data)
for connected_component in nx.connected_components(G):
    print(connected_component)

yields

['productG', 'productF', 'productE', 'productH']
['productD', 'productC', 'productB', 'productA']

An algorithm to create clusters from data pairs in python

2 Answers