Subhajit Sahu supervised by Prof. Kishore Kothapalli received  his doctorate in  Computer Science and Engineering (CSE). Here’s a  summary of his research work on Time Efficient, Space Efficient, and Fault Tolerant Social Network Algorithms for Static and Dynamic Graphs:

The world is in the midst of an unprecedented growth of interconnected data, and graph processing systems are expected to play a vital role. Customers of such systems are diverse and span across various industries. Social media platforms use graph algorithms to suggest connections and personalize user experiences. Online marketplaces leverage age graph algorithms to provide personalized product recommendations based on user preferences and browsing history. The transportation industry uses graph algorithms to minimize travel time and improve logistics. Researchers and data scientists use graph algorithms to analyze and extract insights from complex interconnected datasets. However, the vast scale of social networks and the demand for real-time insights impose significant computational challenges, making traditional single-threaded systems inadequate. Parallel processing, which distributes tasks across CPU cores, accelerates computation, enabling timely analysis of large, dynamic graphs. Social networks’ dynamic nature — frequent updates to connections and data — further necessitates efficient algorithms, as traditional static graph methods struggle to adapt to continuous changes. This thesis embarks on a journey to address the challenge of efficiently analyzing static and dynamic graph data in large social networks while embracing parallelism on multicore CPUs and GPUs. We focus on the problems of discovering natural divisions in such networks (community detection), predicting missing links, and identifying authoritative members (PageRank). First, we propose highly efficient parallel implementations of Louvain and Leiden algorithms, which achieves significant speedups over existing community detection methods. We then present memory-efficient techniques utilizing sketches to reduce memory consumption and enhance scalability of these algorithms. Furthermore, we introduce a novel parallel link prediction algorithm, LHub, which significantly outperforms existing techniques. Finally, we propose parallel algorithms for efficient PageRank and community detection on dynamic graphs, including our Dynamic Frontier approach for efficient tracking of affected vertices and lock-free fault-tolerant algorithms for PageRank updates. These contributions advance the capability to process and extract insights from massive, evolving graphs.

June 2025