Skip to content
Multilevel graph coarsening algorithm with spectral and cut guarantees
Python Jupyter Notebook
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.
libraries
results
LICENSE
README.md
coarsening_demo.ipynb
experiment_approximation.ipynb
experiment_scalability.ipynb
experiment_spectrum.ipynb

README.md

graph-coarsening

Multilevel graph coarsening algorithm with spectral and cut guarantees

The code accompanies the paper: Graph reduction with spectral and cut guarantees published at JMLR/2019.

There are four python notebooks included:

  • The "coarsening_demo.ipynb" demonstrates how the code can be used with a toy example (see also this blogpost).
  • The "experiment_approximation.ipynb" reproduces the results of Section 5.1
  • The "experiment_spectrum.ipynb" reproduces the results of Section 5.2
  • The "experiment_scalability.ipynb" reproduces the results of Section 5.3

Since I have not fixed the random seed, some small variance should be expected in the experiment output.

Depedencies: pygsp, matplotlib, numpy, scipy, networkx, sortedcontainers

This work was kindly supported by the Swiss National Science Foundation (grant number PZ00P2 179981).

15 March 2019

Andreas Loukas

DOI

Released under the Apache license 2.0

You can’t perform that action at this time.