ORC-Bound Documentation¶
ORC-Bound provides lower bound algorithms for Ollivier–Ricci Curvature (ORC) on graph edges, using residual-shell Wasserstein-1 upper bounds with k-hop lazy random walk measures.
Contents:
Quick Start¶
import networkx as nx
from orc_bound import residual_shell_ricci_approximation
G = nx.watts_strogatz_graph(200, 6, 0.2, seed=0)
C = residual_shell_ricci_approximation(G, G.number_of_nodes(), k=2, n_jobs=4)
print(f"Average curvature: {C.sum() / C.nnz:.4f}")
Basic Usage¶
Compute curvature for all edges of a graph and inspect the results:
import networkx as nx
from orc_bound import residual_shell_ricci_approximation
G = nx.karate_club_graph()
C = residual_shell_ricci_approximation(G, G.number_of_nodes())
# Average curvature over all edges
print(f"Average: {C.sum() / C.nnz:.4f}")
# All edge curvatures
for u, v in G.edges():
print(f"Edge ({u}, {v}): {C[u, v]:.4f}")
Choosing k — Number of Random Walk Steps¶
The parameter k controls how “global” the random walk measure is.
Larger k spreads mass further from the source node.
# k=1: local measure (neighbors only)
C1 = residual_shell_ricci_approximation(G, n, k=1)
# k=5: semi-global measure
C5 = residual_shell_ricci_approximation(G, n, k=5)
# k=20: near-uniform measure
C20 = residual_shell_ricci_approximation(G, n, k=20)
Lazy Mixing Parameter alpha¶
The alpha_lazy parameter controls the weight of the Dirac delta at the source node.
Higher alpha keeps more mass locally.
# alpha=0: pure random walk (mass spreads fully)
C0 = residual_shell_ricci_approximation(G, n, k=3, alpha_lazy=0.0)
# alpha=0.5: balanced
C5 = residual_shell_ricci_approximation(G, n, k=3, alpha_lazy=0.5)
# alpha=1: trivial delta measure (kappa = 0 for all edges)
C1 = residual_shell_ricci_approximation(G, n, k=3, alpha_lazy=1.0)
Multi-Threaded Parallel Computation¶
The most expensive step — computing curvature for each edge — is fully parallelizable.
Use n_jobs to control the number of worker threads.
# Use all available CPU cores (default)
C = residual_shell_ricci_approximation(G, n, k=10)
# Use exactly 8 threads
C = residual_shell_ricci_approximation(G, n, k=10, n_jobs=8)
# Use all but one core
C = residual_shell_ricci_approximation(G, n, k=10, n_jobs=-1)
Interpreting the Result Matrix¶
The return value is a scipy.sparse.csr_matrix. Non-zero entries correspond to graph edges.
# Basic statistics
print(f"Shape: {C.shape}") # (n, n)
print(f"Non-zeros: {C.nnz}") # equals number of edges
print(f"Average: {C.sum()/C.nnz:.4f}")
print(f"Min: {C.data.min():.4f}")
print(f"Max: {C.data.max():.4f}")
# Get all non-zero entries
for i in range(C.nnz):
u, v = C.row[i], C.col[i]
print(f"Edge ({u}, {v}): {C.data[i]:.4f}")
# Extract as dense array
dense = C.toarray()
Different Graph Types¶
import networkx as nx
from orc_bound import residual_shell_ricci_approximation
n = 200
# Watts-Strogatz (small-world)
G_sw = nx.watts_strogatz_graph(n, 8, 0.1, seed=0)
C_sw = residual_shell_ricci_approximation(G_sw, n, k=3)
print(f"Watts-Strogatz avg: {C_sw.sum()/C_sw.nnz:.4f}")
# Barabási–Albert (scale-free)
G_sf = nx.barabasi_albert_graph(n, 3, seed=0)
C_sf = residual_shell_ricci_approximation(G_sf, n, k=3)
print(f"Barabási–Albert avg: {C_sf.sum()/C_sf.nnz:.4f}")
# 2D Grid (regular lattice)
G_lat = nx.grid_2d_graph(10, 10)
G_lat = nx.convert_node_labels_to_integers(G_lat)
C_lat = residual_shell_ricci_approximation(G_lat, G_lat.number_of_nodes(), k=2)
print(f"Lattice avg: {C_lat.sum()/C_lat.nnz:.4f}")
# Erdős–Rényi (random)
G_er = nx.erdos_renyi_graph(n, 0.05, seed=0)
C_er = residual_shell_ricci_approximation(G_er, n, k=3)
print(f"Erdős–Rényi avg: {C_er.sum()/C_er.nnz:.4f}")
Using Core Functions Directly¶
For fine-grained control, call the core functions step by step:
import networkx as nx
from orc_bound import (
build_lazy_measures_k,
all_pairs_shortest_path_matrix_cutoff,
residual_shell_upper_bound,
)
G = nx.path_graph(20)
n = G.number_of_nodes()
# Step 1: Build k-hop measures
mu = build_lazy_measures_k(G, alpha_lazy=0.0, k=3)
# Step 2: Precompute distance matrix (cutoff = 2*k + 1)
cutoff = 2 * 3 + 1
nodes, idx, D = all_pairs_shortest_path_matrix_cutoff(G, cutoff=cutoff)
# Step 3: Compute W1 upper bound for a specific edge
ub, m_r, Rl, rbar = residual_shell_upper_bound(
mu[0], mu[1], D, idx,
l=3,
rbar_mode="local-max",
tol=1e-12,
)
print(f"W1 upper bound: {ub:.4f}")
print(f"Mass per bucket: {m_r}")
print(f"Residual mass: {Rl:.4f}, residual distance: {rbar:.1f}")