2017 IEEE 7th Symposium on Large Data Analysis and Visualization (LDAV)
Download PDF

Abstract

Pathfinder network scaling is a graph sparsification technique that has been popularly used due to its efficacy of extracting the “important” structure of a graph. However, existing algorithms to compute the pathfinder network (PFNET) of a graph have prohibitively expensive time complexity for large graphs: O(n3) for the general case and O(n2 log n) for a specific parameter setting, PFNET(r = ∞, q = n − 1), which is considered in many applications. In this paper, we introduce the first distributed technique to compute the pathfinder network with the specific parameters (r = ∞ and q = n − 1) of a large graph with millions of edges. The results of our experiments show our technique is scalable; it efficiently utilizes a parallel distributed computing environment, reducing the running times as more processing units are added.
Like what you’re reading?
Already a member?Sign In
Member Price
$11
Non-Member Price
$21
Add to CartSign In
Get this article FREE with a new membership!

Related Articles