Graph Ricci Curvature

https://graphriccicurvature.readthedocs.io/en/v0.5.1/
Admin
Graph Ricci Curvature is a Python library that computes Ollivier-Ricci curvature, Forman-Ricci...
Tokens:26,693
Snippets:162
Trust Score:9.6
Update:6 months ago
Show doc for...
Tokens:
Raw
### Install GraphRicciCurvature via pip

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/index.html

Standard command to install the package using pip.

```bash
pip3 install [--user] GraphRicciCurvature
```

--------------------------------

### Install and Import Dependencies

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Install the necessary packages and import libraries for graph analysis, visualization, and logging.

```python
# # colab setting
!pip install GraphRicciCurvature
!pip install scikit-learn

import networkx as nx
import numpy as np
import math
import importlib

# matplotlib setting
%matplotlib inline
import matplotlib.pyplot as plt

# to print logs in jupyter notebook
import logging
logging.basicConfig(format='%(levelname)s:%(message)s', level=logging.ERROR)

# load GraphRicciCuravture package
from GraphRicciCurvature.OllivierRicci import OllivierRicci

# load python-louvain for modularity computation
import community as community_louvain

# for ARI computation
from sklearn import preprocessing, metrics
```

--------------------------------

### Example: Compute Ollivier-Ricci Curvature

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Example demonstrating how to compute the Ollivier-Ricci curvature for the karate club graph using NetworkX.

```python
G = nx.karate_club_graph()
orc = OllivierRicci(G, alpha=0.5, verbose="INFO")
orc.compute_ricci_curvature()
orc.G[0][1]
```

--------------------------------

### Example: Compute Ricci Flow

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Example demonstrating how to compute the Ollivier-Ricci flow for the karate club graph using NetworkX.

```python
G = nx.karate_club_graph()
orc_OTD = OllivierRicci(G, alpha=0.5, method="OTD", verbose="INFO")
orc_OTD.compute_ricci_flow(iterations=10)
orc_OTD.G[0][1]
```

--------------------------------

### Example: Detect Community Clustering

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Example demonstrating how to detect community clustering using Ricci flow for the karate club graph.

```python
G = nx.karate_club_graph()
orc = OllivierRicci(G, alpha=0.5, verbose="INFO")
orc.compute_ricci_flow(iterations=50)
cc = orc.ricci_community()
print("The detected community label of node 0: %s" % cc[1][0])
```

--------------------------------

### OllivierRicci Computation Example

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Example of computing Ricci flow using OllivierRicci and displaying results.

```APIDOC
## OllivierRicci Computation Example

### Description
This example demonstrates how to initialize OllivierRicci, compute the Ricci flow, and display the results on a graph.

### Method
POST

### Endpoint
/compute_ricci_flow

### Request Body
```json
{
  "graph": "G",
  "alpha": 0.5,
  "base": "math.e",
  "exp_power": 1,
  "verbose": "ERROR",
  "iterations": 50
}
```

### Response
#### Success Response (200)
- **G_rf2** (Graph) - The graph object after computing Ricci flow.

### Request Example
```python
orf2 = OllivierRicci(G, alpha=0.5, base=math.e, exp_power=1, verbose="ERROR")
orf2.compute_ricci_flow(iterations=50)
G_rf2 = orf2.G.copy()
show_results(G_rf2)
```

### Response Example
```
Karate Club Graph, first 5 edges:
Ollivier-Ricci curvature of edge (0,1) is -0.019430
Ollivier-Ricci curvature of edge (0,2) is -0.012186
Ollivier-Ricci curvature of edge (0,3) is -0.016822
Ollivier-Ricci curvature of edge (0,4) is -0.020180
Ollivier-Ricci curvature of edge (0,5) is -0.020298
```
```

--------------------------------

### Compute Ollivier-Ricci Curvature

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/GraphRicciCurvature.html

Example showing how to initialize the OllivierRicci class and compute curvature for a karate club graph.

```python
>>> G = nx.karate_club_graph()
>>> orc = OllivierRicci(G, alpha=0.5, verbose="INFO")
>>> orc.compute_ricci_curvature()
>>> orc.G[0][1]
{'weight': 1.0, 'ricciCurvature': 0.11111111071683011}
```

--------------------------------

### Compute Forman-Ricci curvature for a graph

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/GraphRicciCurvature.html

Example showing the initialization of the FormanRicci class and the computation of curvature for the karate club graph.

```python
>>> G = nx.karate_club_graph()
>>> frc = FormanRicci(G)
>>> frc.compute_ricci_curvature()
>>> frc.G[0][1]
{'formanCurvature': 0}
```

--------------------------------

### Accuracy Check Example

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Example of checking the accuracy of community detection using the check_accuracy function.

