TY - GEN
T1 - Efficient anytime anywhere algorithms for vertex additions in large and dynamic graphs
AU - Santos, Eunice E.
AU - Korah, John
AU - Murugappan, Vairavan
AU - Subramanian, Suresh
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/6/30
Y1 - 2017/6/30
N2 - 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.
AB - 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.
KW - anytime anywhere algorithms
KW - centrality analysis
KW - dynamic graphs
KW - dynamic vertex addition
KW - parallel and distributed processing
KW - social network analysis
UR - http://www.scopus.com/inward/record.url?scp=85028044358&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028044358&partnerID=8YFLogxK
U2 - 10.1109/IPDPSW.2017.179
DO - 10.1109/IPDPSW.2017.179
M3 - Conference contribution
AN - SCOPUS:85028044358
T3 - Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
SP - 1510
EP - 1519
BT - Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 31st IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
Y2 - 29 May 2017 through 2 June 2017
ER -