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
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.
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