```APIDOC
## Accuracy Check Example

### Description
This example shows how to use `check_accuracy` to evaluate community detection results, often used in conjunction with Ricci curvature computations.

### Method
POST

### Endpoint
/check_accuracy

### Request Body
```json
{
  "graph": "G_rf2",
  "clustering_label": "club"
}
```

### Response
#### Success Response (200)
- **accuracy_metrics** (dict) - Dictionary containing accuracy metrics like modularity, ARI, etc.

### Request Example
```python
check_accuracy(G_rf2, clustering_label="club")
```

### Response Example
```
*Good Cut:1.108158, diff:0.013447, mod_now:0.342205, mod_last:0.355652, ari:0.590553
```
```

--------------------------------

### Load Graph for Fine-tuning Ricci Community Detection

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Loads a graph from a GEXF file for fine-tuning community detection. This example uses the polbooks dataset.

```python
G_polbooks_raw = nx.read_gexf(urlopen("https://raw.githubusercontent.com/saibalmars/RicciFlow-SampleGraphs/master/polbooks_rf_sinkhorn_e2_20.gexf"))
G_polbooks = G_polbooks_raw.copy()
```

--------------------------------

### Compute Ollivier-Ricci Flow

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/GraphRicciCurvature.html

Example showing how to compute the Ricci flow metric for a karate club graph using the OTD method.

```python
>>> G = nx.karate_club_graph()
>>> orc_OTD = OllivierRicci(G, alpha=0.5, method="OTD", verbose="INFO")
>>> orc_OTD.compute_ricci_flow(iterations=10)
>>> orc_OTD.G[0][1]
```

--------------------------------

### GET /internal/density-distributions

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Computes density distributions for source and target nodes and the shortest path matrix between their neighbors.

```APIDOC
## GET /internal/density-distributions

### Description
Computes the density distributions of source and target nodes, and the cost (shortest paths) between all source and target neighbors.

### Parameters
#### Query Parameters
- **source** (int) - Required - Source node index.
- **target** (int) - Required - Target node index.

### Response
#### Success Response (200)
- **x** (numpy.ndarray) - Source's density distributions.
- **y** (numpy.ndarray) - Target's density distributions.
- **d** (numpy.ndarray) - Shortest path matrix.
```

--------------------------------

### GET /internal/shortest-path

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Computes the pairwise shortest path between two nodes using Bidirectional Dijkstra.

```APIDOC
## GET /internal/shortest-path

### Description
Computes pairwise shortest path from source to target using BidirectionalDijkstra via Networkit.

### Parameters
#### Query Parameters
- **source** (int) - Required - Source node index.
- **target** (int) - Required - Target node index.

### Response
#### Success Response (200)
- **length** (float) - Pairwise shortest path length.
```

--------------------------------

### Compute Ricci Community

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Automatically computes Ricci flow for 20 iterations and then detects communities. This is a convenient method to get community detection results directly.

```python
cc = orc_polbooks.ricci_community()
```

--------------------------------

### Get Single Node Neighbor Distributions

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Calculates the neighbor density distribution for a given node in a Networkit graph. Handles directed and undirected graphs, and considers edge weights for distribution. Returns distributions and neighbor indices.

```python
import heapq
import networkit as nk
from functools import lru_cache

_cache_maxsize = 1000
_nbr_topk = 10
_base = 10
_exp_power = 2
_alpha = 0.1
EPSILON = 1e-9
logger = None
_Gk = None

@lru_cache(_cache_maxsize)
def _get_single_node_neighbors_distributions(node, direction="successors"):
    """Get the neighbor density distribution of given node `node`.

    Parameters
    ----------
    node : int
        Node index in Networkit graph `_Gk`.
    direction : {"predecessors", "successors"}
        Direction of neighbors in directed graph. (Default value: "successors")

    Returns
    -------    distributions : lists of float
        Density distributions of neighbors up to top `_nbr_topk` nodes.
    nbrs : lists of int
        Neighbor index up to top `_nbr_topk` nodes.

    """
    if _Gk.isDirected():
        if direction == "predecessors":
            neighbors = _Gk.inNeighbors(node)
        else:  # successors
            neighbors = _Gk.neighbors(node)
    else:
        neighbors = _Gk.neighbors(node)

    # Get sum of distributions from x's all neighbors
    heap_weight_node_pair = []
    for nbr in neighbors:
        if direction == "predecessors":
            w = _base ** (-_Gk.weight(nbr, node) ** _exp_power)
        else:  # successors
            w = _base ** (-_Gk.weight(node, nbr) ** _exp_power)

        if len(heap_weight_node_pair) < _nbr_topk:
            heapq.heappush(heap_weight_node_pair, (w, nbr))
        else:
            heapq.heappushpop(heap_weight_node_pair, (w, nbr))

    nbr_edge_weight_sum = sum([x[0] for x in heap_weight_node_pair])

    if len(neighbors) == 0:
        # No neighbor, all mass stay at node
        return [1], [node]
    elif nbr_edge_weight_sum > EPSILON:
        # Sum need to be not too small to prevent divided by zero
        distributions = [(1.0 - _alpha) * w / nbr_edge_weight_sum for w, _ in heap_weight_node_pair]
    else:
        # Sum too small, just evenly distribute to every neighbors
        logger.warning("Neighbor weight sum too small, list:", heap_weight_node_pair)
        distributions = [(1.0 - _alpha) / len(heap_weight_node_pair)] * len(heap_weight_node_pair)

    nbr = [x[1] for x in heap_weight_node_pair]
    return distributions + [_alpha], nbr + [node]
```

