Articulation Point Guided Redundancy Elimination for Betweenness Centrality
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 MarDisplayed time zone: Belfast change
14:20 - 16:00
|Articulation Point Guided Redundancy Elimination for Betweenness Centrality |
Lei Wang Institute of Computing Technology, Chinese Academy of Science, Fan Yang Institute of Computing Technology, Chinese Academy of Science, Liangji Zhuang Institute of Computing Technology, Chinese Academy of Science, Huimin Cui Institute of Computing Technology, Chinese Academy of Sciences, Fang Lv Institute of Computing Technology, Chinese Academy of Sciences, Xiaobing Feng ICT CASLink to publication DOI
|Multi-Core On-The-Fly SCC Decomposition|
Vincent Bloemen University of Twente, Alfons Laarman Vienna University of Technology, Jaco van de Pol University of TwenteLink to publication DOI
|A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization |
Ramakrishnan Kannan Georgia Institute of Technology, Grey Ballard Sandia National Laboratories, Haesun Park Georgia Institute of TechnologyLink to publication DOI
|Autogen: Automatic Discovery of Cache-Oblivious Parallel Recursive Algorithms for Solving Dynamic Programs|
Rezaul Chowdhury Stony Brook University, Pramod Ganapathi Stony Brook University, Jesmin Jahan Tithi Intel, CA, USA, Charles Bachmeier MIT, Bradley Kuszmaul MIT, Charles E. Leiserson MIT, Armando Solar-Lezama MIT, Yuan Tang Fudan UniversityLink to publication DOI