evan_tech

Previous Entry Share Next Entry
09:27 am, 26 Nov 03

more graphs

(Last time: I was thwarted because dot was redoing the graph layout.)
Last night I remembered I had a tool that could display dot files already: my sexchart grapher! Because it was made for bidirectional (though I can imagine a situation with unidirectional, I hope it never applies to anyone I know) links, it can't display directed graphs well. But it was nice to be able to reuse an old project, anyway.

The other part I needed was random graphs to test with. The standard random graph is n nodes, with links between any pair of nodes with probability p, but that isn't a very interesting graph. From a paper (How Do Networks Become Navigable?) I got from the researcher working on LJ data, I saw another model, from Jon Kleinberg: in d dimensions, n nodes, with links between any pair of nodes with probability proportional to l^(-α), where l is the d-dimensional distance between the nodes and α is another constant you choose (see also: simple discussion of α). For my purposes, that's just making the probability increase when nodes are near each other, so I chose 2 dimensions, randomly positioned my nodes in 2d, and then tweaked the numbers until it looks "right".

(As an aside, Kleinberg's model has a bunch of other interesting properties that I didn't use... I really ought to read all of his stuff now that I've gone to the trouble of finding his website. I actually saw him speak here a few years ago, and was impressed enough with his talk to go to the trouble of ripping a copy of it. I'd put it up for you but it looks like it's 100mb. It's funny now that I watch the video because I see people like harrchenone in the audience, and I think I didn't know him at the time.)

So now, some pictures. It's a shame the grapher is written in Ruby, because now I'd really like to try stuff like tweaking α and seeing what it looks like. I guess I could rewrite the graph generator in Ruby and then do it all in Ruby, but the whole point of this exercise was to better my OCaml-fu!

Source graph:


Shortest paths from node n1:


As you can see, n4 gets left out because its link is going the wrong way.