Presentation
Scaling K-Path Centrality Using Optimized Distributed Data Structure
SessionResearch Posters Display
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.
Event Type
Posters
Research Posters
TimeTuesday, 14 November 202310am - 5pm MST
LocationDEF Concourse
TP
XO/EX
Archive
view