GraphRicciCurvature

You can install the library using pip3. Note that from version 0.4.0 onwards, NetworKit is a required dependency for computing shortest paths for density distribution. If NetworKit installation fails, you may need to follow its specific installation instructions.

pip3 install [--user] GraphRicciCurvature

To ensure the best performance and access the latest features, upgrade the package using the --upgrade flag.

pip3 install [--user] --upgrade GraphRicciCurvature

If ricci_community or standard Ricci flow does not yield high-quality community detection (e.g., low ARI or Modularity), consider the following tuning strategies:

1. Increase Ricci flow iterations: Some graphs require more than the default 10 iterations to capture community structure. Try 20 to 50 iterations.
2. Tune exp_power: Increasing exp_power (e.g., to 1 or 2) puts more focus on neighbors with larger weights during optimal transportation. Setting exp_power=2 is often effective for real-world graphs.
3. Manual Surgery: Instead of relying on automatic cutoffs, manually inspect the edge weight histogram and remove edges with weights above a specific threshold to see how it affects Modularity and the Adjusted Rand Index (ARI).

To use the library, install it along with scikit-learn using pip:

!pip install GraphRicciCurvature
!pip install scikit-learn

To compute the Ollivier-Ricci curvature, use the OllivierRicci class. The curvature values are stored as edge attributes in the NetworkX graph under the key "ricciCurvature".

Parameters:

• G: The NetworkX graph.
• alpha: Curvature parameter (e.g., 0.5).
• method: Set to "OTD" to compute the Ricci flow metric via Optimal Transportation Distance.
• verbose: Logging level (e.g., "INFO").

import networkx as nx
from GraphRicciCurvature.OllivierRicci import OllivierRicci

G = nx.karate_club_graph()
# Initialize and compute
orc = OllivierRicci(G, alpha=0.5, verbose="INFO")
orc.compute_ricci_curvature()

# Access the curvature of a specific edge
curvature = orc.G[0][1]["ricciCurvature"]

Ricci flow uniformizes edge Ricci curvature. You can compute the Ricci flow metric (using Optimal Transportation Distance) and subsequently detect communities using the ricci_community() method.

Steps:

1. Initialize OllivierRicci with method="OTD".
2. Call compute_ricci_flow(iterations=...).
3. Call ricci_community() to get the clustering results.

import networkx as nx
from GraphRicciCurvature.OllivierRicci import OllivierRicci

G = nx.karate_club_graph()
# Initialize with OTD method
orc_OTD = OllivierRicci(G, alpha=0.5, method="OTD", verbose="INFO")

# Compute Ricci flow
orc_OTD.compute_ricci_flow(iterations=10)

# Detect communities
clustering = orc_OTD.ricci_community()

When using OllivierRicci, you can tune the probability distribution used for optimal transportation to improve community detection results. This is done via the following parameters:

• alpha: The share of mass to leave on the original node. Range: [0, 1]. Default: 0.5.
• base: Base variable for weight distribution. Default: math.e.
• exp_power: Exponential power for weight distribution. Higher values focus more on neighbors with larger weights. Default: 0.
• method: Transportation method. Options: "OTD" (Optimal Transportation Distance), "ATD" (Average Transportation Distance), or "Sinkhorn" (Approximated Sinkhorn distance, faster). Default: "Sinkhorn".

The following packages are required for GraphRicciCurvature to function:

• NetworkX >= 2.0 (Base graph library)
• NetworKit >= 6.1 (Required for shortest path algorithms in version 0.4.0+)
• NumPy (POT support)
• POT (For optimal transportation distance)
• python-louvain (For faster modularity computation)