Dynamic graphs, which continuously evolve, require advanced methods for processing and updating computations efficiently. My PhD thesis addresses this by developing innovative incremental algorithms for three key problems: random walks, butterfly counting, and overlapping community detection. I introduce Wharf, a parallel system that uses compressed purely functional binary trees and pairing functions for efficient random walk updates, outperforming existing methods. Abacus, a novel algorithm for butterfly counting in fully dynamic bipartite graphs, provides highly accurate estimates and handles both edge insertions and deletions. Its parallel version, ParAbacus, achieves significant speedups through load-balanced processing. Lastly, Communis facilitates overlapping community detection in dynamic graphs by incrementally updating a persona graph, surpassing baselines in speed and quality. These techniques collectively ensure efficient and effective processing of dynamic graphs, delivering up-to-date and high-quality results. In this talk, I will detail these approaches, and demonstrate their performance.
