Efficient anytime anywhere algorithms for vertex additions in large and dynamic graphs

Eunice E. Santos, John Korah, Vairavan Murugappan, Suresh Subramanian

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

Abstract

Over the past decade, there has been a dramatic increase in the availability of large and dynamic social network datasets. Conducting social network analysis (SNA) on these networks is critical for understanding underlying social phenomena. However, continuously evolving graph structures require massive recomputations and conducting SNA is infeasible if the computations have to be restarted for every change. Many recent works have proposed large-scale graph processing systems and frameworks, but less attention has been given to scalable SNA algorithm designs that can efficiently adapt to dynamic graph changes. Moreover, continuously adapting to dynamic graph changes such as node/vertex/actor additions/deletions in a parallel/distributed computational environment can skew the initial graph partitions, leading to load imbalance issues and performance degradation. Previous approaches that focus on computing SNA measures on dynamic graphs either ignore this critical load-balancing aspect or focus only on measures that are straightforward and inherently adjustable to changes in the graph topology. In this work, we have designed an anytime anywhere closeness centrality algorithm that can efficiently incorporate vertex additions while avoiding massive recomputations, by leveraging a generic framework for designing parallel/distributed algorithms called anytime anywhere. Furthermore, we have also performed an analysis of the effectiveness of various processor assignment strategies to mitigate the load imbalances caused by dynamic graph changes.

Original languageEnglish (US)
Title of host publicationProceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1510-1519
Number of pages10
ISBN (Electronic)9781538634080
DOIs
StatePublished - Jun 30 2017
Externally publishedYes
Event31st IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017 - Orlando, United States
Duration: May 29 2017Jun 2 2017

Publication series

NameProceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017

Other

Other31st IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
Country/TerritoryUnited States
CityOrlando
Period5/29/176/2/17

Keywords

  • anytime anywhere algorithms
  • centrality analysis
  • dynamic graphs
  • dynamic vertex addition
  • parallel and distributed processing
  • social network analysis

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Networks and Communications
  • Information Systems

Fingerprint

Dive into the research topics of 'Efficient anytime anywhere algorithms for vertex additions in large and dynamic graphs'. Together they form a unique fingerprint.

Cite this