clustering connected nodes based on node attribute

Prakash Selvam 0
Viewed 39

I need to find n clusters such that the density of each cluster is above the threshold value of 50. I have 639 nodes, with average density assigned to the node attribute. Is there an algorithm to traverse through the nodes and merge nodes on attribute density so that I get n said clusters(should comprise connected nodes) with average density around and above the threshold value of 50. Each node can be connected to nodes with a connection to the said node.nx.connected_components(G) is 20. code snippet in python would be appreciated, as I'm a novice, with python and data science.

the image shows the nodes in blue and the connections in black

cluster-analysis graph-theory networkx python-3.x
1 Answers

The greedy algorithm goes like this:

SET maximum size of the clusters to 639 / n
ORDER nodes in descending density
LOOP
    Start new cluster
    Move node of greatest density to cluster from ordered list
    LOOP
       Calculate average density of cluster
       IF average > 50
           LOOP over nodes in order of increasing density
           IF node connected to cluster
               MOVE node into cluster
               break
       ELSE
           LOOP over nodes in order of decreasing density
           IF node connected to cluster
               MOVE node into cluster
               break
       IF cluster size == maximum
           BREAK
ravenspoint0
Related