--------------------------------

### Load Sample Graph

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Load the Zachary's Karate Club graph from NetworkX and display its basic information.

```python
G = nx.karate_club_graph()
```

```python
print(nx.info(G))
```

--------------------------------

### Initialize OllivierRicci for Curvature Computation

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Initialize the OllivierRicci class with a graph and curvature parameters. Use verbose='TRACE' for detailed computation logs.

```python
orc = OllivierRicci(G, alpha=0.5, verbose="TRACE")
```

--------------------------------

### Initialize OllivierRicci

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Initialize the OllivierRicci calculator with a graph. Set verbose to 'INFO' to see computation details.

```python
orc_polbooks = OllivierRicci(G_polbooks,verbose="INFO")
```

--------------------------------

### GET /internal/node-neighbors-distribution

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Retrieves the neighbor density distribution for a specific node in the graph.

```APIDOC
## GET /internal/node-neighbors-distribution

### Description
Calculates the neighbor density distribution of a given node, considering either predecessors or successors in a directed graph.

### Parameters
#### Query Parameters
- **node** (int) - Required - Node index in Networkit graph.
- **direction** (string) - Optional - Direction of neighbors in directed graph ("predecessors" or "successors"). Default is "successors".

### Response
#### Success Response (200)
- **distributions** (list of float) - Density distributions of neighbors.
- **nbrs** (list of int) - Neighbor indices.
```

--------------------------------

### Initialize OllivierRicci with Custom exp_power

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Configures the OllivierRicci object with a specific exponential power and computes the community structure.

```python
orc_polbooks1 = OllivierRicci(G_polbooks,exp_power=1,verbose="ERROR")
cc1 = orc_polbooks1.ricci_community()
```

--------------------------------

### GraphRicciCurvature.util Methods

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/genindex.html

This section details the utility functions available in the GraphRicciCurvature library.

```APIDOC
## GET /methods/util

### Description
Retrieves information about utility functions.

### Method
GET

### Endpoint
/methods/util

### Parameters
None

### Request Example
None

### Response
#### Success Response (200)
- **methods** (array) - A list of available utility functions.
  - **name** (string) - The name of the function.
  - **description** (string) - A brief description of the function.

#### Response Example
{
  "methods": [
    {
      "name": "cut_graph_by_cutoff",
      "description": "Cuts a graph based on a cutoff value."
    },
    {
      "name": "get_rf_metric_cutoff",
      "description": "Gets the Ricci flow metric cutoff value."
    },
    {
      "name": "set_verbose",
      "description": "Sets the verbosity level for utility functions."
    }
  ]
}
```

--------------------------------

### Import necessary libraries for GraphRicciCurvature

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Imports required libraries including heapq, importlib, math, multiprocessing, time, functools, cvxpy, networkit, networkx, numpy, and ot. Also imports utility functions from the current package.

```python
import heapq
import importlib
import math
import multiprocessing as mp
import time
from functools import lru_cache

import cvxpy as cvx
import networkit as nk
import networkx as nx
import numpy as np
import ot

from .util import logger, set_verbose, cut_graph_by_cutoff, get_rf_metric_cutoff
```

--------------------------------

### Distribute Densities for Source and Target Nodes

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Calculates density distributions for source and target nodes, and the shortest path costs between their neighbors. Supports directed and undirected graphs, and different shortest path algorithms.

```python
import time
import numpy as np

_shortest_path = "pairwise"
_apsp = None

def _distribute_densities(source, target):
    """Get the density distributions of source and target node, and the cost (all pair shortest paths) between
    all source's and target's neighbors. Notice that only neighbors with top `_nbr_topk` edge weights.

    Parameters
    ----------
    source : int
        Source node index in Networkit graph `_Gk`.
    target : int
        Target node index in Networkit graph `_Gk`.
    Returns
    -------    x : (m,) numpy.ndarray
        Source's density distributions, includes source and source's neighbors.
    y : (n,) numpy.ndarray
        Target's density distributions, includes source and source's neighbors.
    d : (m, n) numpy.ndarray
        Shortest path matrix.

    """

    # Distribute densities for source and source's neighbors as x
    t0 = time.time()

    if _Gk.isDirected():
        x, source_topknbr = _get_single_node_neighbors_distributions(source, "predecessors")
    else:
        x, source_topknbr = _get_single_node_neighbors_distributions(source, "successors")

    # Distribute densities for target and target's neighbors as y
    y, target_topknbr = _get_single_node_neighbors_distributions(target, "successors")

    logger.debug("%8f secs density distribution for edge." % (time.time() - t0))

    # construct the cost dictionary from x to y
    t0 = time.time()

    if _shortest_path == "pairwise":
        d = []
        for src in source_topknbr:
            tmp = []
            for tgt in target_topknbr:
                tmp.append(_source_target_shortest_path(src, tgt))
            d.append(tmp)
        d = np.array(d)
    else:  # all_pairs
        d = _apsp[np.ix_(source_topknbr, target_topknbr)]  # transportation matrix

    x = np.array([x]).T  # the mass that source neighborhood initially owned
    y = np.array([y]).T  # the mass that target neighborhood needs to received

    logger.debug("%8f secs density matrix construction for edge." % (time.time() - t0))

    return x, y, d
```

