TY - GEN
T1 - Fast parallel graph triad census and triangle counting on shared-memory platforms
AU - Parimalarangan, Sindhuja
AU - Slota, George M.
AU - Madduri, Kamesh
PY - 2017/6/30
Y1 - 2017/6/30
N2 - Triad census is a graph analytic used for comparative network analysis and to characterize local structure in directed networks. For large sparse graphs, an algorithm by Batagelj and Mrvar is considered the state-of-the-art for computing triad census. In this paper, we present a new parallel algorithm for triad census. Our algorithm takes advantage of a specific graph vertex identifier ordering to reduce the operation count. We also develop several new variants for exact triangle counting in large sparse, undirected graphs. We show that our parallel triangle counting variants outperform other recently-developed triangle counting methods on current Intel multicore and manycore processors. We also achieve good strong scaling for both triad census and triangle counting on these platforms.
AB - Triad census is a graph analytic used for comparative network analysis and to characterize local structure in directed networks. For large sparse graphs, an algorithm by Batagelj and Mrvar is considered the state-of-the-art for computing triad census. In this paper, we present a new parallel algorithm for triad census. Our algorithm takes advantage of a specific graph vertex identifier ordering to reduce the operation count. We also develop several new variants for exact triangle counting in large sparse, undirected graphs. We show that our parallel triangle counting variants outperform other recently-developed triangle counting methods on current Intel multicore and manycore processors. We also achieve good strong scaling for both triad census and triangle counting on these platforms.
UR - http://www.scopus.com/inward/record.url?scp=85028046236&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028046236&partnerID=8YFLogxK
U2 - 10.1109/IPDPSW.2017.144
DO - 10.1109/IPDPSW.2017.144
M3 - Conference contribution
AN - SCOPUS:85028046236
T3 - Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
SP - 1500
EP - 1509
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 -