Metadata-Version: 2.4
Name: orc-bound
Version: 0.1.1
Summary: Ollivier-Ricci Curvature (ORC) Lower Bounds via Residual-Shell Measures
Author-email: Xiang Gu <xianggu@xjtu.edu.cn>
License: MIT
Project-URL: Homepage, https://github.com/XJTU-XGU/ORC_bound
Project-URL: Documentation, https://orc-bound.readthedocs.io
Project-URL: Repository, https://github.com/XJTU-XGU/ORC_bound
Project-URL: Issues, https://github.com/XJTU-XGU/ORC_bound/issues
Keywords: graph curvature,Ricci curvature,optimal transport,Wasserstein distance,network analysis,random walk
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Topic :: Scientific/Engineering :: Artificial Intelligence
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.21.0
Requires-Dist: scipy>=1.7.0
Requires-Dist: networkx>=3.0
Provides-Extra: dev
Requires-Dist: pytest>=7.0.0; extra == "dev"
Requires-Dist: pytest-cov>=3.0.0; extra == "dev"
Requires-Dist: black>=22.0.0; extra == "dev"
Requires-Dist: ruff>=0.1.0; extra == "dev"
Provides-Extra: serpapi
Requires-Dist: google-search-results>=2.4.0; extra == "serpapi"
Provides-Extra: all
Requires-Dist: pytest>=7.0.0; extra == "all"
Requires-Dist: pytest-cov>=3.0.0; extra == "all"
Requires-Dist: black>=22.0.0; extra == "all"
Requires-Dist: ruff>=0.1.0; extra == "all"
Requires-Dist: google-search-results>=2.4.0; extra == "all"
Dynamic: license-file

# ORC-Bound

**ORC (Ollivier–Ricci Curvature) Lower Bounds** via residual-shell Wasserstein-1 measures with k-hop lazy random walks.

## Overview

This package implements lower bound algorithms for Ollivier–Ricci Curvature (ORC) on graph edges. For each edge `(u, v)` in a graph, it computes:

```
κ_lb(u, v) = 1 - W̄₁(μ_u, μ_v) / dist(u, v)
```

where `μ_u` is the k-hop lazy random walk measure at `u` and `W̄₁` is the residual-shell upper bound on the 1-Wasserstein distance.

## Features

- **Residual-shell Ricci curvature** with k-hop random walk support
- **Multi-threaded edge processing** — leverage all CPU cores for large graphs
- **Sparse matrix output** — memory efficient for large graphs
- **Truncated APSP** — avoids full all-pairs shortest path computation

## Installation

```bash
pip install .
```

For development:

```bash
pip install -e ".[dev]"
```

For SerpAPI support:

```bash
pip install -e ".[serpapi]"
```

## Quick Start

```python
import networkx as nx
from orc_bound import residual_shell_ricci_approximation

# Build a graph
G = nx.watts_strogatz_graph(200, 6, 0.2, seed=0)

# Compute curvature with k=1-hop measures and 4 threads
C = residual_shell_ricci_approximation(
    G,
    G.number_of_nodes(),
    k=1,
    n_jobs=4,
)

# Average curvature over all edges
avg_curv = C.sum() / C.nnz
print(f"Average curvature: {avg_curv:.4f}")
```

## API Reference

### `residual_shell_ricci_approximation`

```python
def residual_shell_ricci_approximation(
    graph: nx.Graph,
    num_nodes: int,
    k: int = 1,
    alpha_lazy: float = 0.0,
    l_shell: int = 3,
    rbar_mode: str = "local-max",
    tol: float = 1e-12,
    symmetric: bool = False,
    n_jobs: int | None = None,
) -> csr_matrix:
```

| Parameter     | Type           | Default  | Description                                           |
|---------------|----------------|---------- |-------------------------------------------------------|
| `graph`       | `nx.Graph`     | —         | Input graph                                           |
| `num_nodes`   | `int`          | —         | Number of nodes (must match graph)                    |
| `k`           | `int`          | `1`       | Number of random walk steps (k-hop neighborhood)      |
| `alpha_lazy`  | `float`        | `0.0`     | Lazy mixing parameter [0, 1]                          |
| `l_shell`     | `int`          | `3`       | Maximum shell distance for bucket matching            |
| `rbar_mode`   | `str`          | `"local-max"` | Residual distance estimation method              |
| `tol`         | `float`        | `1e-12`   | Numerical tolerance for mass pruning                  |
| `symmetric`   | `bool`         | `False`   | Whether to populate both (u,v) and (v,u) entries       |
| `n_jobs`      | `int \| None`  | `None`    | Number of parallel workers (None=all cores)           |

### Core Functions

- `build_lazy_measures_k(G, alpha_lazy, k)` — Build k-hop lazy random walk measures
- `all_pairs_shortest_path_matrix_cutoff(G, cutoff)` — Truncated APSP matrix
- `residual_shell_upper_bound(mu_x, mu_y, D, idx, l, ...)` — W1 upper bound

## Multi-Threading

The most expensive step — computing curvature for each edge — is fully parallelizable because each edge's computation is independent.

```python
# Use all CPU cores (default)
C = residual_shell_ricci_approximation(G, n, k=10)

# Use exactly 8 workers
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)
```

### Threading vs Multiprocessing

The algorithm is **memory-bandwidth bound** (dominated by numpy array operations on the precomputed distance matrix), not CPU-bound. Threading avoids the GIL for numpy operations and sidesteps the serialization overhead of multiprocessing, making `ThreadPoolExecutor` the natural choice.

## Web Search via SerpAPI

The package includes a utility for fetching related literature:

```python
from orc_bound.utils.search import search_orc_literature

# Search for ORC-related papers
results = search_orc_literature(
    query="Ollivier Ricci curvature graph networks",
    num_results=10,
    serpapi_key="your-serpapi-key",
)
```

## License

MIT License
