A Case Study of Complex Graph Analysis in Distributed Memory: Implementation and Optimization

Citations Over TimeTop 10% of 2016 papers

Abstract

In recent years, a large number of graph processing frameworks have been introduced, with their goal to simplify analysis of real-world graphs on commodity hardware. Additionally, the Graph500 benchmark has motivated extensive optimization of fundamental graph computations such as breadth-first search and shortest paths on leading high-performance computing systems. The purpose of this current work is to bridge the gap between these two research areas: we introduce a methodology for graph processing that is simple to implement, and yet offers high performance when scaling up from a single compute node up to several thousand nodes. We develop a compact and efficient graph representation, implement several graph analytics, and describe a number of optimizations that can be applied to these analytics. We test our implementations on the 2012 Web Data Commons hyperlink graph with 3.56 billion vertices and 128.7 billion edges, and perform scalability studies up to 4096 nodes of the Blue Waters supercomputer. On 256 nodes of Blue Waters, we demonstrate execution of six graph analytics on this large hyperlink graph in about 20 minutes.

Related Papers

• → Evaluation of Pattern Matching Workloads in Graph Analysis Systems(2016)2 cited
• → Graph Database and Graph Computing for Cyber-Physical Power Systems(2018)1 cited
• → CPS Modeling and Analysis Method of Power Grid Based on Graph Computing(2021)1 cited
• → Dealing with Big Data and Network Analysis Using Neo4j(2018)1 cited
• → Empirical Evaluation of Visual Graph Analytic Techniques(2019)