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 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 Decomposition 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 Programs 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 |