## 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