GraphRicciCurvature

Binder Open In Colab Build Status Documentation Status License

This work computes the Ollivier-Ricci Curvature [1], Ollivier-Ricci Flow [2] [3] and Forman-Ricci Curvature (or Forman curvature) [4], and Ricci community [3] detected by Ollivier-Ricci flow metric.

Ricci flow on manifold karate club demo

Curvature is a geometric property to describe the local shape of an object. If we draw two parallel paths on a surface with positive curvature like a sphere, these two paths move closer to each other while for a negatively curved surface like a saddle, these two paths tend to be apart.

In [Ni], we observe that the edge Ricci curvature plays an important role in the graph structure. An edge with positive curvature represents an edge within a cluster, while a negatively curved edge tent to be a bridge within clusters. Also, negatively curved edges are highly related to graph connectivity, with negatively curved edges removed from a connected graph, the graph soon become disconnected.

Ricci flow is a process to uniformized the edge Ricci curvature of the graph. For a given graph, the Ricci flow gives a “Ricci flow metric” on each edge as edge weights, such that under these edge weights, the Ricci curvature of the graph is mostly equal everywhere. In [Ni3], this “Ricci flow metric” is shown to be able to detect communities.

Both Ricci curvature and Ricci flow metric can act as a graph fingerprint for graph classification. The different graph gives different edge Ricci curvature distributions and different Ricci flow metric.

Video demonstration of Ricci flow for community detection:

Ricci community

Package Requirement

Installation

Installing via pip

pip3 install [--user] GraphRicciCurvature
  • From version 0.4.0, in order to support larger graph, we switch to NetworKit’s pairwise bidirectional dijkstra algorithm for density distribution (NetworKit>6.0 is required). If the installation of NetworKit failed, please refer to [NetworKit’ Installation instructions]. In most of the cast build this package from source is recommended.

Upgrading via pip

To run with the latest code for the best performance, upgrade GraphRicciCurvature to the latest version with pip:

pip3 install [--user] --upgrade GraphRicciCurvature

Getting Started

  • See the jupyter notebook tutorial on [nbviewer] for a walk through for the basic usage of Ricci curvature, Ricci flow, and Ricci flow for community detection.
  • Or you can run it in directly on [binder] (no account required) or [Google colab] (Faster but Google account required).
  • Check the Documentations.
  • Try out sample graphs with precomputed Ricci curvature/flow.

Simple Example

import networkx as nx
from GraphRicciCurvature.OllivierRicci import OllivierRicci
from GraphRicciCurvature.FormanRicci import FormanRicci

print("\n- Import an example NetworkX karate club graph")
G = nx.karate_club_graph()

print("\n===== Compute the Ollivier-Ricci curvature of the given graph G =====")
# compute the Ollivier-Ricci curvature of the given graph G
orc = OllivierRicci(G, alpha=0.5, verbose="INFO")
orc.compute_ricci_curvature()
print("Karate Club Graph: The Ollivier-Ricci curvature of edge (0,1) is %f" % orc.G[0][1]["ricciCurvature"])

print("\n===== Compute the Forman-Ricci curvature of the given graph G =====")
frc = FormanRicci(G)
frc.compute_ricci_curvature()
print("Karate Club Graph: The Forman-Ricci curvature of edge (0,1) is %f" % frc.G[0][1]["formanCurvature"])

# -----------------------------------
print("\n=====  Compute Ricci flow metric - Optimal Transportation Distance =====")
G = nx.karate_club_graph()
orc_OTD = OllivierRicci(G, alpha=0.5, method="OTD", verbose="INFO")
orc_OTD.compute_ricci_flow(iterations=10)
print("\n=====  Compute Ricci community - by Ricci flow =====")
clustering = orc_OTD.ricci_community()

More example in example.py.

Reference

[1]Ni, C.-C., Lin, Y.-Y., Gao, J., Gu, X., and Saucan, E. 2015. Ricci curvature of the Internet topology (Vol. 26, pp. 2758–2766). Presented at the 2015 IEEE Conference on Computer Communications (INFOCOM), IEEE. [arXiv]
[2]Ni, C.-C., Lin, Y.-Y., Gao, J., and Gu, X. 2018. Network Alignment by Discrete Ollivier-Ricci Flow, Graph Drawing 2018, [arXiv]
[3](1, 2) Ni, C.-C., Lin, Y.-Y., Luo, F. and Gao, J. 2019. Community Detection on Networks with Ricci Flow, Scientific Reports, [arXiv]
[4]Sreejith, R. P., Karthikeyan Mohanraj, Jürgen Jost, Emil Saucan, and Areejit Samal. 2016. Forman Curvature for Complex Networks. Journal of Statistical Mechanics: Theory and Experiment 2016 (6). IOP Publishing: 063206. [arXiv]

Contact

Please contact [Chien-Chun Ni].

Cite

If you use this code in your research, please considering cite our paper:

@article{ni2019community,
  title={Community detection on networks with ricci flow},
  author={Ni, Chien-Chun and Lin, Yu-Yao and Luo, Feng and Gao, Jie},
  journal={Scientific reports},
  volume={9},
  number={1},
  pages={1--12},
  year={2019},
  publisher={Nature Publishing Group}
}

Indices and tables