API: GraphRicciCurvature

FormanRicci

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

class GraphRicciCurvature.FormanRicci.FormanRicci(G, verbose='ERROR')[source]
__init__(G, verbose='ERROR')[source]

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.
compute_ricci_curvature()[source]

Compute Forman-ricci curvature for all nodes and edges in G. Node curvature is defined as the average of all it’s adjacency edge.

Returns:G – A NetworkX graph with “formanCurvature” on nodes and edges.
Return type:NetworkX graph

Examples

To compute the Forman-Ricci curvature for karate club graph:

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

OllivierRicci

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

class GraphRicciCurvature.OllivierRicci.OllivierRicci(G: <sphinx.ext.autodoc.importer._MockObject object at 0x7fc20f5c5f98>, weight='weight', alpha=0.5, method='OTD', base=2.718281828459045, exp_power=2, proc=2, chunksize=None, shortest_path='all_pairs', cache_maxsize=1000000, nbr_topk=1000, verbose='ERROR')[source]

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.

__init__(G: <sphinx.ext.autodoc.importer._MockObject object at 0x7fc20f5c5f98>, weight='weight', alpha=0.5, method='OTD', base=2.718281828459045, exp_power=2, proc=2, chunksize=None, shortest_path='all_pairs', cache_maxsize=1000000, nbr_topk=1000, verbose='ERROR')[source]

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”)
  • edge_list (list of edges) – The list of edges to compute Ricci curvature, set to [] to run for all edges in G. (Default value = [])
  • 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 = “OTD”)

    Transportation method:
    • ”OTD” for Optimal Transportation Distance,
    • ”ATD” for Average Transportation Distance.
    • ”Sinkhorn” for OTD approximated Sinkhorn distance.
  • base (float) – Base variable for weight distribution. (Default value = math.e)
  • exp_power (float) – Exponential power for weight distribution. (Default value = 0)
  • 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","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.
compute_ricci_curvature()[source]

Compute Ricci curvature of edges and nodes. The node Ricci curvature is defined as the average of node’s adjacency edges.

Returns:G – A NetworkX graph with “ricciCurvature” on nodes and edges.
Return type:NetworkX graph

Examples

To compute the Ollivier-Ricci curvature for karate club graph:

>>> 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_ricci_curvature_edges(edge_list=None)[source]

Compute Ricci curvature for edges in given edge lists.

Parameters:edge_list (list of edges) – The list of edges to compute Ricci curvature, set to [] to run for all edges in G. (Default value = [])
Returns:output – A dictionary of edge Ricci curvature. E.g.: {(node1, node2): ricciCurvature}.
Return type:dict[(int,int), float]
compute_ricci_flow(iterations=10, step=1, delta=0.0001, surgery=(<function OllivierRicci.<lambda>>, 100))[source]

Compute the given Ricci flow metric of each edge of a given connected NetworkX graph.

Parameters:
  • iterations (int) – Iterations to require Ricci flow metric. (Default value = 100)
  • step (float) – step size for gradient decent process. (Default value = 1)
  • delta (float) – process stop when difference of Ricci curvature is within delta. (Default value = 1e-4)
  • surgery ((function, int)) – A tuple of user define surgery function that will execute every certain iterations. (Default value = (lambda G, *args, **kwargs: G, 100))
Returns:

G – A NetworkX graph with weight as Ricci flow metric.
Return type:

NetworkX graph

Examples

To compute the Ollivier-Ricci flow for karate club graph:

>>> 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]
{'weight': 0.06399135316908759,
 'ricciCurvature': 0.18608249978652802,
 'original_RC': 0.11111111071683011}
set_verbose(verbose)[source]

Set the verbose level for this process.

Parameters: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.

util

GraphRicciCurvature.util.set_verbose(verbose='ERROR')[source]

Set up the verbose level of the GraphRicciCurvature.

Parameters: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.