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!