--------------------------------

### OllivierRicci Class Initialization

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/GraphRicciCurvature.html

Initializes a container to compute Ollivier-Ricci curvature/flow for a given NetworkX graph.

```APIDOC
## OllivierRicci Class

### Description
A class to compute the Ollivier-Ricci curvature of a given NetworkX graph.

### Method
__init__

### Parameters
#### Path Parameters
- **G** (NetworkX graph) - Required - A given directional or undirectional NetworkX graph.
- **weight** (str) - Optional - The edge weight used to compute Ricci curvature. (Default value = "weight")
- **alpha** (float) - Optional - The parameter for the discrete Ricci curvature, range from 0 ~ 1. It means the share of mass to leave on the original node. E.g. x -> y, alpha = 0.4 means 0.4 for x, 0.6 to evenly spread to x’s nbr. (Default value = 0.5)
- **method** ({"OTD", "ATD", "Sinkhorn"}) - Optional - The optimal transportation distance computation method. (Default value = "Sinkhorn")
  Transportation method:
    * "OTD" for Optimal Transportation Distance,
    * "ATD" for Average Transportation Distance.
    * "Sinkhorn" for OTD approximated Sinkhorn distance. (faster)
- **base** (float) - Optional - Base variable for weight distribution. (Default value = math.e)
- **exp_power** (float) - Optional - Exponential power for weight distribution. (Default value = 2)
- **proc** (int) - Optional - Number of processor used for multiprocessing. (Default value = cpu_count())
- **chunksize** (int) - Optional - Chunk size for multiprocessing, set None for auto decide. (Default value = None)
- **shortest_path** ({"all_pairs", "pairwise"}) - Optional - Method to compute shortest path. (Default value = all_pairs)
- **cache_maxsize** (int) - Optional - Max size for LRU cache for pairwise shortest path computation. Set this to None for unlimited cache. (Default value = 1000000)
- **nbr_topk** (int) - Optional - Only take the top k edge weight neighbors for density distribution. Smaller k run faster but the result is less accurate. (Default value = 1000)
- **verbose** ({"INFO", "TRACE", "DEBUG", "ERROR"}) - Optional - Verbose level. (Default value = "ERROR")
  * "INFO": show only iteration process log.
  * "TRACE": show detailed iteration process log.
  * "DEBUG": show all output logs.
  * "ERROR": only show log if error happened.

### Request Example
```python
import networkx as nx
from graphriccicurvature.OllivierRicci import OllivierRicci

G = nx.karate_club_graph()
orc = OllivierRicci(G, alpha=0.5, verbose="INFO")
```
```

--------------------------------

### Initialize OllivierRicci Container

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Constructor for the OllivierRicci class. Requires the Python Optimal Transport (POT) package if using the Sinkhorn method.

```python
class OllivierRicci:
    """A class to compute Ollivier-Ricci curvature for all nodes and edges in G.
    Node Ricci curvature is defined as the average of all it's adjacency edge.

    """


[docs]    def __init__(self, G: nx.Graph, weight="weight", alpha=0.5, method="Sinkhorn",
                 base=math.e, exp_power=2, proc=mp.cpu_count(), chunksize=None, shortest_path="all_pairs",
                 cache_maxsize=1000000,
                 nbr_topk=1000, verbose="ERROR"):
        """Initialized a container to compute Ollivier-Ricci curvature/flow.

        Parameters
        ----------
        G : NetworkX graph
            A given directional or undirectional NetworkX graph.
        weight : str
            The edge weight used to compute Ricci curvature. (Default value = "weight")
        alpha : float
            The parameter for the discrete Ricci curvature, range from 0 ~ 1.
            It means the share of mass to leave on the original node.
            E.g. x -> y, alpha = 0.4 means 0.4 for x, 0.6 to evenly spread to x's nbr.
            (Default value = 0.5)
        method : {"OTD", "ATD", "Sinkhorn"}
            The optimal transportation distance computation method. (Default value = "Sinkhorn")

            Transportation method:
                - "OTD" for Optimal Transportation Distance,
                - "ATD" for Average Transportation Distance.
                - "Sinkhorn" for OTD approximated Sinkhorn distance. (faster)
        base : float
            Base variable for weight distribution. (Default value = `math.e`)
        exp_power : float
            Exponential power for weight distribution. (Default value = 2)
        proc : int
            Number of processor used for multiprocessing. (Default value = `cpu_count()`)
        chunksize : int
            Chunk size for multiprocessing, set None for auto decide. (Default value = `None`)
        shortest_path : {"all_pairs","pairwise"}
            Method to compute shortest path. (Default value = "all_pairs")
        cache_maxsize : int
            Max size for LRU cache for pairwise shortest path computation.
            Set this to `None` for unlimited cache. (Default value = 1000000)
        nbr_topk : int
            Only take the top k edge weight neighbors for density distribution.
            Smaller k run faster but the result is less accurate. (Default value = 1000)
        verbose : {"INFO", "TRACE","DEBUG","ERROR"}
            Verbose level. (Default value = "ERROR")
                - "INFO": show only iteration process log.
                - "TRACE": show detailed iteration process log.
                - "DEBUG": show all output logs.
                - "ERROR": only show log if error happened.

        """
        self.G = G.copy()
        self.alpha = alpha
        self.weight = weight
        self.method = method
        self.base = base
        self.exp_power = exp_power
        self.proc = proc
        self.chunksize = chunksize
        self.cache_maxsize = cache_maxsize
        self.shortest_path = shortest_path
        self.nbr_topk = nbr_topk

        self.set_verbose(verbose)
        self.lengths = {}  # all pair shortest path dictionary
        self.densities = {}  # density distribution dictionary

        assert importlib.util.find_spec("ot"), \
            "Package POT: Python Optimal Transport is required for Sinkhorn distance."
```

