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

Fingerprint

Data storage equipment
Availability
Electric network analysis
Processing
Social networks
Methodology
Scaling
Dynamism
Trade-offs
Social systems
Theoretical analysis
Network analysis
Closeness
Centrality

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

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

Handling vertex deletions in memory scalable anytime anywhere algorithms for large and dynamic social networks. / Santos, Eunice E.; Korah, John; Murugappan, Vairavan.

Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 1153-1162 8425544 (Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018).

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

Santos, EE, 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., 8425544, Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018, Institute of Electrical and Electronics Engineers Inc., pp. 1153-1162, 32nd IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018, Vancouver, Canada, 5/21/18. https://doi.org/10.1109/IPDPSW.2018.00177
Santos EE, Korah J, Murugappan V. 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. Institute of Electrical and Electronics Engineers Inc. 2018. p. 1153-1162. 8425544. (Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018). https://doi.org/10.1109/IPDPSW.2018.00177
Santos, Eunice E. ; Korah, John ; Murugappan, Vairavan. / Handling vertex deletions in memory scalable anytime anywhere algorithms for large and dynamic social networks. Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 1153-1162 (Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018).
@inproceedings{ea9dd43cc6e2439ebe1e98181eed74b9,
title = "Handling vertex deletions in memory scalable anytime anywhere algorithms for large and dynamic social networks",
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.",
keywords = "Anytime anywhere algorithms, Centrality analysis, Dynamic graphs, Memory scalability, Parallel and distributed processing, Social network analysis",
author = "Santos, {Eunice E.} and John Korah and Vairavan Murugappan",
year = "2018",
month = "8",
day = "3",
doi = "10.1109/IPDPSW.2018.00177",
language = "English (US)",
isbn = "9781538655559",
series = "Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1153--1162",
booktitle = "Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018",
address = "United States",

}

TY - GEN

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

AU - Santos, Eunice E.

AU - Korah, John

AU - Murugappan, Vairavan

PY - 2018/8/3

Y1 - 2018/8/3

N2 - 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.

AB - 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.

KW - Anytime anywhere algorithms

KW - Centrality analysis

KW - Dynamic graphs

KW - Memory scalability

KW - Parallel and distributed processing

KW - Social network analysis

UR - http://www.scopus.com/inward/record.url?scp=85052229744&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052229744&partnerID=8YFLogxK

U2 - 10.1109/IPDPSW.2018.00177

DO - 10.1109/IPDPSW.2018.00177

M3 - Conference contribution

AN - SCOPUS:85052229744

SN - 9781538655559

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

SP - 1153

EP - 1162

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

PB - Institute of Electrical and Electronics Engineers Inc.

ER -