Presentation

· Contributors · Organizations · Search Program · My Schedule · Happening Now · Maps

This content is available for: Tech Program Reg Pass, Exhibits Reg Pass. Upgrade Registration

Scaling K-Path Centrality Using Optimized Distributed Data Structure

DescriptionK-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.

Authors

Lance Fletcher

Texas A&M University

Lawrence Livermore National Laboratory

Trevor Steil

Lawrence Livermore National Laboratory

Roger Pearce

Lawrence Livermore National Laboratory

Texas A&M University

Event Type

Posters

Research Posters