PEGASUS: Peta-Scale Graph Mining System

Original Pegasus logo (designed by Maria Tsiarli)

Pegasus is an award-winning large-scale graph mining system originally developed at Carnegie Mellon University.

Paper

You can read our ICDM 2009 paper Pegasus: A peta-scale graph mining system — implementation and observations for all the details.

Code

Software is available from the official Pegasus web page.

Fennel: Streaming Graph Partitioning for
Massive Scale Graphs

Streaming graph partitioning

How to partition fast a large-scale network into machines such that (i) all parts receive roughly the same amount of work, and (ii) the communication is minimized? Fennel provides a streaming graph partitioning framework that unifies existing heuristics, and is able to interpolate between them, improving performance overall.

Results of Fennel, the best competitor, hash partitioning, and METIS on the Twitter network. METIS requires hours, Fennel 40 minutes.

Paper 

Fennel: Streaming Graph Partitioning for Massive Scale Graphs  (Bibtex)

Code

Software is available from my github (to be released soon)
Disclaimer: The code is a prototype, and not the original implementation with optimized data structures that was used in the Fennel paper.

Streaming Graph Partitioning in the Planted Partition

We study further the streaming graph partitioning setting: when the graph is drawn from the planted partition model, we can uncover the partition using small seeds. The proposed method (EGyPT) may be used as a heuristic on real-world networks, and on similarity graphs.

EGyPT on digit similarity graph. See paper for details.

Paper 

Streaming Graph Partitioning in the Planted Partition Model  (Bibtex)

Code

Software is available from my github (to be released soon)