Sunday, April 3, 2011

The Simulations! -1

<Apr 3 2011 10:51 am> Starting with Random Graphs - the only property I wish to make interactive that these in these graphs - if you choose any pairs of nodes at random, there exists a short path between them with high probability. This means that all I need to do is to generate a huge random graph and show that there indeed exists short paths between arbitrarily chosen vertices. I would have loved to make these take inputs - but right now, I'm hard coding the values.

So, on a graph with 100 nodes : -
I'll consider 20 pairs of nodes and simulate the paths between them. In the original python script itself I can print out a table which I can use with gnuplot to generate a graph on the percentage of nodes having short paths. Now these values that I have mentioned are only representational - I'll have to tune these to get a good visualisation. And by "short", I mean path length is poly-logarithmic in the size of the network.

I am using a random regular graph : one problem I have is in choosing the degree of the regular graph . It does not make sense to choose a constant value like say d=3, as that may be too high(making the graph extremely connected and thus, an unrealistic estimate) or too low(for a graph with 20k+ nodes, that will be low). I'm not very sure of it, but for the time being, I have given it to be log(n).

Network-X is too slow in handling a graph with just 1000 nodes(which no: pairs = 10^6), but then I have got the asymptotic peaks below these values, so its ok.
The plot is done using gnuplot - now to export the graph as GML, and to write the code for automatically generating the input python script for GUESS. <Apr 3 2011 12:02 pm>

<Apr 3 2011 4:17 pm> Done! The first video is done.




The video quality is pretty bad :(. I'm working on this right now - And moreover, it is quite difficult to understand anything from this video, but i think this goes along with the reports and help files, so it's ok :-|.

No comments:

Post a Comment