Handling vertex deletions in memory scalable anytime anywhere algorithms for large and dynamic social networks

Eunice E. Santos, John Korah, Vairavan Murugappan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Due to the dramatic increase in the availability of dynamic data in various domains, including computational social systems, there is a need to formulate processing and analysis methodologies that can efficiently incorporate data changes while reducing recomputations. This is especially critical for network analysis techniques where current methodologies pursue strategies based on maintaining intermediate or partial results. However, there are critical trade-offs with respect to memory and processing time overheads that have prevented these designs from scaling with larger network sizes and higher rates of network dynamism. In this work, we demonstrate the capability of our anytime anywhere framework to formulate closeness centrality algorithms that can adapt to memory availability by varying the number of partial results that are stored and maintained over the course of the analysis. Additionally, using a combination of theoretical analysis and experimental results we compare the performance of these algorithm designs, and identify conditions under which one design performs better than the others.

Original languageEnglish (US)
Title of host publicationProceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1153-1162
Number of pages10
ISBN (Print)9781538655559
DOIs
StatePublished - Aug 3 2018
Externally publishedYes
Event32nd IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018 - Vancouver, Canada
Duration: May 21 2018May 25 2018

Publication series

NameProceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018

Other

Other32nd IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018
CountryCanada
CityVancouver
Period5/21/185/25/18

Keywords

  • Anytime anywhere algorithms
  • Centrality analysis
  • Dynamic graphs
  • Memory scalability
  • Parallel and distributed processing
  • Social network analysis

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Networks and Communications
  • Hardware and Architecture
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Handling vertex deletions in memory scalable anytime anywhere algorithms for large and dynamic social networks'. Together they form a unique fingerprint.

  • Cite this

    Santos, E. E., Korah, J., & Murugappan, V. (2018). Handling vertex deletions in memory scalable anytime anywhere algorithms for large and dynamic social networks. In Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018 (pp. 1153-1162). [8425544] (Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPSW.2018.00177