Compute discrete Ricci curvatures and Ricci flow on NetworkX graphs.
Project description
GraphRicciCurvature
A Python library to compute Discrete Ricci curvature and Ricci flow on NetworkX graph.
This work computes the Ollivier-Ricci Curvature[Ni], Ollivier-Ricci Flow[Ni2,Ni3] and Forman-Ricci Curvature(or Forman curvature)[Sreejith].
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 negative curved surface like saddle, these two paths tend to be apart.
In [Ni], we observe that the edge Ricci curvature play an important role in graph structure. An edge with positive curvature represents an edge within a cluster, while a negatively curved edge tents 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 be act as a graph fingerprint for graph classification. Different graph gives different edge Ricci curvature distributions and different Ricci flow metric.
Video demonstration of Ricci flow for community detection:
Package Requirement
- NetworkX (Based Graph library)
- NetworKit > 6.01 (Pairwise bidirectional dijkstra algorithm)
- CVXPY (LP solver for Optimal transportation)
- NumPy (CVXPY support)
- POT (For approximate Optimal transportation distance)
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.
Getting Started
- See the jupyter notebook tutorial on nbviewer or github 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.
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)
More example in example.py.
Contact
Please contact Chien-Chun Ni.
Reference
[Ni]: 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
[Ni2]: Ni, C.-C., Lin, Y.-Y., Gao, J., and Gu, X. 2018. "Network Alignment by Discrete Ollivier-Ricci Flow", Graph Drawing 2018, arXiv
[Ni3]: Ni, C.-C., Lin, Y.-Y., Luo, F. and Gao, J. 2019. "Community Detection on Networks with Ricci Flow", Scientific Reports, arXiv
[Sreejith]: 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
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for GraphRicciCurvature-0.4.3.1.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3cb0fa60d6e8c8a458bef46dbc22e8237913d22462db367019282c3f08349ae1 |
|
MD5 | d8c7872bdf9e6b601168e4c3a4e16bf4 |
|
BLAKE2b-256 | 398be0facf600f5e8366017d950140f9def83463f789e95d220539219e645e6a |
Hashes for GraphRicciCurvature-0.4.3.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5b8c1c7eb1ef9c8be42f6811d1d22a0ffeb5151414618cdcb956dbc2dfe923a4 |
|
MD5 | 1670650cf8338f3cb12c1ae4f6f2efe5 |
|
BLAKE2b-256 | e48f3bc0d756b26073844ef51da8946ae3fcfbb97d8b2b370c23ac501c975675 |