Application of Graph Sparsification in Developing Parallel Algorithms for Updating Connected Components
Analyzing large dynamic networks is an important problem with applications in a wide range of disciplines. A key operation is updating the network properties as its topology changes. In this paper we present graph sparsification as an efficient abstraction for updating the properties of dynamic networks. We demonstrate the applicability of graph sparsification in updating the connected components in random and scale-free networks on shared memory systems. Our results show that the updating is scalable (10X on 16 processors for larger networks). To the best of our knowledge this is the first parallel implementation of graph sparsification. Based on these initial results, we discuss how the current implementation can be further improved and how graph sparsification can be applied to updating other network properties.
S. Srinivasan et al., "Application of Graph Sparsification in Developing Parallel Algorithms for Updating Connected Components," Proceedings of the IEEE 30th International Parallel and Distributed Processing Symposium Workshops (2016, Chicago, IL), pp. 885-891, Institute of Electrical and Electronics Engineers (IEEE), May 2016.
The definitive version is available at https://doi.org/10.1109/IPDPSW.2016.180
IEEE 30th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2016 (2016: May 23-27, Chicago, IL)
Intelligent Systems Center
Keywords and Phrases
Connected component; Dynamic networks; Graph sparsification; Large dynamic networks; Network properties; Shared memory system
International Standard Book Number (ISBN)
Article - Conference proceedings
© 2016 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.