This is the fast, scalable implementation of edge decomposition based on fixed points of degree peeling used in Atlas.
For the main Atlas visualization repository, see github.com/fredhohman/atlas.
Download or clone this repository.
git clone https://github.com/fredhohman/atlas-algorithm.git
From the directory, compile the code by
g++ -o atlas-decomposition -g -fopenmp -O3 parallelkcore.cpp
We first convert a plain text edge list file to a .bin
to use for algorithm. Input text files should be comma (or tab) separated where each row contains a source
and target
(these must be numbers).
Note: graphs should not have:
- self-loops / self-edges
- duplicate edges (multi-graph)
For example, a graph with three edges would look like:
1, 2
1, 3
2, 4
Convert the text edge list to a .bin
using the mmap.jar file available here: http://poloclub.gatech.edu/mmap/MMap.zip
java -jar mmap.jar Convert <myGraph>
The algorithm takes in this .bin
file to perform the decomposition. It outputs a myGraph-decomposition.csv
file where each row contains three values: the source
, target
, and peel
. The source
and target
columns together form the original edge list, and the new column peel
contains the peel assignment, i.e., what layer an edge belongs to. To run the algorithm, use:
./atlas-decomposition <myGraph>.bin <# of edges> <# of vertices>
It also outputs a myGraph-decomposition-info.json
file that contains metadata such as the number of vertices in the graph, number of edges in the graph, time taken to preprocess the data, and time taken to run the algorithm.
For an example of what the output looks like, see github.com/fredhohman/atlas/data
Atlas: Local Graph Exploration in a Global Context
James Abello*, Fred Hohman*, Varun Bezzam, Duen Horng (Polo) Chau
ACM Conference on Intelligent User Interfaces (IUI). Los Angeles, CA, USA, 2019.
* Authors contributed equally.
@inproceedings{hohman2019atlas,
title={Atlas: Local Graph Exploration in a Global Context},
author={Abello, James and Hohman, Fred and Bezzam, Varun and Chau, Duen Horng},
booktitle={Proceedings of the International Conference on Intelligent User Interfaces},
year={2019},
organization={ACM}
}
MIT License. See LICENSE.md
.
For questions or support open an issue or contact Fred Hohman.