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
Times are displayed in time zone: Greenwich Mean Time : Belfast change

14:20 - 16:00: AlgorithmsMain conference at Mallorca+Menorca
Chair(s): Lawrence RauchwergerTexas A&M University
14:20 - 14:45
Talk
Articulation Point Guided Redundancy Elimination for Betweenness Centrality
Main conference
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
14:45 - 15:10
Talk
Multi-Core On-The-Fly SCC DecompositionArtifact Evaluation
Main conference
Vincent BloemenUniversity of Twente, Alfons LaarmanVienna University of Technology, Jaco van de PolUniversity of Twente
Link to publication DOI
15:10 - 15:35
Talk
A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization
Main conference
Ramakrishnan KannanGeorgia Institute of Technology, Grey BallardSandia National Laboratories, Haesun ParkGeorgia Institute of Technology
Link to publication DOI
15:35 - 16:00
Talk
Autogen: Automatic Discovery of Cache-Oblivious Parallel Recursive Algorithms for Solving Dynamic ProgramsArtifact Evaluation
Main conference
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