modularity based clustering

[Mahadev Dovre Wudali]

Aapo/Danny,

Do you have any ideas on implementing a hierarchical graph clustering program a little more complex than the current communitydetection example to structure massive graphs into an hierarchy based on modularity (for example the one implemented by Gephi)?

Thanks

Mahadev

[Aapo Kyrola]

Hi Mahadev,

I am not well versed in community detection algorithms, could you point me to the algorithm description?

I recently heard Jure Leskovec's talk about their new community detection algorithms (NIPS 2012). Based on the talk, I think they would be easy to implement in GraphChi.

Aapo

--
You received this message because you are subscribed to the Google Groups "graphchi-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to graphchi-discu...@googlegroups.com.
To post to this group, send email to graphchi...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/graphchi-discuss/c103446c-5781-41d5-9968-d8acd44b3ebe%40googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Aapo Kyrola
Ph.D. student, http://www.cs.cmu.edu/~akyrola

GraphChi: Big Data - small machine: http://graphchi.org

twitter: @kyrpov

[Mahadev Dovre Wudali]

Aapo,

The Gephi algorithm is described at http://arxiv.org/pdf/0803.0476v2

The other one that I think is very interesting and looks like it can break up a very large connected graph using modularity as a measure of connectivity. It is described in  http://studiy.tu-cottbus.de/~clustering/start

Thaks for your response.

Mahadev

[Aapo Kyrola]

Hi,

I had a look at the Gephi algorithm, and I think it would be fairly easy to implement in GraphChi:

1) for the first phase, you need to keep in memory the current edge weight totals for each community and modify

them accordingly when a vertex is moved to a new community.  Thus, if you have enough memory (you need O(V) as the number of communities is initially one per vertex), you should be fine. Typically the number of vertices is much less than the number of edges, so you should be fine even on just a laptop. Good way is to manage the community values is to have a std::vector<double> as a field in the graphchiprogram-object.

2) The second phase is a graph contraction, where the new graph has each community contracted into one vertex. This is nowadays fairly easy to do with GraphChi, have a look here: https://github.com/GraphChi/graphchi-cpp/wiki/Graph-Contraction-Algorithms

Aapo

To view this discussion on the web visit https://groups.google.com/d/msgid/graphchi-discuss/0a472d19-0fd0-4379-b5fd-c268d8353050%40googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.