Sunday, April 3, 2011

Simulations on Power law Graphs

<Apr 3 2011 7:07 pm> Now, I'm going to work on simulating a Random Walk Strategy on Power Law Graphs with broadcasting to two levels of neighbours - this is a fair assumption according to Adamic/Adar.
The procedure is simple - You start at an arbitrary node, and each iteration, you forward to a node reached by randomly choosing one of the outgoing edges, and in the process transmitting this information to two levels of its neighbours.
Say if I start at node v1, I choose at random one of the neighbours of v1 and transmit the message to the neighbours of v1 and their neighbours - This type of random walk covers the network in sublinear time(Adamic/Adar). <Apr 3 2011 7:11 pm>

<Apr 3 2011 11:39 pm> Random Walks simulation has been much more interesting. In this case, the visualisation actually allows us to visualise something! What is interesting from these kinds of visualisations is that they help us in understanding the problem better. The graphs and statistics one would obtain for random walks is somewhat similar in spirit to say an example, like the Spread of a file in a P2P network.

This is the completed video. The random walk broadcasts the message to neighbours of the node holding the message and their neighbours - which is a fair assumption in social networks, as one will know his friends and their friends. The random walks are continued till there is graph coverage of 80%.



A small improvement to the above strategy is to choose the node with the highest degree at each step, i.e. to to forward the packet to the highest connected neighbour. Only small modifications are required in the code for this. Check the video and notice how fast it covers the graph in comparison to the Random Walk Video above.



<Apr 4 2011 3:20 am> I want to simulate Greedy Routing on Klienberg's Grid-based model with the inverse square law distribution as well, but due to time constraints, I'm leaving it for the time being. I need to work on my report now. Will come back later.

No comments:

Post a Comment