Rahil Sharma

Detecting communities is of great importance in social networks where systems are often represented as graphs. With the advent of web-based social networks like Twitter, Facebook, LinkedIn, etc. community detection became even more difficult due to the massive network size, which can reach up to hundreds of millions of vertices and edges. In this paper, we present a novel hybrid (shared + distributed memory) parallel algorithm to efficiently detect high quality communities in massive social… Show more

Detecting communities is of great importance in social networks where systems are often represented as graphs. With the advent of web-based social networks like Twitter, Facebook, LinkedIn, etc. community detection became even more difficult due to the massive network size, which can reach up to hundreds of millions of vertices and edges. In this paper, we present a novel hybrid (shared + distributed memory) parallel algorithm to efficiently detect high quality communities in massive social networks. For our simulations, we use synthetic graphs ranging from 100K to 16M vertices to show the scalability and quality performance of our algorithm. We also use two massive real world networks: (a) section of Twitter-2010 network having ≈ 41M vertices and ≈ 1.4B edges (b) UK-2007 (.uk web domain) having ≈ 105M vertices and ≈ 3.3B edges. Simulation results on a MPI setup with 8 compute nodes having 16 cores each shows that, upto ≈ 6X speedup is achieved for synthetic graphs in detecting communities without compromising the quality of the results. Show less

Journal paper :

One of the most relevant and widely studied structural properties of networks
is their community structure or clustering. Detecting communities is of great importance in
various disciplines where systems are often represented as graphs. Different community detection
algorithms have been introduced in the past few years, which look at the problem from different
perspectives. Most of these algorithms, however, have expensive computational time that makes
them… Show more

Journal paper :

One of the most relevant and widely studied structural properties of networks
is their community structure or clustering. Detecting communities is of great importance in
various disciplines where systems are often represented as graphs. Different community detection
algorithms have been introduced in the past few years, which look at the problem from different
perspectives. Most of these algorithms, however, have expensive computational time that makes
them impractical to use for large graphs found in the real world. In this paper, we propose a
multi-core multi-level (MCML) community detection algorithm based on the topology of the graph.
Applying MCML algorithm on two benchmark datasets for different strength requirements results
in detection of accurate communities. We also apply MCML on Facebook Forum dataset to find
users with similar interests and Amazon dataset.We show the scalability of MCML on large datasets
with 16 Xeon Phi cores. Show less

Journal paper :
Airborne Light Detection and Ranging (LiDAR) topographic data provide highly accurate digital terrain information, which is used widely in applications like creating flood insurance rate maps, forest and tree studies, coastal change mapping, soil and landscape classification, 3D urban modeling, river bank management, agricultural crop studies, etc. In this paper, we focus mainly on the use of LiDAR data in terrain modeling/ Digital Elevation Model(DEM) generation… Show more

Journal paper :
Airborne Light Detection and Ranging (LiDAR) topographic data provide highly accurate digital terrain information, which is used widely in applications like creating flood insurance rate maps, forest and tree studies, coastal change mapping, soil and landscape classification, 3D urban modeling, river bank management, agricultural crop studies, etc. In this paper, we focus mainly on the use of LiDAR data in terrain modeling/ Digital Elevation Model(DEM) generation. Technological advancements in building LiDAR sensors has enabled highly accurate and highly dense LiDAR point-clouds, which have made possible high resolution modeling of terrain surfaces. However, high density data results in massive data volumes, which pose computing issues when disseminating, processing, and storing data. We describe a novel technique based on the slope-map of the terrain, to reduce the data without sacrificing its accuracy. To the best of our knowledge this is the first ever landscape driven data reduction algorithm. We also perform an empirical study which shows that, there is no significant loss in accuracy for the DEM generated from a 52% reduced LiDAR dataset generated by our algorithm, compared to the DEM generated from an original complete LiDAR dataset. For accuracy of our statistical analysis, we perform Root Mean Square Error (RMSE) comparing all the grid points of original DEM to the DEM generated by reduced data, instead of comparing few random control points. Besides, our multi-core data reduction algorithm is highly scalable. We perform a scalability test using 1,2,4,8,16 CPU cores. We also describe a modified parallel Inverse Distance Weighted (IDW) spatial interpolation method, and show that the DEMs it generates is time-efficient, and has better accuracy than the one’s generated by traditional IDW method.
Show less

