brain of mat kelcey...

e10.5 revisiting community detection

March 30, 2010 at 08:42 PM | categories: Uncategorized

i've decided to switch back to some previous work i did on community detection in (social) graphs

the last chunk of code i wrote which tried to deal with weighted directed graphs was terribly, terribly, broken but it seems that simplifying to undirected graphs is giving me much saner results. yay!

here's an example of my work in progress generated from the new version of the code

consider the graph


and it's corresponding decomposition


the results are reasonable; the initial breaking of clusters [1,2,3,4,5,6] and [7,8,9,10,11,12] is the most obvious but some of the others are not as intuitive

[1,2,5] and [7,8,10] remain as unbreakable cliques though it's arbitrary that 11 was broken off from [7,8,10] instead of 10 (arbitrary but an artifact related to my shortest path calculation for the edge betweenness)

the idea of identifying the edge to remove using edge betweenness works well but it is often the case there are many edges with the same maximal betweeness and you have to choose only one. i think my current implementation of picking one is a bit naive and i'm not sure if i should move to a stochastic / monte carlo style approach or focus more on modularity maximisation