December 2022
Sayantan Jana received his Master of Science – Dual Degree in Computer Science and Engineering (CSE). His research work was supervised by Prof. Kishore Kothapalli. Here’s a summary of his research work on Efficient Computation of Percolation Centrality in Static and Dynamic Networks:
Centrality measures on graphs have applications in many domains, including modeling the spread of an infection/disease, social network analysis, and transportation networks. As a result, parallel algorithms for computing various centrality metrics on graphs are gaining significant research attention in recent years. Also, since the networks of importance are extremely large, and the exact computation of the metric requires super-quadratic time, finding efficient algorithms to approximate the measure is essential.
We study parallel algorithms for the percolation centrality (PC) measure, which extends the betweenness centrality measure by incorporating a time-dependent state variable with every node. We present parallel algorithms that compute the source-based and source-destination variants of the percolation centrality values of nodes in a network. Our algorithms extend the algorithm of Brandes and introduce optimizations aimed at exploiting the structural properties of graphs. Experimental studies of our algorithms on an Intel Xeon(R) Silver 4116 CPU indicate that our algorithmic techniques offer a significant speedup.
We also present a new randomized approximation algorithm, called Dual-Brandes, for the source-destination variant of PC for undirected graphs. Our algorithm is inspired by the source-sampling technique developed by Brandes and Pich. We show that the estimates produced by our algorithm are equal to PC in expectation. We also experimentally evaluate our algorithm against baselines based on existing ideas on a collection of 12 real-world graphs. Our algorithm outperforms baselines in accuracy and other metrics. On a fixed sample size of 10% nodes, our algorithm achieves a mean squared error 61% lower than the nearest baseline.