Skip to content
a repo for edge partitioning algorithms
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src
threadpool11
.clang-format
.gitignore
.ycm_extra_conf.py
CMakeLists.txt
LICENSE
README.md

README.md

Edge Partitioning Algorithms for Large Graphs

These algorithms are implemented by Qin Liu during his study at CUHK.

In this repo, we implement several edge partitioning algorithms and compute their replication factors for comparison:

Compilation and Usage

We tested our program on Ubuntu 14.04/16.04, and it requires the following packages: cmake, glog, gflags, boost:

sudo apt-get install libgoogle-glog-dev libgflags-dev libboost-all-dev

Compilation:

git clone https://github.com/ansrlab/edgepart.git
cd edgepart
mkdir release && cd release
cmake ..
make -j8

Usage:

$ ./main --help
main: -filename <path to the input graph> [-filetype <edgelist|adjlist>] [-p <number of partitions>] [-memsize <memory budget in MB>]

  Flags from /home/qliu/workspace/edgepart/src/main.cpp:
    -filename (the file name of the input graph) type: string default: ""
    -filetype (the type of input file (supports 'edgelist' and 'adjlist'))
      type: string default: "edgelist"
    -inmem (in-memory mode) type: bool default: false
    -memsize (memory size in megabytes) type: uint64 default: 4096
    -method (partition method: ne, sne, random, and dbh) type: string
      default: "sne"
    -p (number of parititions) type: int32 default: 10
    -sample_ratio (the sample size divided by num_vertices) type: double
      default: 2

Example. Partition the Orkut graph into 30 parts using our NE algorithm:

$ ./main -p 30 -method ne -filename /path/to/com-orkut.ungraph.txt

Example. Partition the LiveJournal graph into 30 parts using our SNE algorithm (CacheSize = 2|V|, see our paper for detailed description):

$ ./main -p 30 -method sne -filename /path/to/com-lj.ungraph.txt -sample_ratio 2

Evaluation

The experiments are conducted on a PC with 16 GB RAM. MLE means "memory limit exceeded".

Algorithms that are listed but not contained in this repo:

  • METIS
  • Sheep: published on VLDB'15
  • Algorithms that has been integrated in to PowerGraph
    • Oblivious
    • High-Degree (are) Replicated First (HDRF): published on CIKM'15
Algorithm wiki-Vote email-Enron web-Google com-LiveJournal com-Orkut twitter-2010 com-Friendster uk-union
METIS 5.25 2.40 1.05 2.13 MLE MLE MLE MLE
NE 2.35 1.34 1.12 1.55 2.48 1.88 1.98 1.04
Random 9.28 5.10 6.54 8.27 19.48 11.68 11.84 15.99
DBH 5.43 3.32 4.09 5.18 11.97 3.67 6.88 5.14
Oblivious 3.85 2.30 2.28 3.43 6.94 8.60 8.82 2.03
HDRF 3.90 2.12 2.18 3.33 7.27 7.90 8.87 1.62
Sheep 4.20 1.78 1.71 3.33 7.94 2.34 4.45 1.29
SNE 3.05 1.44 1.17 1.88 4.49 2.83 3.00 1.65
HSFC 3.80 3.75 2.66 3.78 6.31 5.82 4.80 1.96
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.