Doing some simulations of Small-World networks. In other words, graphs/networks that display some small world phenomenon we all know as the “6 degrees of separation” Heres a few generated graphs from my project in Advanced Algorithms. I have been focusing on grid model described by Kleinberg in “The Small-World Phenomenon: An Algorithmic Perspective”. The model is a 2d N sized square grid with connections (edges) connecting nodes in local areas and long distance. Anyways. Heres a pretty snarly picture.
You can track my Python code here on GitHub
n = 10, p=1, q = 2
————-UPDATE————-
wow, that was ugly
Ive updated the code, added a show_me() method which throws a pyplot display of the graph with the nodes positioned as it should be, in a darn grid!
try it out
Python 2.5.2 (r252:60911, Oct 5 2008, 19:24:49)
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import smallworld as sw
>>> sw.show_me( sw.kleinberg_grid(8, 1, 2, 2) )
a nice popup window will now be displaying the grid
>>> sw.plt.savefig("hi.png")
save it for a blog post
other things you can try,
>>> g = sw.kleinberg_grid(10,1,2,2)
>>> u = (0,0)
>>> v = (9,9)
>>> sw.kb_trav(g, u, v)
8
outputs the number of edges traversed with a local information only traversal, nodes only know links they are on currently
if anyone can tweek the make long range function so that it doesn’t run in n^2 time, please feel free =)
Its Blog 