Efficient Anytime Anywhere Algorithms for Vertex Additions in Large and Dynamic Graphs

Over the past decade, there has been a dramatic increase in the availability of large and dynamic social network datasets. Conducting social network analysis (SNA) on these networks is critical for understanding underlying social phenomena. However, continuously evolving graph structures require massive recomputations and conducting SNA is infeasible if the computations have to be restarted for every change. Many recent works have proposed large-scale graph processing systems and frameworks, but less attention has been given to scalable SNA algorithm designs that can efficiently adapt to dynamic graph changes. Moreover, continuously adapting to dynamic graph changes such as node/vertex/actor additions/deletions in a parallel/distributed computational environment can skew the initial graph partitions, leading to load imbalance issues and performance degradation. Previous approaches that focus on computing SNA measures on dynamic graphs either ignore this critical load-balancing aspect or focus only on measures that are straightforward and inherently adjustable to changes in the graph topology. In this work, we have designed an anytime anywhere closeness centrality algorithm that can efficiently incorporate vertex additions while avoiding massive recomputations, by leveraging a generic framework for designing parallel/distributed algorithms called anytime anywhere. Furthermore, we have also performed an analysis of the effectiveness of various processor assignment strategies to mitigate the load imbalances caused by dynamic graph changes.