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.

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

Comments

This research was funded by NSF-CCF under award numbers 1533918 and 1533881.

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

Link to Full Text

Share

 
COinS