SRC12. Parallel Algorithms for Updating Large Dynamic Networks Using Graph Sparsification
Student: Sriram Srinivasan (University of Nebraska Omaha)
Supervisor: Sanjukta Bhowmick (University of Nebraska Omaha)
Abstract: Algorithms for analyzing dynamic networks help study how properties of complex systems, such as those in bioinformatics and social sciences, evolve with time. Since the networks are very large, it is essential to design parallel algorithms for updating their properties. However, because network data is highly unstructured and exhibit poor locality of access, designing fast and scalable dynamic algorithms is challenging.
We present a framework for converting sequential algorithms on static networks to efficient parallel algorithms on dynamic networks using a technique called graph sparsification that expresses network algorithms in a reduction-like format. We describe how our framework can be used to update connected components and the minimum weighted spanning tree (MST), present a new graph ordering method for reducing computation time and the scalability results for these methods on shared memory systems. To the best of our knowledge, this is the first parallel implementation for updating MST.
Two-page extended abstract: pdf