Wednesday, February 16, 2011

More on Power Law graphs

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! 

Tuesday, February 8, 2011

The story so far . .


This is the first post on my project. I had started the project a few months back, and it's only now I've decided to keep a proper log on my project progress.

The aim of the whole project was to study complex networks - their structure and function. I kept the objective very broad for the simple reason that I didn't know what I was getting into. I got interested in the analysis of social networks after an earlier project of mine, in which I studied the Link Prediction Problem in Social Networks. I decided to investigate the area of large networks in general, and to understand the properties that shape the phenomena in these networks.

I started by looking at the background of this new research area. A lot of research activity has been going on in this area since the late 90s mainly because of the availability of large scale network data. After spending some time looking at the famous Stanley-Milgram experiment and and the Small-World Phenomenon, and I proceeded to understand the modelling of these networks.

Most early models of these networks were Random Graph Models, in particular the Erdos-Renyi G(n,p) model. A common property that was looked at was the existence of short paths in the network models. Random graphs do have short paths between arbitrary pairs of nodes  - I just went ahead and carried out few simulations using the Network-X package in Python - I wanted to get my hands a bit dirty at this stage itself. As expected, it follows  that a random graph induces a Poisson degree distribution on the nodes. (A simple and elegant proof exists for this - I'll post that in a future post). So far, so good. I studied Jon Klienberg's survey paper "Complex Networks and Decentralized Search Mechanisms" in detail which looks at the whole picture in a very algorithmic point of view. Algorithms were looked upon which can find these "short paths" in logarithmic or poly-logarithmic time. (Any algorithm which performs worse would not suit the notion of 'short paths').

The model looked at was a grid-based model and by varying a tuning parameter, one can show that poly-logarithmic time algorithms exist for finding short paths for a particular value of the tuning parameter. I simulated the simple greedy routing algorithm mentioned in Jon Klienberg's paper as well using the same tools, and found this to be true for the specific value of the alpha parameter. (For details, see the above mentioned paper).

However, all said and done, observed network data shows that most real-world networks follows a power law degree distribution. Power law networks were the focus of a lot of research in recent years, and I studied a paper considered seminal  - "Search in Power-Law Networks" by Adamic and Adar in detail. This paper talks about Random walk strategies and its variations that shows how poly-logarithmic time algorithms can be used to find short paths in power law networks. The existence of short paths in Power Law graphs is a proven fact, about which I will talk in the next post.