3

i'm studying a method to cluster similar topic represented in a graph like this:

The result must be:

[0] = 1,2,4
[1] = 3

I tried Markov Cluster Algorithm but i haven't good result.

Now i'm trying HCS cluster, but i have a doubt about Minimum cut which is only a probabilistic method.

In your experience is HCS the right algorithm to cluster a graph? A good and simple example is welcome

Thanks!

Stefano Vet
  • 131
  • 1
  • 1
    Are you looking for that particular triangle [*motif*](https://en.wikipedia.org/wiki/Network_motif), or perhaps finding [*strongly connected components*](https://en.wikipedia.org/wiki/Strongly_connected_component)? Or maybe even more general [graph clustering algorithm](http://stats.stackexchange.com/a/140129/1036)? – Andy W Sep 16 '15 at 12:37
  • @AndyW i think a general graph clustering. I'm trying to cluster similar topic. I've tried Markov algorithm but from a matrix 0,1,1,1 - 1,0,0,4 - 1,0,0,0 - 1,1,0,0 the result is only one cluster 1,2,3,4. The right result must be 1,2,4 - 1. HCS have the problem of Minimum cut which is only probabilistic. – Stefano Vet Sep 16 '15 at 13:06
  • 1
    Your question is unanswerable as it is. You've presented a single extremely simple example without describing what the generic trait is that you desire of a clustering. What is wrong with the clustering 1,2,3,4? The fact that the induced subgraph has diameter 2? The fact that it is not completely connected but does contain a completely connected subgraph? What is it that you expect of the resulting clustering? – micans Sep 16 '15 at 16:14
  • @micans sorry for the lack of explanation. I try to get a result based on the frequency of edge between vertex. Vertex 1,2,4 are more connected than vertex 1 and i suppose that are 2 distinct cluster 1,2,4 and 3. A matrix like 0,1,1,1,0,0 - 1,0,0,1,0,0 - 1,0,0,0,1,1 - 1,1,0,0,0,1 - 0,0,1,0,0,1 - 0,0,1,0,1,0 return [0]= 1,2,4 - [1]= 3,5,6. Thanks for your help – Stefano Vet Sep 16 '15 at 17:01
  • I think your example is way too simplistic to base your choice of clustering algorithm on. Really, hugely overly simplistic. That said, if you want some criterion like 'edge density' to be central to your notion of clustering, have a look at DBSCAN. Did I mention that your example is too simple to base your choice on? – micans Sep 17 '15 at 10:19
  • @micans try to explain the matter, starting from the use of this algorithm. I measures the cosine similarity between topic. Now i know that topic 3 i similar to 1, topic 1 is similar to 2 and 4, topic 2 is similar to 1 and 4. Vertex 3 is not highly connected with other vertex then i supposed thats is another cluster or only noise. For connected i mean directly connected or indirectly connected. This algorithm must work with thousand of vertex but also with 4 vertex. I hope I explained myself and thanks for your valuable tips. – Stefano Vet Sep 17 '15 at 11:37

0 Answers0