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
N1 - Publisher Copyright:
© 2018 IEEE.
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.
T2 - 32nd IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2018
Y2 - 21 May 2018 through 25 May 2018
ER -