The explosive growth of interconnected data has elevated the role of graph analytics in domains ranging from social media and e-commerce to transportation and biological systems. However, the massive scale and dynamic nature of real-world graphs pose substantial challenges to traditional graph processing methods, which are often sequential, memory-intensive, and ill-suited for rapid updates. This thesis addresses these limitations by developing high-performance, memory-efficient, and fault-tolerant algorithms for analyzing both static and dynamic graphs, with a focus on community detection, link prediction, and PageRank computation.

We first introduce GVE-Louvain and GVE-Leiden — parallel, shared-memory implementations that significantly accelerate community detection by optimizing both the local-moving and aggregation phases. These algorithms employ techniques such as pre-allocated CSR structures, per-thread hash tables, dynamic OpenMP scheduling, and a refinement step for Leiden. On a 3.8B-edge graph, GVE-Louvain and GVE-Leiden achieve processing rates of 560M and 403M edges/s, respectively, offering up to 50× mean speedup over existing methods while maintaining or improving modularity. To address memory constraints, we propose weighted-sketch-based variants of Louvain, Leiden, and LPA that replace per-thread hash tables with Misra-Gries and Boyer-Moore sketches. These methods maintain over 99% of the community quality while reducing memory usage to a few kilobytes per thread and incurring only modest runtime overhead.

For link prediction, we introduce DLH (Disregard Large Hubs), a parallel algorithm that restricts similarity computations to 2-hop neighborhoods and skips high-degree hubs to improve both efficiency and accuracy. DLH achieves up to 1622×mean speedup over baseline methods and reaches processing rates of 38.1M edges/s on billion-scale graphs.

In the dynamic setting, we develop asynchronous PageRank update strategies (DF and DF-P) that selectively recompute ranks based on local changes, as well as DF_LF — a fault-tolerant, lock-free parallel implementation. These methods deliver up to 26× mean speedup over static recomputation and maintain high accuracy and scalability under thread failures. Finally, we extend the Dynamic Frontier approach to community detection on dynamic graphs. This technique identifies minimal affected regions using efficient heuristics and supports integration with parallel Louvain, LPA, and hybrid algorithms. Our methods consistently outperform current dynamic algorithms in speed and community quality on large-scale benchmarks.

Together, these contributions represent a comprehensive suite of scalable, practical solutions for processing massive, evolving graphs using multicore architectures.