TY - GEN
T1 - Parallel k-Core decomposition on multicore platforms
AU - Kabir, Humayun
AU - Madduri, Kamesh
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/6/30
Y1 - 2017/6/30
N2 - k-core decomposition is a social network analytic that can be applied to centrality analysis, visualization, and community detection. There is a simple and well-known linear time sequential algorithm to perform k-core decomposition, and for this reason, k-core decomposition is widely used as a network analytic. In this work, we present a new shared-memory parallel algorithm called PKC for k-core decomposition on multicore platforms. This approach improves on the state-of-the-art implementations for k-core decomposition algorithms by reducing synchronization overhead and creating a smaller graph to process high-degree vertices. We show that PKC consistently outperforms implementations of other methods on a 32-core multicore server and on a collection of large sparse graphs. We achieve a 2.81× speedup (geometric mean of speedups for 17 large graphs) over our implementation of the ParK k-core decomposition algorithm.
AB - k-core decomposition is a social network analytic that can be applied to centrality analysis, visualization, and community detection. There is a simple and well-known linear time sequential algorithm to perform k-core decomposition, and for this reason, k-core decomposition is widely used as a network analytic. In this work, we present a new shared-memory parallel algorithm called PKC for k-core decomposition on multicore platforms. This approach improves on the state-of-the-art implementations for k-core decomposition algorithms by reducing synchronization overhead and creating a smaller graph to process high-degree vertices. We show that PKC consistently outperforms implementations of other methods on a 32-core multicore server and on a collection of large sparse graphs. We achieve a 2.81× speedup (geometric mean of speedups for 17 large graphs) over our implementation of the ParK k-core decomposition algorithm.
UR - http://www.scopus.com/inward/record.url?scp=85028077884&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028077884&partnerID=8YFLogxK
U2 - 10.1109/IPDPSW.2017.151
DO - 10.1109/IPDPSW.2017.151
M3 - Conference contribution
AN - SCOPUS:85028077884
T3 - Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
SP - 1482
EP - 1491
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 -