--------------------------------

### OllivierRicci Initialization

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Initializes a container to compute Ollivier-Ricci curvature/flow for a given NetworkX graph.

```APIDOC
## OllivierRicci

### Description
A class to compute Ollivier-Ricci curvature for all nodes and edges in G. Node Ricci curvature is defined as the average of all its adjacency edge.

### Method
__init__

### Parameters
#### Path Parameters
- **G** (nx.Graph) - Required - A given directional or undirectional NetworkX graph.
- **weight** (str) - Optional - The edge weight used to compute Ricci curvature. (Default value = "weight")
- **alpha** (float) - Optional - The parameter for the discrete Ricci curvature, range from 0 ~ 1. It means the share of mass to leave on the original node. E.g. x -> y, alpha = 0.4 means 0.4 for x, 0.6 to evenly spread to x's nbr. (Default value = 0.5)
- **method** (str) - Optional - The optimal transportation distance computation method. (Default value = "Sinkhorn"). Options: {"OTD", "ATD", "Sinkhorn"}
- **base** (float) - Optional - Base variable for weight distribution. (Default value = `math.e`)
- **exp_power** (float) - Optional - Exponential power for weight distribution. (Default value = 2)
- **proc** (int) - Optional - Number of processor used for multiprocessing. (Default value = `cpu_count()`)
- **chunksize** (int) - Optional - Chunk size for multiprocessing, set None for auto decide. (Default value = `None`)
- **shortest_path** (str) - Optional - Method to compute shortest path. (Default value = `all_pairs`). Options: {"all_pairs","pairwise"}
- **cache_maxsize** (int) - Optional - Max size for LRU cache for pairwise shortest path computation. Set this to `None` for unlimited cache. (Default value = 1000000)
- **nbr_topk** (int) - Optional - Only take the top k edge weight neighbors for density distribution. Smaller k run faster but the result is less accurate. (Default value = 1000)
- **verbose** (str) - Optional - Verbose level. (Default value = "ERROR"). Options: {"INFO", "TRACE","DEBUG","ERROR"}

### Request Example
```python
import networkx as nx
import math
import multiprocessing as mp

G = nx.DiGraph()
G.add_edge(1, 2, weight=1.0)

ollivier_ricci = OllivierRicci(G, weight='weight', alpha=0.5, method='Sinkhorn', base=math.e, exp_power=2, proc=mp.cpu_count(), chunksize=None, shortest_path='all_pairs', cache_maxsize=1000000, nbr_topk=1000, verbose='ERROR')
```

### Response
#### Success Response (200)
- **self.G** (nx.Graph) - The input graph.
- **self.alpha** (float) - The alpha parameter for curvature computation.
- **self.weight** (str) - The edge weight attribute name.
- **self.method** (str) - The optimal transportation distance method.
- **self.base** (float) - The base for weight distribution.
- **self.exp_power** (float) - The exponential power for weight distribution.
- **self.proc** (int) - The number of processors for multiprocessing.
- **self.chunksize** (int) - The chunk size for multiprocessing.
- **self.cache_maxsize** (int) - The cache size for shortest path computation.
- **self.shortest_path** (str) - The method for shortest path computation.
- **self.nbr_topk** (int) - The number of top neighbors to consider.
- **self.lengths** (dict) - Dictionary to store shortest path lengths.
- **self.densities** (dict) - Dictionary to store density distributions.

#### Response Example
```json
{
  "message": "OllivierRicci object initialized successfully."
}
```
```

--------------------------------

### Initialize FormanRicci Class

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/FormanRicci.html

