Research Posters Archive

Scaling K-Path Centrality Using Optimized Distributed Data Structure

Authors: Lance Fletcher (Texas A&M University, Lawrence Livermore National Laboratory); Trevor Steil (Lawrence Livermore National Laboratory); and Roger Pearce (Lawrence Livermore National Laboratory, Texas A&M University)

Abstract: K-Path centrality is based on the flow of information in a graph along simple paths of length at most K. This work addresses the computational cost of estimating K-path centrality in large-scale graphs by introducing the random neighbor traversal graph (RaNT-Graph). The distributed graph data structure employs a combination of vertex delegation partitioning and rejection sampling, enabling it to sample massive amounts of random paths on large scale-free graphs. We evaluate our approach by running experiments which demonstrate strong scaling on large real-world graphs. The RaNT-Graph approach achieved a 56,544x speedup over the baseline 1D partition implementation when estimating K-path centrality on a graph with 89 million vertices and 1.9 billion edges.

Best Poster Finalist (BP): no

Poster: PDF
Poster summary: PDF


Back to Poster Archive Listing