Transitive Closure#

Computes transitive closure on a weighted graph. These algorithms work with undirected weighted (distance) graphs.

distanceclosure.closure.distance_closure(D, kind='metric', algorithm='dijkstra', weight='weight', only_backbone=False, verbose=False, *args, **kwargs)#

Computes the transitive closure (All-Pairs-Shortest-Paths; APSP) using different shortest path measures on the distance graph (adjacency matrix) with values in the [0,inf] interval.

\[c_{ij} = min_{k}( metric ( a_{ik} , b_{kj} ) )\]
Parameters

  • D (NetworkX.Graph) – The Distance graph.

  • kind (string) – Type of closure to compute: metric or ultrametric.

  • algorithm (string) – Type of algorithm to use: dense or dijkstra.

  • weight (string) – Edge property containing distance values. Defaults to weight.

  • only_backbone (bool) – Only include new distance closure values for edges in the original graph.

  • Verbose (bool) – Prints statements as it computes.

Returns

C – The distance closure graph. Note this may be a fully connected graph.

Return type

NetworkX.Graph

Examples

>>> distance_closure(D, kind='metric', algorithm='dijkstra', weight='weight', only_backbone=True)

Note

Dense matrix is slow for large graphs. We are currently working on optimizing it. If your network is large and/or sparse, use the Dijkstra method.

  • Metric: \((min,+)\)

  • Ultrametric: \((min,max)\) – also known as maximum flow.

  • Semantic proximity: (to be implemented)

\[[ 1 + \sum_{i=2}^{n-1} log k(v_i) ]^{-1}\]
distanceclosure.closure.s_values(Cm, weight_distance='distance', weight_metric_distance='metric_distance')#

Computes s-values for each network edge. The s-value is the ratio between the direct distance (from the original graph) and the indirect distance (from the metric distance closure graph). The formal definition is as follow:

\[s_{ij} = d_{ij} / d_{ij}^m.\]
Parameters

  • Cm (networkx.Graph) – The metric distance closure graph.

  • weight_distance (string) – Edge attribute containing distance values. Defaults to ‘distance’.

  • weight_metric_distance (string) – Edge attribute containing metric distance values. Defaults to ‘metric_distance’.

distanceclosure.closure.b_values(Cm, weight_distance='distance', weight_metric_distance='metric_distance')#

Computes b-values for each edge with infinite distance, thus not existing in the original distance graph. The formal definition is as follow:

\[ \begin{align}\begin{aligned}b_{ij} = <d_{ik}> / d_{ij}^m\\b_{ji} = <d_{jk}> / d_{ij}^m\end{aligned}\end{align} \]

which is the average distance of all edges that leaves from node x_i, divided by its metric distance closure. Note that b_{ij} can be different from b_{ji}.

Parameters

  • (networkx.Graph) (Cm) –

  • (string) (weight_metric_distance) –

  • (string) –

Note

Both arguments must be numpy arrays as the Metric Closure network is a dense matrix.

Warning

This computation takes a while.