Initializes the FormanRicci class with a NetworkX graph and sets the verbosity level for logging. The graph is copied to avoid modifying the original.

```python
from .util import logger, set_verbose



class FormanRicci:

    def __init__(self, G, verbose="ERROR"):
        """A class to compute Forman-Ricci curvature for all nodes and edges in G.

        Parameters
        ----------
        G : NetworkX graph
            A given NetworkX graph, unweighted graph only for now, edge weight will be ignored.
        verbose: {"INFO","DEBUG","ERROR"}
            Verbose level. (Default value = "ERROR")
                - "INFO": show only iteration process log.
                - "DEBUG": show all output logs.
                - "ERROR": only show log if error happened.
        """

        self.G = G.copy()
        set_verbose(verbose)
```

--------------------------------

### Initialize OllivierRicci for Ricci Flow Computation

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Initialize the OllivierRicci class with specific parameters for Ricci flow, including base, exponent power, and number of processes. Verbose level can be set to 'INFO'.

```python
# Start a Ricci flow with Lin-Yau's probability distribution setting with 4 process.
orf = OllivierRicci(G, alpha=0.5, base=1, exp_power=0, proc=4, verbose="INFO")

# Do Ricci flow for 2 iterations
orf.compute_ricci_flow(iterations=2)
```

--------------------------------

### Compute Ricci community for a graph

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Demonstrates how to initialize the OllivierRicci object, compute the Ricci flow, and extract all possible community clusterings for the karate club graph.

```python
>>> G = nx.karate_club_graph()
>>> orc = OllivierRicci(G, alpha=0.5, verbose="INFO")
>>> orc.compute_ricci_flow(iterations=50)
>>> cc = orc.ricci_community_all_possible_clusterings()
>>> print("The number of possible clusterings: %d" % len(cc))
The number of possible clusterings: 3
```

--------------------------------

### Initialize OllivierRicci for Graph

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Initializes the OllivierRicci class with a graph object. Use this to set up Ricci curvature computations.

```python
orc_football = OllivierRicci(G_football,verbose="INFO")
```

--------------------------------

### Load Football Graph from URL

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Loads a graph dataset from a specified URL using the GEXF format. This is typically used for loading benchmark datasets with known community structures.

```python
G_football_raw = nx.read_gexf(urlopen("https://raw.githubusercontent.com/saibalmars/RicciFlow-SampleGraphs/master/football_rf_sinkhorn_e2_20.gexf"))
G_football = G_football_raw.copy()
```

--------------------------------

### Upgrade GraphRicciCurvature via pip

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/index.html

Command to update the package to the latest version.

```bash
pip3 install [--user] --upgrade GraphRicciCurvature
```

--------------------------------

### FormanRicci Class Initialization

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/GraphRicciCurvature.html

Initializes the FormanRicci class to compute Forman-Ricci curvature for a given NetworkX graph.

```APIDOC
## FormanRicci Class

### Description
A class to compute the Forman-Ricci curvature of a given NetworkX graph.

### Method
__init__

### Parameters
#### Path Parameters
- **G** (NetworkX graph) - Required - A given NetworkX graph, unweighted graph only for now, edge weight will be ignored.
- **verbose** (string) - Optional - Verbose level. Options: "INFO", "DEBUG", "ERROR". Default: "ERROR".
  - "INFO": show only iteration process log.
  - "DEBUG": show all output logs.
  - "ERROR": only show log if error happened.

### Request Example
```python
import networkx as nx
from GraphRicciCurvature.FormanRicci import FormanRicci

G = nx.karate_club_graph()
frc = FormanRicci(G, verbose="INFO")
```

### Response
#### Success Response (200)
- **G** (NetworkX graph) - The initialized graph object with potential attributes.

#### Response Example
```python
# No direct response example for initialization, but the object `frc` is created.
```
```

--------------------------------

### Graph Surgery and Drawing

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Demonstrates using 'my_surgery' to cut a graph based on a cutoff value and then drawing the resulting graph.

```APIDOC
## Graph Surgery and Drawing

### Description
This example illustrates how to modify a graph using `my_surgery` with a specified cutoff value and then visualize the modified graph.

### Method
POST

### Endpoint
/surgery

### Request Body
```json
{
  "graph": "G_rf2",
  "cut": 3.88
}
```

### Response
#### Success Response (200)
- **modified_graph** (Graph) - The graph after applying the surgery operation.

### Request Example
```python
draw_graph(my_surgery(G_rf2, cut=3.88))
```

### Response Example
```
*************** Surgery time ****************
* Cut 10 edges.
* Number of nodes now: 34
* Number of edges now: 68
* Modularity now: 0.499999
* ARI now: 0.771626
*********************************************
```
```

--------------------------------

### GraphRicciCurvature.OllivierRicci Methods

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/genindex.html

This section details the methods available within the OllivierRicci module for computing Ricci curvature.

