GraphCT: Multithreaded algorithms for massive graph analysis

David Ediger, Karl Jiang, E. Jason Riedy, David A. Bader

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


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 data sets, 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 data sets. On a synthetic power law graph with 2 billion vertices and 17 billion edges, we can find the connected components in 2 minutes. We can estimate the betweenness centrality of a similar graph with 537 million vertices and over 8 billion edges in under 1 hour. GraphCT is built for portability and performance.

Original languageEnglish (US)
Article number6365184
Pages (from-to)2220-2229
Number of pages10
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number11
StatePublished - 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


  • Cray XMT
  • Graph algorithms
  • high-performance computing
  • multithreaded architectures
  • network analysis


Dive into the research topics of 'GraphCT: Multithreaded algorithms for massive graph analysis'. Together they form a unique fingerprint.

Cite this