Multiscale graph clustering with dynamic Ollivier-Ricci curvature

Multiscale clustering on undirected graphs based on the geometric modularity method. This relies on computing the dynamic Ollivier-Ricci curvature based on Markov diffusion processes for edges of a graph at a sequence of increasing scales. The resulting curvature weighted graphs are clustered using signed Louvain modularity.

Cite

Please cite our paper if you use this code in your own work. To reproduce the results of our paper, run the jupyter notebooks in the folder examples/paper_results.

@article{GosztolaiArnaudon2021,
author = {Gosztolai, Adam and Arnaudon, Alexis},
doi = {10.1038/s41467-021-24884-1},
issn = {2041-1723},
journal = {Nat. Commun.},
number = {1},
pages = {4561},
title = {{Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature}},
volume = {12},
year = {2021}
}

Getting started

Installation

To install this package, clone this repository, and run

pip install geometric-clustering

To run the code is very simple. The folder /examples contains some example scripts.

Data requirements

Our code can be applied to any graph provided as a networkx object. This can be taken from the examples in the folder /graph, or provided by the user. You can generate a host of standard graphs using our graph library package!

Compute curvature

If taken from the folder graph, the multiscale curvature can be computed by running

python run_curvature.py <graph>

To plot the results, use

python plot_curvature.py <graph>

To only run the classical Ollivier-Ricci curvature, use

python compute_original_OR.py <graph>

Compute clustering

The clustering function requires our PyGenStability package, which is a Python wrapper for the generalised Louvain algorithm.

To run clustering using geometric modularity (modularity on curvature weighted graph without null model), run

python run_clustering.py <graph>

then plot the results with

python plot_clustering.py <graph>

Multiscale graph clustering with dynamic Ollivier-Ricci curvature

Multiscale clustering on undirected graphs based on the geometric modularity method. This relies on computing the dynamic Ollivier-Ricci curvature based on Markov diffusion processes for edges of a graph at a sequence of increasing scales. The resulting curvature weighted graphs are clustered using signed Louvain modularity.

Cite

Please cite our paper if you use this code in your own work. To reproduce the results of our paper, run the jupyter notebooks in the folder examples/paper_results.

@article{gosztolaiArnaudon,
  author    = {Adam Gosztolai and
               Alexis Arnaudon},
  title     = {Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature},
  journal = {Preprint at Researchsquare https://www.researchsquare.com/article/rs-222407/v1}
  doi = {10.21203/rs.3.rs-222407/v1}
  year      = {2021}
}

Getting started

Installation

To install this package, clone this repository, and run

pip install geometric-clustering

To run the code is very simple. The folder /examples contains some example scripts.

Data requirements

Our code can be applied to any graph provided as a networkx object. This can be taken from the examples in the folder /graph, or provided by the user. You can generate a host of standard graphs using our graph library package!

Compute curvature

If taken from the folder graph, the multiscale curvature can be computed by running

python run_curvature.py <graph>

To plot the results, use

python plot_curvature.py <graph>

To only run the classical Ollivier-Ricci curvature, use

python compute_original_OR.py <graph>

Compute clustering

The clustering function requires our PyGenStability package, which is a Python wrapper for the generalised Louvain algorithm.

To run clustering using geometric modularity (modularity on curvature weighted graph without null model), run

python run_clustering.py <graph>

then plot the results with

python plot_clustering.py <graph>

First release

v1.0

fix format