```APIDOC
## GET /methods/ollivierricci

### Description
Retrieves information about Ollivier Ricci curvature computation methods.

### Method
GET

### Endpoint
/methods/ollivierricci

### Parameters
None

### Request Example
None

### Response
#### Success Response (200)
- **methods** (array) - A list of available Ollivier Ricci methods.
  - **name** (string) - The name of the method.
  - **description** (string) - A brief description of the method.

#### Response Example
{
  "methods": [
    {
      "name": "compute_ricci_curvature_edges",
      "description": "Computes Ricci curvature for edges."
    },
    {
      "name": "compute_ricci_flow",
      "description": "Applies the Ricci flow algorithm."
    },
    {
      "name": "ricci_community",
      "description": "Identifies communities using Ricci curvature."
    },
    {
      "name": "ricci_community_all_possible_clusterings",
      "description": "Finds all possible clusterings based on Ricci curvature."
    },
    {
      "name": "set_verbose",
      "description": "Sets the verbosity level for Ollivier Ricci computations."
    }
  ]
}
```

--------------------------------

### FormanRicci Class Initialization

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/FormanRicci.html

Initializes the FormanRicci class with a NetworkX graph and a verbosity level.

```APIDOC
## FormanRicci Class

### Description
A class to compute the Forman-Ricci curvature of a given NetworkX graph.

### Method
__init__

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Parameters
- **G** (NetworkX graph) - A given NetworkX graph, unweighted graph only for now, edge weight will be ignored.
- **verbose** (str) - Verbose level. Options: {"INFO","DEBUG","ERROR"}. Default: "ERROR".
  - "INFO": show only iteration process log.
  - "DEBUG": show all output logs.
  - "ERROR": only show log if error happened.

### Request Example
```python
import networkx as nx
from GraphRicciCurvature.FormanRicci import FormanRicci

G = nx.karate_club_graph()
frc = FormanRicci(G, verbose="INFO")
```

### Response
None

### Response Example
None
```

--------------------------------

### Visualize Graph Communities

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Uses a helper function to draw a NetworkX graph where nodes are colored according to their community labels.

```python
def draw_graph(G, clustering_label="club"):
    """
    A helper function to draw a nx graph with community.
    """
    complex_list = nx.get_node_attributes(G, clustering_label)

    le = preprocessing.LabelEncoder()
    node_color = le.fit_transform(list(complex_list.values()))

    nx.draw_spring(G,seed=0, nodelist=G.nodes(),
                   node_color=node_color,
                   cmap=plt.cm.rainbow,
                   alpha=0.8)

draw_graph(G_rf)
```

--------------------------------

### Compute Ricci Curvature and Flow

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/index.html

Demonstrates calculating Ollivier-Ricci and Forman-Ricci curvatures, and performing Ricci flow for community detection on a NetworkX graph.

```python
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)
print("\n=====  Compute Ricci community - by Ricci flow =====")
clustering = orc_OTD.ricci_community()
```

--------------------------------

### OllivierRicci Parameters

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Explains the parameters used in the OllivierRicci class for computing Ricci curvature.

```APIDOC
## OllivierRicci Parameters

### Description
Parameters for configuring the OllivierRicci computation.

### Parameters
#### Query Parameters
- **alpha** (float) - Required - The parameter for the probability distribution, range from [0 ~ 1]. It means the share of mass to leave on the original node. E.g. x→yx→y, alpha = 0.4 means 0.4 for xx, 0.6 to evenly spread to xx’s nbr. Default: `0.5`
- **base** (float) - Optional - Base variable for weight distribution. Default: `math.e`
- **exp_power** (float) - Optional - Exponential power for weight distribution. Default: `0`
- **method** (string) - Optional - Transportation method. Options: ["OTD", "ATD", "Sinkhorn"]. Default: `Sinkhorn`
  - "OTD" for Optimal Transportation Distance.
  - "ATD" for Average Transportation Distance.
  - "Sinkhorn" for OTD approximated Sinkhorn distance (faster).
```

--------------------------------

### Pre-compute All Pairs Shortest Paths

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/OllivierRicci.html

Pre-computes all-pairs shortest paths for the assigned Networkit graph `_Gk`. This function is intended to be called once to optimize subsequent shortest path calculations.

```python
import networkit as nk

def _get_all_pairs_shortest_path():
    """Pre-compute all pairs shortest paths of the assigned graph `_Gk`."""
    logger.trace("Start to compute all pair shortest path.")

    global _Gk

    t0 = time.time()
```

--------------------------------

### Import Necessary Libraries for Graph Loading

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Imports modules for fetching data from URLs and for graph manipulation related to cutoffs. These are essential for loading external graph datasets.

```python
from urllib.request import urlopen
from GraphRicciCurvature.util import cut_graph_by_cutoff
```

--------------------------------

### Configure Logging Verbosity

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/util.html

Sets the logging level for the GraphRicciCurvature package. Supported levels are INFO, TRACE, DEBUG, and ERROR.

