GraphletLift is an algorithm to estimate the graphlet counts by a method we call lifting. The method is described and analyzed in this paper, with some theoretical results in the supplementary materials.
You can jump in to a demo at the introductory Jupyter notebook.
To install, clone the repo and run
git clone https://github.com/dshemetov/LiftSRW
cd LiftSRW
pipenv install
pipenv shell
cd pynauty-0.6.0
cd nauty
make clean
make
cd ..
make clean
make pynauty
make user-ins
make tests
exit
To verify that you have installed everything correctly run
pipenv run python tests.py
which should conclude with an average time report.
The code has been tested on
- OS Mojave 10.14.3, Python 3.5.2, gcc Developer tools
- Linux Ubuntu 16.04, Python 3.5.2, gcc
See the "Introduction.ipynb" for a tutorial on usage.
The bulk of the code is contained in "lift.py". The unit tests are in "tests.py". Various conversion and batch experiment scripts are in "/scripts". Some graphs we tested were too large to fit in repo; you can find the missing graphs by searching on http://networkrepository.com/ (you may have to convert them from the .mtx format into a .edges or .edgelist format; converter script in "/scripts").
The code uses pynauty-0.6.0, a wrapper for nauty by Peter Dobcsányi, and networkx. For ease of installation, pynauty-0.6.0 is bundled in this repo.
We compared our method to two other modern methods: PGD and ESCAPE.