API: GraphRicciCurvature

FormanRicci

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

class GraphRicciCurvature.FormanRicci.FormanRicci(G: networkx.Graph, weight='weight', method='augmented', verbose='ERROR')

__init__(G: networkx.Graph, weight='weight', method='augmented', 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.

• weight (str) – The edge weight used to compute Ricci curvature. (Default value = “weight”)

• method ({"1d", "augmented", "balanced"}) –

  The method used to compute Forman-Ricci curvature. (Default value = “augmented”)

  • ”1d”: Computed with 1-dimensional simplicial complex (vertex, edge).

  • ”augmented”: Computed with 2-dimensional simplicial complex, length <=3 (vertex, edge, face).

  • ”balanced”: Computed with balanced Forman-Ricci curvature (Topping et al. 2022) for unweighted graphs.

• 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.

__dict__ = mappingproxy({'__module__': 'GraphRicciCurvature.FormanRicci', '__init__': <function FormanRicci.__init__>, 'compute_ricci_curvature': <function FormanRicci.compute_ricci_curvature>, '__dict__': <attribute '__dict__' of 'FormanRicci' objects>, '__weakref__': <attribute '__weakref__' of 'FormanRicci' objects>, '__doc__': None, '__annotations__': {}})

__module__ = 'GraphRicciCurvature.FormanRicci'

__weakref__

list of weak references to the object

compute_ricci_curvature()

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][2]
{'weight': 1.0, 'formanCurvature': -7.0}

OllivierRicci

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

class GraphRicciCurvature.OllivierRicci.OllivierRicci(G: networkx.Graph, weight='weight', alpha=0.5, method='OTDSinkhornMix', base=2.718281828459045, exp_power=2, proc=4, chunksize=None, shortest_path='all_pairs', cache_maxsize=1000000, nbr_topk=3000, verbose='ERROR')

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: networkx.Graph, weight='weight', alpha=0.5, method='OTDSinkhornMix', base=2.718281828459045, exp_power=2, proc=4, chunksize=None, shortest_path='all_pairs', cache_maxsize=1000000, nbr_topk=3000, 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 = “OTDSinkhornMix”)

  Transportation method:

  • ”OTD” for Optimal Transportation Distance,

  • ”ATD” for Average Transportation Distance.

  • ”Sinkhorn” for OTD approximated Sinkhorn distance.

  • ”OTDSinkhornMix” use OTD for nodes of edge with less than _OTDSinkhorn_threshold(default 2000) neighbors,

    use Sinkhorn for faster computation with nodes of edge more neighbors. (OTD is faster for smaller cases)

• 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)

  • ”all_pairs” precomputes the full APSP matrix.

  • ”pairwise” avoids the APSP matrix and builds each transportation cost row with a single-source multi-target shortest-path search.

• cache_maxsize (int) – Max size for LRU cache for batched 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 = 3000)

• 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.

set_verbose(verbose)

Set the verbose level for this process.

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.

compute_ricci_curvature_edges(edge_list=None)

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_curvature()

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_flow(iterations=10, step=1, delta=0.0001, surgery=(<function OllivierRicci.<lambda>>, 100))

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 = 10)

• 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 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}

ricci_community(cutoff_step=0.025, drop_threshold=0.01)

Detect community clustering by Ricci flow metric. The communities are detected by the modularity drop while iteratively remove edge weight (Ricci flow metric) from large to small.

Parameters:

• cutoff_step (float) – The step size to find the good cutoff points.

• drop_threshold (float) – At least drop this much to considered as a drop for good_cut.

Returns:

• cutoff (float) – Ricci flow metric weight cutoff for detected community clustering.

• clustering (dict) – Detected community clustering.

Examples

To compute the Ricci community for karate club graph:

>>> 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])
The detected community label of node 0: 0

ricci_community_all_possible_clusterings(cutoff_step=0.025, drop_threshold=0.01)

Detect community clustering by Ricci flow metric (all possible clustering guesses). The communities are detected by Modularity drop while iteratively remove edge weight (Ricci flow metric) from large to small.

Parameters:

• cutoff_step (float) – The step size to find the good cutoff points.

• drop_threshold (float) – At least drop this much to considered as a drop for good_cut.

Returns:

cc – All detected cutoff and community clusterings pairs. Clusterings are detected by detected cutoff points from large to small. Usually the last one is the best clustering result.

Return type:

list of (float, dict)

Examples

To compute the Ricci community for karate club graph:

>>> 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

__dict__ = mappingproxy({'__module__': 'GraphRicciCurvature.OllivierRicci', '__doc__': "A class to compute Ollivier-Ricci curvature for all nodes and edges in G.\n    Node Ricci curvature is defined as the average of all it's adjacency edge.\n\n    ", '__init__': <function OllivierRicci.__init__>, 'set_verbose': <function OllivierRicci.set_verbose>, 'compute_ricci_curvature_edges': <function OllivierRicci.compute_ricci_curvature_edges>, 'compute_ricci_curvature': <function OllivierRicci.compute_ricci_curvature>, 'compute_ricci_flow': <function OllivierRicci.compute_ricci_flow>, 'ricci_community': <function OllivierRicci.ricci_community>, 'ricci_community_all_possible_clusterings': <function OllivierRicci.ricci_community_all_possible_clusterings>, '__dict__': <attribute '__dict__' of 'OllivierRicci' objects>, '__weakref__': <attribute '__weakref__' of 'OllivierRicci' objects>, '__annotations__': {}})

__module__ = 'GraphRicciCurvature.OllivierRicci'

__weakref__

list of weak references to the object

util

GraphRicciCurvature.util.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.

GraphRicciCurvature.util.cut_graph_by_cutoff(G_origin, cutoff, weight='weight')

Remove graph’s edges with “weight” greater than “cutoff”.

Parameters:

• G_origin (NetworkX graph) – A graph with weight as Ricci flow metric to cut.

• cutoff (float) – A threshold to remove all edges with “weight” greater than it.

• weight (str) – The edge weight used as Ricci flow metric. (Default value = “weight”)

Returns:

G – A graph with edges cut by given cutoff value.

Return type:

NetworkX graph

GraphRicciCurvature.util.get_rf_metric_cutoff(G_origin, weight='weight', cutoff_step=0.025, drop_threshold=0.01)

Get good clustering cutoff points for Ricci flow metric by detect the change of modularity while removing edges.

Parameters:

• G_origin (NetworkX graph) – A graph with “weight” as Ricci flow metric to cut.

• weight (str) – The edge weight used as Ricci flow metric. (Default value = “weight”)

• cutoff_step (float) – The step size to find the good cutoff points.

• drop_threshold (float) – At least drop this much to considered as a drop for good_cut.

Returns:

good_cuts – A list of possible cutoff point, usually we use the first one as the best cut.

Return type:

list of float