Parallel Framework for Updating Large-Scale Dynamic Networks
DescriptionAnalysis of large-scale dynamic networks is vital for understanding the relationship between entities that constantly change over time. Unfortunately, existing algorithms for identifying graph properties are optimized for static networks and resort to recomputing those properties over the entire network every time it evolves. To combat this problem, we introduce a parallel framework in this poster that efficiently updates the network properties as the structure changes in time through edge insertions or deletions. Our framework implements four parallel algorithms for identifying graph properties, namely: strongly connected components (SCC); single source shortest path (SSSP), minimum spanning tree (MST); and page rank on dynamic networks. All four implementations are enabled with shared-memory parallelism, while SCC is also enabled with distributed memory parallelism for improved memory utilization and SSSP is implemented on an NVIDIA GPU platform to leverage the data parallelism.