Application of Graph Sparsification in Developing Parallel Algorithms for Updating Connected Components
Abstract
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.
Recommended Citation
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
Meeting Name
IEEE 30th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2016 (2016: May 23-27, Chicago, IL)
Department(s)
Computer Science
Research Center/Lab(s)
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)
978-1-5090-3682-0
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2016 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
01 May 2016
Comments
This research was funded by NSF-CCF under award numbers 1533918 and 1533881.