last night i applied my network decomposition algorithm to a graph of some of the people near me in twitter.
first i build a friend graph for 100 people ‘around’ me (taken from a crawl i did last year). by ‘friend’ i mean that if alice follows bob then bob also follows alice.
here the graph, some things to note though; it was an unfinished crawl (can a crawl of twitter EVER be finished) and was done october last year so is a bit out of date.
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
