### Research Interests

I am interested in Large Scale Networks - Social Networks, Internet, etc. In particular, (1) Modelling, Analysis and Simulation of Large Scale Networks
and (2) Theoretic Problems- Information Diffusion, Link Prediction, etc. Look below for detailed information.

### Research Experience

__Navigability and Searching in Complex Networks__*B.Tech Major Project*

*Sept 2010- Apr 2011*

*Guides : Dr. K. Muralikrishnan, NIT Calicut and Praphul Chandra, Senior Research Scientist, Hewlett Packard Labs, Bangalore*

*Complex Networks has been an active area of research since the 90s mainly because of the availability of large-scale network data. Complex networks can be broadly defined as networks that are so huge in size and scale that it is impossible to maintain global state topology at each node. This means, that although these graphs can be modeled reasonably using models from Graph Theory, most graph algorithms like Dijkstra's Algorithm, etc don't work. This gives rise to a very interesting problem - Is there a way to route through these networks without global state topology?. From an algorithmic point of view, this means trying to model networks in some way and develop algorithms that find these "short paths" in polylogarithmic time(in the size of network). So far, we've looked at Random Graph Models, the Watts-Strogatz Model, Klienberg's grid-based Model and Power Law Networks(otherwise known as Scale-free networks). It is a generally accepted fact that most observed networks have a power law degree distribution(although some argue that log-normal distributions should also be considered), in sharp contrast to the Poisson degree distribution in case of Random Graphs. I'm currently looking at another promising characterization of Complex Networks which consider these networks to be embedded in a hyperbolic metric space. The general idea is that the reason for observed efficient routing in Complex Networks is because of the proximity of nodes in some low level hidden metric space.What distance metrics on these metric spaces give rise to observed properties like power-law degree distribution, strong local clustering, etc. This is part of my senior thesis at National Institute of Technology(NIT), Calicut.*

Download the Report here.

Download the document on Random Walks in Power Law Graphs here

The informal project blog: http://www.complexnetworksproject.blogspot.com

Download all simulation files here

Simulation Video of Random Walks in Power Law Graphs

Simulation Video of High Degree Node Seeking Strategy(HDNSS) in Power Law Graphs

The Initial Report is available. View

Submitted http://arxiv.org/abs/1007.1345v1

Download the final report here

Download the Report here.

Download the document on Random Walks in Power Law Graphs here

The informal project blog: http://www.complexnetworksproject.blogspot.com

Download all simulation files here

Simulation Video of Random Walks in Power Law Graphs

Simulation Video of High Degree Node Seeking Strategy(HDNSS) in Power Law Graphs

__Placement Algorithm for Virtual Machines__*Research Project**Feb 2010- May 2010**Guide : Dr. Umesh Bellur, Associate Prof., Department of Computer Science and Engineering, IIT Bombay**This was an independent research project with Prof. Umesh Bellur at Indian Institute of Technology(IIT), Mumbai. The problem was that of packing virtual machines in physical machines in a data center. The problem was mapped to an instance of the multi-dimensional vector bin packing problem which is NP-hard. Although the bin packing problem and the vector packing problem are well studied in a single dimension, good approximation algorithms are very rare, especially for the Vector Bin packing problem in multiple dimensions.We came up with a Linear Programming(LP) Approach which gives reasonable approximation ratios.*

This is the wiki page for the project.This is the wiki page for the project.

The Initial Report is available. View

**Improved approximation bounds for Vector Bin Packing***Chetan S Rao, Jeffrey John Geevarghese, Karthik Rajan*Submitted http://arxiv.org/abs/1007.1345v1

__Link Prediction in Social Networks__*B.Tech Mini Project**Jan 2010- April 2010**Studied the Link prediction problem in Social Networks. Surveyed existing link prediction techniques from Data Mining, Graph Theory and Statistics. Read more*Download the final report here

*f*-Edge Cover Coloring of Nearly Bipartite Graphs*Summer Internship , Indian Institute of Science(IISc.), Bangalore**Jun 2009- Jul 2009**Guide : Dr. Sunil Chandran, Computer Science and Automation, IISc., Bangalore**Reviewed an unpublished manuscript**On f-edge cover coloring of nearly Bipartite Graphs.*A thorough literature survey of edge colorings and edge cover colorings on different types of graphs was done, with emphasis on Bipartite Graphs. Read more