After a considerable amount of reading on Power Law Graphs, and how they often come up in real world network data, I decided I should get my hands dirty by understanding some analysis techniques of these networks. In all of this exploration so far, my aim was to understand how to model complex networks, simulate them, and understand existing routing mechanisms in these. In most of the literature I have explored so far, emphasis on modelling, and routing strategies are simple strategies like Random Walks or Greedy strategies . A very strong line of analysis on Power Law Graphs(and in other graphs with arbitrary degree distributions as well) is using the formalism of Generating Functions suggested by Newman et al.
Adamic/Adar's seminal work on Search in Power Law networks makes use of this. It took me some time to understand the details in depth, and hence I wrote a small document outlining the proof for sublinear scaling of random walks. It is available here.
If you happen to go there, feel free to take a look at my other projects as well!
Adamic/Adar's seminal work on Search in Power Law networks makes use of this. It took me some time to understand the details in depth, and hence I wrote a small document outlining the proof for sublinear scaling of random walks. It is available here.
If you happen to go there, feel free to take a look at my other projects as well!
No comments:
Post a Comment