David A. Bader
IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA 30332


 
 

 

GraphCT: Multithreaded Algorithms for Massive Graph Analysis

The digital world has given rise to massive quantities of data that include rich semantic and complex networks. A social graph, for example, containing hundreds of millions of actors and tens of billions of relationships is not uncommon. Analyzing these large datasets, even to answer simple analytic queries, often pushes the limits of algorithms and machine architectures. We present GraphCT, a scalable framework for graph analysis using parallel and multithreaded algorithms on shared memory platforms. Utilizing the unique characteristics of the Cray XMT, GraphCT enables fast network analysis at unprecedented scales on a variety of input datasets. On a synthetic power law graph with 2 billion vertices and 17 billion edges, we can find the connected components in under 2 minutes. We can estimate the betweenness centrality of a similar graph with 537 million vertices and over 8 billion edges in under one hour. GraphCT is built for portability and performance.

Publication History

Versions of this paper appeared as:
  1. D. Ediger, K. Jiang, E.J. Riedy, and D.A. Bader, ``GraphCT: Multithreaded Algorithms for Massive Graph Analysis,'' IEEE Transactions on Parallel & Distributed Systems, 2012.

Download this report in Adobe PDF


 
 

Last updated: April 26, 2013

 




Computational Biology



Parallel Computing



Combinatorics