/Highly-Connected-Subgraphs-Clustering-HCS

Primary LanguagePython

Highly Connected Subgraphs (HCS)

Python implementation of Hartuv, Erez, and Ron Shamir. "A clustering algorithm based on graph connectivity." Information processing letters 76.4-6 (2000): 175-181.

Based on NetworkX and Numpy

Usage:

It provides the sample graph which is used in the publication. It can be created by calling:

G = hcs.create_example_graph()

alt text

Another easy way to get your graph is by passing the adjacency matrix to NetworkX

A = np.eye(4)
G = nx.convert_matrix.from_numpy_array(A)

alt text

The NetworkX graph can be clustered. There are two functions:

  • HCS(G): should be called if you want to get NetworkX graph that is clustered into the sub-graphs found by HCS.
  • labelled_HCS(G): should be called if you are just interested in the cluster labels. It returns a list with the cluster assignment for each vertex in G.

The clustered example graph looks like this:

alt text

And the labels are:

array([1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3], dtype=uint16)