Evan Martin (evan) wrote in evan_tech,
Evan Martin

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.

  • blog moved

    As described elsewhere, I've quit LiveJournal. If you're interested in my continuing posts, you should look at one of these (each contains feed…

  • dremel

    They published a paper on Dremel, my favorite previously-unpublished tool from the Google toolchest. Greg Linden discusses it: "[...] it is capable…

  • treemaps

    I finally wrote up my recent adventures in treemapping, complete with nifty clickable visualizations.

  • Post a new comment


    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.