```python
def set_verbose(verbose="ERROR"):
    """Set up the verbose level of the GraphRicciCurvature.

    Parameters
    ----------
    verbose : {"INFO", "TRACE","DEBUG","ERROR"}
        Verbose level. (Default value = "ERROR")
            - "INFO": show only iteration process log.
            - "TRACE": show detailed iteration process log.
            - "DEBUG": show all output logs.
            - "ERROR": only show log if error happened.
    """
    if verbose == "INFO":
        logger.setLevel(logging.INFO)
    elif verbose == "TRACE":
        logger.setLevel(logging.TRACE)
    elif verbose == "DEBUG":
        logger.setLevel(logging.DEBUG)
    elif verbose == "ERROR":
        logger.setLevel(logging.ERROR)
    else:
        print('Incorrect verbose level, option:["INFO","DEBUG","ERROR"], use "ERROR instead."')
        logger.setLevel(logging.ERROR)
```

--------------------------------

### Draw Graph After Surgery with Cutoff 1.5

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Visualizes the graph after applying `my_surgery` with a specific edge weight cutoff of 1.5.

```python
draw_graph(my_surgery(G_rf, cut=1.5))
```

--------------------------------

### Draw Graph After Surgery with Cutoff 1.0

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Visualizes the graph after applying `my_surgery` with a specific edge weight cutoff of 1.0.

```python
draw_graph(my_surgery(G_rf, cut=1.0))
```

--------------------------------

### GraphRicciCurvature.FormanRicci Methods

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/genindex.html

This section details the methods available within the FormanRicci module for computing Ricci curvature.

```APIDOC
## GET /methods/formanricci

### Description
Retrieves information about Forman Ricci curvature computation methods.

### Method
GET

### Endpoint
/methods/formanricci

### Parameters
None

### Request Example
None

### Response
#### Success Response (200)
- **methods** (array) - A list of available Forman Ricci methods.
  - **name** (string) - The name of the method.
  - **description** (string) - A brief description of the method.

#### Response Example
{
  "methods": [
    {
      "name": "compute_ricci_curvature",
      "description": "Computes the Ricci curvature using the Forman definition."
    }
  ]
}
```

--------------------------------

### Utility Functions

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/GraphRicciCurvature.html

Utility functions for graph manipulation and configuration.

```APIDOC
## GraphRicciCurvature.util.cut_graph_by_cutoff

### Description
Remove graph’s edges with weight greater than the specified cutoff.

### Parameters
- **G_origin** (NetworkX graph) - Required - A graph with weight as Ricci flow metric to cut.
- **cutoff** (float) - Required - A threshold to remove all edges with weight greater than it.
- **weight** (str) - Optional - The edge weight used as Ricci flow metric.

### Response
- **G** (NetworkX graph) - A graph with edges cut by given cutoff value.

## GraphRicciCurvature.util.get_rf_metric_cutoff

### Description
Get good clustering cutoff points for Ricci flow metric by detecting modularity changes.

### Parameters
- **G_origin** (NetworkX graph) - Required - A graph with weight as Ricci flow metric.
- **weight** (str) - Optional - The edge weight used as Ricci flow metric.
- **cutoff_step** (float) - Optional - The step size to find the good cutoff points.
- **drop_threshold** (float) - Optional - At least drop this much to considered as a drop for good_cut.

### Response
- **good_cuts** (list of float) - A list of possible cutoff points.
```

--------------------------------

### set_verbose

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/_modules/GraphRicciCurvature/util.html

Configures the logging verbosity level for the GraphRicciCurvature library.

```APIDOC
## set_verbose

### Description
Sets the logging level for the library to control the amount of output generated during execution.

### Parameters
#### Request Body
- **verbose** (string) - Optional - Verbose level: "INFO", "TRACE", "DEBUG", or "ERROR". Default is "ERROR".
```

--------------------------------

### Compute Ricci Flow with Custom Parameters

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Initializes and computes the Ricci flow on a graph with specified parameters for alpha, base, exp_power, and iterations. Use this to explore different curvature calculations.

```python
orf2 = OllivierRicci(G, alpha=0.5, base=math.e, exp_power=1, verbose="ERROR")
orf2.compute_ricci_flow(iterations=50)
G_rf2 = orf2.G.copy()
```

--------------------------------

### Draw Graph with Ricci Communities

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/tutorial.html

Visualizes the graph with communities detected by Ricci flow. Requires the graph and community labels.

```python
draw_graph(cut_graph_by_cutoff(orc_football.G,cutoff=cc[0]),clustering_label="value")
```

--------------------------------

### Compute All Possible Ricci Community Clusterings

Source: https://graphriccicurvature.readthedocs.io/en/v0.5.1/GraphRicciCurvature.html

Identifies all potential community clustering configurations by analyzing modularity drops during edge weight removal.

```python
>>> G = nx.karate_club_graph()
>>> orc = OllivierRicci(G, alpha=0.5, verbose="INFO")
>>> orc.compute_ricci_flow(iterations=50)
>>> cc = orc.ricci_community_all_possible_clusterings()
>>> print("The number of possible clusterings: %d" % len(cc))
```
Tokens:
Raw