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
since the twitter api is rate limited it’s quite slow to crawl twitter and after a most of a week i’ve still only managed to get info on 8,000 users. i probably should subscribe to get a 20,000 an hr limit instead of the 150 i’m on now. i’ll just let it chug along in the background of my pvr.
while the crawl has been going on i’ve been trying some things on the data to decide what to do with it.
i’ve managed to write a version of pagerank using pig which has been very interesting. (for those who haven’t seen it before pig is a query language that sits on top of hadoop’s mapreduce). my initial feel for pig is that it’s pretty awesome. it was much quicker to write this script than to write the statistically improbable phrases. in fact i’m reinspired to have another crack at the sip stuff using pig. my final result wasn’t great for the performance of hadoop and after some great feedback on the hadoop mailing list i’ve got a number of other things to try including writing my joins in pig.
anyways, here’s my pagerank in pig
let’s consider an example of the crawl order for tgraph…
we seed our frontier with ‘a’ and bootstrap cost of 0.
fetching the info for ‘a’ shows 2 outedges to ‘b’ and ‘c’, from our cost formula these all have cost 0 + 1 + Log10(2+1) = 1.6
our frontier becomes [ {b,1.6}, {c,1.6} ]
next is ‘b’ and see it has an outdegree of 3, these nodes, b1 -> b3, all have a cost of 1.6 + 1 + Log10(3+1) = 3.2
our frontier becomes [ {c,1.6}, {b1,3.2}, {b2,3.2}, {b3,3.2} ]
next is ‘c’ with an outdegree of 15. these 15 nodes, c1 -> c15, have cost 1.6 + 1 + Log10(16) = 3.8
our frontier is now [ {b1,3.2}, {b2,3.2}, {b3,3.2}, {c1,3.8} ... {c15,3.8} ]
we would then continue with the ‘b’ nodes before the ‘c’ ones
note that this cost system is more than just an ordering, it allows an element at depth n+1 to be checked an element at depth n, if the cost of the latter is high enough.
our first goal is to get some data and the twitter api makes getting the data trivial. i’m focused mainly on the friends stuff but because it only gives user ids i’ll also get the user info so i can put names to ids.
a depth first crawl makes no sense for this one experiment, we’re unlikely to get the entire graph and are more interested in following edges “close” to me. instead we’ll use a breadth first search.
since any call to twitter is expensive (in time that is, they rate limit their api calls) instead of a plain vanilla breadth first we’ll introduce a cost component to elements on the frontier so help decide what to grab next. this is especially important for a graph like twitter where the outdegree of a node is often in the hundreds. it turns the crawl into something that is not strictly depth first but it works out.
to explain the cost component consider the expected connectivity of nodes in the twitter friend graph. most nodes have an outdegree of the order 20-200. occasionally you see much larger (in the 1000’s) or much smaller (under 10).
we might, naively perhaps, say that having a large outdegree means the person is a bit less strict with her following criteria and that some of them are not really that important to her. if this is the case we should focus a little more on getting nodes with smaller outdegree.
the formula i’ve come up with is to not consider the depth but instead add 1 + Log10(1+the outdegree of the previous node). in this way we penalise large outdegress, but not by a huge amount. we always add 1 to counter the cases where there are no edges leaving a node.
so e9 sip is on hold for a bit while i kick off e10 tgraph. was looking for another problem to try hadoop with and came across a classic graph one, pagerank. a well understood algorithm like page rank will be a great chance to try pig, the query language that sits on top of hadoop mapreduce.
so we need a graph to work on. my first thoughts were using one of the wikipedia linkage dumps but it feels a bit sterile. instead it’s a good excuse to do a little crawl of the following graph of twitter.
this will also be a chance to try to document a project via a blog. skorks‘ incessant blog rambling has convinced me to give it a go.
