PPoPP 2016
Sat 12 - Wed 16 March 2016 Barcelona, Spain
Mon 14 Mar 2016 14:20 - 14:45 at Mallorca+Menorca - Algorithms Chair(s): Lawrence Rauchwerger

Betweenness centrality (BC) is an important metrics in graph analysis which indicates critical vertices in large-scale networks based on shortest path enumeration. Typically, a BC algorithm constructs a shortest-path DAG for each vertex to calculate its BC score. However, for emerging real-world graphs, even the state-of-the-art BC algorithm will introduce a number of redundancies, as suggested by the existence of articulation points. Articulation points imply some common sub-DAGs in the DAGs for different vertices, but existing algorithms do not leverage such information and miss the optimization opportunity.

We propose a redundancy elimination approach, which identifies the common sub-DAGs shared between the DAGs for different vertices. Our approach leverages the articulation points and reuses the results of the common sub-DAGs in calculating the BC scores, which eliminates redundant computations. We implemented the approach as an algorithm with two-level parallelism and evaluated it on a multicore platform. Compared to the state-of-the-art implementation using shared memory, our approach achieves an average speedup of 4.6x across a variety of real-world graphs, with the traversal rates up to 45 ~ 2400 MTEPS (Millions of Traversed Edges per Second).

Mon 14 Mar

PPoPP-2016-papers
14:20 - 16:00: Main conference - Algorithms at Mallorca+Menorca
Chair(s): Lawrence RauchwergerTexas A&M University
PPoPP-2016-papers14:20 - 14:45
Talk
Lei WangInstitute of Computing Technology, Chinese Academy of Science, Fan YangInstitute of Computing Technology, Chinese Academy of Science, Liangji ZhuangInstitute of Computing Technology, Chinese Academy of Science, Huimin CuiInstitute of Computing Technology, Chinese Academy of Sciences, Fang LvInstitute of Computing Technology, Chinese Academy of Sciences, Xiaobing FengICT CAS
Link to publication DOI
PPoPP-2016-papers14:45 - 15:10
Talk
Vincent BloemenUniversity of Twente, Alfons LaarmanVienna University of Technology, Jaco van de PolUniversity of Twente
Link to publication DOI
PPoPP-2016-papers15:10 - 15:35
Talk
Ramakrishnan KannanGeorgia Institute of Technology, Grey BallardSandia National Laboratories, Haesun ParkGeorgia Institute of Technology
Link to publication DOI
PPoPP-2016-papers15:35 - 16:00
Talk
Rezaul ChowdhuryStony Brook University, Pramod GanapathiStony Brook University, Jesmin Jahan TithiIntel, CA, USA, Charles BachmeierMIT, Bradley KuszmaulMIT, Charles E. LeisersonMIT, Armando Solar-LezamaMIT, Yuan TangFudan University
Link to publication DOI