Journal paper :

Identifying functional modules is believed to reveal most cellular pro-
cesses. There have been many computational approaches to investigate
the underlying biological structures. We shall use community detec-
tion algorithm which we present in a bi-level algorithmic framework to
accurately identify protein complexes in less computational time. We
call this algorithm bi-level label propagation algorithm (BLLP). Using
this algorithm, we extract 123… Show more

Journal paper :

Identifying functional modules is believed to reveal most cellular pro-
cesses. There have been many computational approaches to investigate
the underlying biological structures. We shall use community detec-
tion algorithm which we present in a bi-level algorithmic framework to
accurately identify protein complexes in less computational time. We
call this algorithm bi-level label propagation algorithm (BLLP). Using
this algorithm, we extract 123 communities from a protein-protein inter-
action (PPI) network involving 2361 proteins and 7182 interactions in
Saccharomyces cerevisiae i.e.Yeast. Based on these communities found,
we make accurate prediction of functional modules for 57 uncharacter-
ized proteins in our dataset. We also perform a comparative study by
applying various well known community detection algorithms on the
PPI yeast network. We conclude that, BLLP algorithm extracts more
accurate community structures from PPI yeast networks in less compu-
tational time. Show less

Accepted poster presentation :

Currently, not many on-board analytics available for real-time machine productivity and work-site solutions. We develop compression and parallel processing algorithms for solving work-site problems exploiting on-board multi-core architecture. Accurate topographic data, obstacle detection, etc. are some potential applications.

Accepted abstract and oral presentation:

The modern science of networks has brought significant advances to study of networks. One of
the most relevant and widely studied structural properties of networks is their community structure or clustering. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as network. We are designing algorithms that focuses on the methodology for detecting community… Show more

Accepted abstract and oral presentation:

The modern science of networks has brought significant advances to study of networks. One of
the most relevant and widely studied structural properties of networks is their community structure or clustering. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as network. We are designing algorithms that focuses on the methodology for detecting community structures in weighted large scale networks such as the users’ relationship on social networks like Facebook, Twitter, etc. Most social networks are very large and tackling this volume of graph-structured data requires parallel tools. Using C++ libraries for graphs we incorporate parallel multicore directives to achieve scalable algorithms, which will be applicable for huge data-sets. It involves pre-processing the given graph to compute the topological features, then use label-propagation technique to find communities, followed by post processing to improve the quality of the result. We perform a comparative study using various bench mark data-sets. We observe that our algorithm gives better modularity clusters and running time, as compared to previous well known algorithms. We perform all our simulations on the University of Iowa’s Neon cluster using high-memory node with 24 cores. Show less

Accepted abstract and oral presentation

The first part of this work describes the following result that, logarithmic approximation factor for hard capacitated set cover can be achieved from Wolsey’s work, using a simpler and more intuitive analysis. We further show in our work, that O(log n) approximation factor can be achieved for the same problem by applying analysis of general set cover to analyze Wolsey’s algorithm. This work is based on the key observation that we make in Lemma 3.
The second part of this work describes the… Show more

The first part of this work describes the following result that, logarithmic approximation factor for hard capacitated set cover can be achieved from Wolsey’s work, using a simpler and more intuitive analysis. We further show in our work, that O(log n) approximation factor can be achieved for the same problem by applying analysis of general set cover to analyze Wolsey’s algorithm. This work is based on the key observation that we make in Lemma 3.
The second part of this work describes the geometric hitting set problem, where X is a ground set of points in a plane and S is a set of axis parallel rectangles. It is shown that  epsilon-nets of size O((1/epsilon) log log (1/epsilon)) can be computed in polynomial time. Applying Bronnimann and Goodrich result gives the hitting set of size O(log log OPT) for this problem. Show less