Rishi Ranjan Singh
Associate Professor
Dept. of Computer Science and Engineering
Indian Institute of Technology, Bhilai
E-mail: rishi@iitbhilai.ac.in
Areas of Interest
- Social & Complex Network Analysis, Machine Learning with Graphs, Approximation Algorithms, Combinatorial Optimization, Mathematical Formulation, Vehicle Routing Problems, Graph Theory, Theoretical computer science.
Education
- PhD, 2016, Indian Institute of Technology Ropar
- BTech, 2011, Uttar Pradesh Technical University, Lucknow, India
Teaching
- Theory of Computation
- Complexity Theory
- Approximation Algorithms
- Network Science
- Social and Complex Network Analysis
Experience
- November 2024-Present: Associate Professor, Dept. of Computer Science and Engineering, IIT Bhilai, India.
- August 2017-November 2024: Assistant Professor, Dept. of Computer Science and Engineering, IIT Bhilai, India.
- April 2016-August 2017: Assistant Professor, Dept. of Information Technology, IIIT Allahabad, India.
- September 2015-April 2016: Visiting Faculty, Dept. of Information Technology, IIIT Allahabad, India.
Students
- Kirtidev Mohapatra [Ph.D., Ongoing]
- Aditi Shukla [M.Tech., Ongoing]
- Sanjeevani Vishni Bhopre [M.Tech., Ongoing] (Co-supervised with Dr. Soumajit Pramanik)
- Parul Diwakar [M.Tech., Completed] (Co-supervised with Dr. Soumajit Pramanik)
- Shaswati Patra [Ph.D., Completed] (Co-supervised with Dr. Barun Gorain)
- Bikas Saha [M.Tech., Completed]
- Shivam Sharma [M.Tech., Completed] (Co-supervised with Dr. Amit Kumar Dhar)
- Anuj Singh [B.Tech. Hons., Completed]
Selected Publications
-
A variant of graph covering problem demands to find a set of sub-graphs when the union of sub-graphs contain all the edges of G. Another variant of graph covering problem requires finding a collection of subgraphs such that the union of the vertices of subgraphs forms a vertex cover. We study the later version of the graph covering problem. The objective of these problems is to minimize the size/cost of the collection of subgraphs. Covering graphs with the help of a set of edges, set of vertices, tree or tour has been studied extensively in the past few decades. In this paper, we study a variant of the graph covering problem using two special subgraphs. The first problem is called bounded component forest cover problem. The objective is to find a collection of minimum number of edge-disjoint bounded weight trees such that the vertices of the forest, i.e., collection of edge-disjoint trees, cover the graph. The second problem is called bounded size walk cover problem. It asks to minimize the number of bounded size walks which can cover the graph. Walks allow repetition of vertices/edges. Both problems are a generalization of classical vertex cover problem, therefore, are NP-hard. We give 4ρ and 6ρ factor approximation algorithm for bounded component forest cover and bounded size walk cover problems respectively, where ρ is an approximation factor to find a solution to the tree cover problem..
-
Experts from several disciplines have been widely using centrality measures for analyzing large as well as complex networks. These measures rank nodes/edges in networks by quantifying a notion of the importance of nodes/edges. Ranking aids in identifying important and crucial actors in networks. In this chapter, we summarize some of the centrality measures that are extensively applied for mining social network data. We also discuss various directions of research related to these measures.
-
In this paper, we study the wars fought in history and draw conclusions by analysing a curated temporal multi-graph. We explore the participation of countries in wars and the nature of relationships between various countries during different timelines. This study also attempts to shed light on different countries’ exposure to terrorist encounters.
-
We propose a network based framework to model spread of disease. We study the evolution and control of spread of virus using the standard SIR-like rules while incorporating the various available models for social interaction. The dynamics of the framework has been compared with the real-world data of COVID-19 spread in India. This framework is further used to compare vaccination strategies.
-
We use a queuing model to study the spread of an infection due to interaction among individuals in a public facility. We provide tractable results for the probability that a susceptible individual leaves the facility infected. This model is then applied to study infection spread in a closed system like a large campus, community, and model the interaction among individuals in the multiple public facilities found in such systems. These public facilities could be restaurants, shopping malls, public transportation, etc. We study the impact of relative timescales of the Close Contact Time (CCT) and the individuals’ stay time in a facility on the spread of the virus. The key contribution is on using queuing theory to model time-spread of an infection in a closed population.
-
We compare the Indian railways and domestic airways using network analysis approach. The analysis also compares different characteristics of the networks with a previous work and notes the change in the networks over a decade. In a populous country like India with an ever increasing GDP, more and more people are gaining the facility of choosing one mode of travel over the other. Here we have compared these two networks, by building a merger network. The need for such type of network arises as the order of both networks are different. This newly formed network can be used in identifying new routes and adding more flights on some of the popular routes in India.
-
Centrality measures have been proved to be a salient computational science tool for analyzing networks in the last two to three decades aiding many problems in the domain of computer science, economics, physics, and sociology. With increasing complexity and vividness in the network analysis problems, there is a need to modify the existing traditional centrality measures. Weighted centrality measures usually consider weights on the edges and assume the weights on the nodes to be uniform. One of the main reasons for this assumption is the hardness and challenges in mapping the nodes to their corresponding weights. In this paper, we propose a way to overcome this kind of limitation by hybridization of the traditional centrality measures. The hybridization is done by taking one of the centrality measures as a mapping function to generate weights on the nodes and then using the node weights in other centrality measures for better complex ranking.
-
Service Coverage Problem aims to find an ideal node for installing a service station in a given network such that services requested from various nodes are satisfied while minimizing the response time. Centrality Measures have been proved to be a salient computational science tool to find important nodes in networks. With increasing complexity and vividness in the network analysis problems, there is a need to modify the existing traditional centrality measures. In this paper we propose a new way of hybridizing centrality measures based on node-weighted centrality measures to address the service coverage problem.
-
Centrality measures, erstwhile popular amongst the sociologists and psychologists, have seen broad and increasing applications across several disciplines of late. Amongst a plethora of application-specific definitions available in the literature to rank the vertices, closeness centrality, betweenness centrality and eigenvector centrality (page-rank) have been the widely applied ones. We are surrounded by networks where information, signal or commodities are flowing through the edges. Betweenness centrality comes as a handy tool to analyze such systems, but computation of these scores is a daunting task in large-size networks. Since computing the betweenness centrality of one node is conjectured to be same as time taken for computing the betweenness centrality of all the nodes, a fast algorithm was required that can efficiently estimate a node’s betweenness score. In this paper, we propose a heuristic that efficiently estimates the betweenness score of a given node. The algorithm incorporates a non-uniform node-sampling model which is developed based on the analysis of random Erdős-Rényi graphs. We apply the heuristic to estimate the ranking of an arbitrary k vertices, called betweenness-ordering problem, where k is much less than the total number of vertices. The proposed heuristic produces very efficient results even when runs for a linear time in the number of edges. An extensive experimental evidence is presented to demonstrate the performance of the proposed heuristic for betweenness estimation and ordering on several synthetic and real-world graphs.
-
In this paper, we give randomized approximation algorithms for stochastic cumulative VRPs for the split and unsplit deliveries. The approximation ratios are max {1+ 1.5 α, 3} max {1+ 1. 5 α, 3} and 6, respectively, where α is the approximation ratio for the metric TSP. The approximation factor is further reduced for trees. These results extend the results in Anupam Gupta et al.(2012) and Daya Ram Gaur et al.(2013). The bounds reported here improve the bounds in Daya Ram Gaur et al.(2016).
-
There has been a recent resurge of interest in vehicle routing problems, especially in the context of green vehicle routing. One popular and simplified model is that of the cumulative vehicle routing problem. In this chapter, we examine the motivation, the definition, and the mixed integer linear program for the cumulative VRP. We review some of the recent results on approximation algorithms for the cumulative VRP. A column generation-based procedure for solving the cumulative VRP is also described. We also review approximation algorithms for a stochastic version of the cumulative VRP.
-
Cumulative vehicle routing problems are a simplified model of fuel consumption in vehicle routing problems. Here we computationally study, an inexact approach for constructing solutions to cumulative vehicle routing problems based on rounding solutions to a linear program. The linear program is based on the set cover formulation and is solved using column generation. The pricing subproblem is solved heuristically using dynamic programming. Simulation results show that a simple scalable strategy gives solutions with cost close to the lower bound given by the linear programming relaxation. We also give theoretical bounds on the integrality gap of the set cover formulation.
-
In this paper we give randomized approximation algorithms for stochastic cumulative VRPs for split and unsplit deliveries. The approximation ratios are 2(1+α) and 7 respectively, where α is the approximation ratio for the metric TSP. The approximation factor is further reduced for trees and paths. These results extend the results in [Technical note - approximation algorithms for VRP with stochastic demands. Operations Research, 2012] and [Routing vehicles to minimize fuel consumption. Operations Research Letters, 2013].
-
Betweenness centrality is widely used as a centrality measure, with applications across several disciplines. It is a measure that quantifies the importance of a vertex based on the vertex’s occurrence on shortest paths in a graph. This is a global measure, and in order to find the betweenness centrality of a node, one is supposed to have complete information about the graph. Most of the algorithms that are used to find betweenness centrality assume the constancy of the graph and are not efficient for dynamic networks. We propose a technique to update betweenness centrality of a graph when nodes are added or deleted. Observed experimentally, for real graphs, our algorithm speeds up the calculation of betweenness centrality from 7 to 412 times in comparison to the currently best-known techniques.
-
Betweenness Centrality measures, erstwhile popular amongst the sociologists and psychologists, have seen wide and increasing applications across several disciplines of late. In conjunction with the big data problems, there came the need to analyze large complex networks. Exact computation of a node’s betweenness is a daunting task in the networks of large size. In this paper, we propose a non-uniform sampling method to estimate the betweenness of a node. We apply our approach to estimate a node’s betweenness in several synthetic and real world graphs. We compare our method with the available techniques in the literature and show that our method fares several times better than the currently known techniques. We further show that the accuracy of our algorithm gets better with the increase in size and density of the network.
-
Cumulative vehicle routing problems are a simplified model of fuel consumption in vehicle routing problems. Here we study computationally, an approach for constructing approximate solutions to cumulative vehicle routing problems based on rounding solutions to a linear program. The linear program is based on the set cover formulation, and is solved using column generation. The pricing sub-problem is solved using dynamic programming. Simulation results show that the simple scalable strategy computes solutions with cost close to the lower bound given by the linear programming relaxation.
-
We consider a generalization of the capacitated vehicle routing problem known as the cumulative vehicle routing problem in the literature. Cumulative VRPs are known to be a simple model for fuel consumption in VRPs. We examine four variants of the problem, and give constant factor approximation algorithms. Our results are based on a well-known heuristic of partitioning the traveling salesman tours and the use of the averaging argument.
-
Betweenness centrality is a centrality measure that is widely used, with applications across several disciplines. It is a measure which quantifies the importance of a vertex based on its occurrence in shortest paths between all possible pairs of vertices in a graph. This is a global measure, and in order to find the betweenness centrality of a node, one is supposed to have complete information about the graph. Most of the algorithms that are used to find betwenness centrality assume the constancy of the graph and are not efficient for dynamic networks. We propose a technique to update betweenness centrality of a graph when nodes are added or deleted. Our algorithm experimentally speeds up the calculation of betweenness centrality (after updation) from 7 to 412 times, for real graphs, in comparison to the currently best known technique to find betweenness centrality.
Exposure to half-truths or lies has the potential to undermine democracies, polarize public opinion, and promote violent extremism. Identifying the veracity of fake news is a challenging task in distributed and disparate cyber-socio platforms. To enhance the trustworthiness of news on these platforms, in this article, we put forward a fake news detection model, OptNet-Fake. The proposed model is architecturally a hybrid that uses a meta-heuristic algorithm to select features based on usefulness and trains a deep neural network to detect fake news in social media. The d -D feature vectors for the textual data are initially extracted using the term frequency inverse document frequency (TF-IDF) weighting technique. The extracted features are then directed to a modified grasshopper optimization (MGO) algorithm, which selects the most salient features in the text. The selected features are then fed to various convolutional neural networks (CNNs) with different filter sizes to process them and obtain the n-gram features from the text. These extracted features are finally concatenated for the detection of fake news. The results are evaluated for four real-world fake news datasets using standard evaluation metrics. A comparison with different meta-heuristic algorithms and recent fake news detection methods is also done. The results distinctly endorse the superior performance of the proposed OptNet-Fake model over contemporary models across various datasets.