EM-FGS: Graph sparsification via faster semi-metric edges pruning

摘要

Graph sparsification is a useful approach for mining, analyzing, and visualizing large graphs. It simplifies the structure of a graph by pruning some of the edges while preserving the nodes. One well-known edge-removal technique is determination of a single shortest path between any pair of nodes to maintain the overall connectivity of the graph and remove the rest of the edges. Recently, a graph sparsification approach has been proposed that classifies the edges for removal according to metricity. Considering this classification system, a three-phase algorithm has been presented to prune the edges of each identified classification. The main bottleneck of the existing approach is the computational cost required for all three phases. To overcome these problems, we propose a new concept that generalizes the metricity of the edges to a uniform and homogeneous level. We also propose a new algorithm: edge metricity–based faster graph sparsification (EM-FGS), which utilizes edge weight as a constraint for effective pruning of the search space for shortest path computations. Our proposed approach is effective because we use the edge weight, which is a freely available intrinsic property of a graph, for edge-metricity identification. Our proposed approach improves the time complexity of existing methods from O(m ∗ n) + O(U3) to O(m ∗ log(n)). We evaluated our approach on publicly available real and synthetic graphs and improved the sequential algorithm’s execution time by a minimum of 125 times and the parallel algorithm’s runtime speed performance by 13 times while providing the same degree of accuracy.