Last One week

<Mon Mar 28th 2011 2:12 a.m.> As part of the project, "Navigability and Searching in Social Networks", we consider the problem of information propagation through a social network.
This is one practical problem in the following settings :-
1. How far does a file spread in a P2P network?
2. How far does word-of-mouth 'rumours' spread?

The aim is to answer these two questions using simulation studies.
Ideally, file spread in a P2P network will have to make use of actual P2P information, so I'm not attempting to simulate this right now.
Word-of-Mouth Rumours are to be studied in the following manner :-
What are the models of Information Diffusion ? 1. The independent cascade model 2. Linear threshold Model
The theory of these two models will be adopted from Klienberg's paper.
The end result of the simulation study will be this :-
On each of the following three types of graphs :
1. Random Graphs
2. Klienberg's grid-model and,
3. Power Law Graphs
Nodes will be chosen at random and using both of the Information Diffusion Models, the spread of a word-of-mouth referral will be simulated,
and statistical properties will be measured.
This tantamounts to a total of 6 video visualizations showing Information DIffusion in different well known settings.
The tools to be used are the Network-X package(Python), GUESS(The Graph Exploratory System) and mencoder(to encode the images as a short video).
Because the earlier visualizations were lost, Random s-t reaachability will be simulated for both the Random Graph and Klienberg's grid model using
Greedy Routing. (2 more video visualizations). Another video visualization on Graph Coverage using Random Walks in Power Law Graphs will also be completed.

The end goals in the next 1 week's time will be :-
1. 9 video visualizations with documentation
2. The final report - Additions from the interim report will be the document on Random Walks in Power Law Graphs and the notes on simulations. <Mon Mar 28th 2011 2:46 a.m.>

Deadlines Ahead

Unfortunate incident - I lost almost all my files from last semester related to the project. It's not much, but I had a good collection of relevant papers categorized very well. And I lost my tex file for my report, and the simulation files, and output jpeg's I had generated. I think I have 10 more days to complete my project and the report. Right now, the work left, in order of priority are: 

1. The final report, along with the simulations on Random Graphs, Power Law Graphs, Klienberg's grid-based model and greedy routing algorithm - these I had done earlier, but I don't have them now. A simulation on Random walks in power law graphs is also pending. 

2. LiveJournal Dataset - Statistical Properties of the Same - Analysis - This will also be included in the final report. 

3. I would like to show a simulation regarding the spread of a file in a P2P network as well - to show the importance of accurate modeling of these networks. But this is at a lower priority. 

I am a bit disappointed with the way this project went  - I had thought of doing a bit more research, but by the time I kicked off in full swing, and had all the tools in place, a semester got over! And this semester was short - anyway I'm not cribbing. I can safely say I have done a fair amount of work - considering I don't have any team members. 

But I have identified few good problems and lines of research i want to pursue after I'm done with my report : 

1. Characterization of Social (or Complex Networks) as networks embedded in hyperbolic metric spaces. Klienberg's model considered the nodes to be in a Euclidean metric space, but recent research shows hyperbolic metric spaces achieve greater efficiency for greedy routing - I wanted to do a simulation of the same, and understand this more. 

2. Although this characterization is very promising, and researchers have started making hyperbolic maps of the whole Internet at the AS-Level, given a huge network, like say a P2P network, there does not exist any algorithm that can map the nodes to a hyperbolic metric space, so as to facilitate greedy routing. 

Such an algorithm will have good consequences. 

One problem I am facing is that I have not taken any formal course in Real Analysis or Topology, so metric spaces itself is a new concept for me. I spent quite some time in my project, trying to understand this characterization, but have not been able to proceed much. 

I'm a bit tense also. Hope to complete everything in time! 

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! 

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.