Compute discrete Ricci curvatures and Ricci flow on NetworkX graphs.
Project description
GraphRicciCurvature
Compute Discrete Ricci curvature and Ricci flow on NetworkX graph.
This work computes the OllivierRicci Curvature[Ni], OllivierRicci Flow[Ni2,Ni3] and FormanRicci 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. 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)

CVXPY (LP solver for Optimal transportation)

NumPy (CVXPY support)

POT (For approximate Optimal transportation distance)

NetworKit (Optional: for faster parallel shortest path computation)
Installation
Installing via pip
pip3 install [user] GraphRicciCurvature
Installing via pip (with NetworKit)
pip3 install [user] "GraphRicciCurvature [faster_apsp]"
 Notice that the NetworKit is not required. It is optional for faster all pair shortest path computation for larger graphs that NetworkX performs poorly. If the installation 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).
Simple Example
import networkx as nx from GraphRicciCurvature.OllivierRicci import OllivierRicci from GraphRicciCurvature.FormanRicci import FormanRicci # import an example NetworkX karate club graph G = nx.karate_club_graph() # compute the OllivierRicci curvature of the given graph G orc = OllivierRicci(G, alpha=0.5, verbose="INFO") orc.compute_ricci_curvature() print("Karate Club Graph: The OllivierRicci curvature of edge (0,1) is %f" % orc.G[0][1]["ricciCurvature"]) # compute the FormanRicci curvature of the given graph G frc = FormanRicci(G) frc.compute_ricci_curvature() print("Karate Club Graph: The FormanRicci curvature of edge (0,1) is %f" % frc.G[0][1]["formanCurvature"]) #  # 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 ChienChun 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 OllivierRicci 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
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size GraphRicciCurvature0.3.1.tar.gz (10.1 kB)  File type Source  Python version None  Upload date  Hashes View hashes 
Hashes for GraphRicciCurvature0.3.1.tar.gz
Algorithm  Hash digest  

SHA256  c6e4376d8b8feb5424fc9c134dbafc8b36d5b96710d0622a04632b3b84e32f88 

MD5  d2f3fc90a832dddc3aebf984a8a9acd4 

BLAKE2256  b554cc89dd3cceb34ef7ab4c5c33cd5e7eb9b7a8ff0035431ff1408bd90780b1 