[month] [year]

Shukla Kshitij Prem Sarita – CSE

Shukla Kshitij Prem Sarita received his MS in Computer Science and Engineering (CSE). His research work was supervised by Prof. Kishore Kothapalli. Here’s a summary of Shukla Kshitij Prem Sarita’s MS  thesis, Computing Betweenness Centrality in Evolving Graphs as explained by him: 

Graph centralities play a crucial role in graph/network analytics to help us determine the importance of nodes in real-world graphs. Betweenness centrality is one such metric and is indeed the most popularly used centrality measure. Algorithms to calculate Betweenness centrality have been studied in the literature for a long time, the latest and most profound one being the Brandes Algorithm. Although many optimizations of the Brandes algorithm exist, very few of them address the problem of finding centrality in a continually evolving graph i.e, graphs that change due to the addition/deletion of nodes/edges. The majority of the graphs where these metrics are required are dynamic graphs. In such scenarios, having techniques to update centrality quickly and efficiently becomes paramount. There have been works on updating centrality on the addition/deletion of a single node/edge. However, the techniques become computationally expensive when updates happen in bulk. We build upon the work done on single edge betweenness centrality update and present a novel parallel algorithm to process a batch of edges at once. We also introduce some new optimization techniques along the way that exploits specific structural properties of graphs. We implement our algorithm on both multi-threaded CPUs and GPU and provide detailed analysis of our algorithm across CPU, GPU for varied batch edge updates on a variety of graph datasets spanning major application areas.