brainconn.distance.distance_wei_floyd

distance_wei_floyd(adjacency, transform=None)[source]

Computes the topological length of the shortest possible path connecting every pair of nodes in the network.

Parameters:
  • D ((N x N) array_like) – Weighted/unweighted, direct/undirected connection weight/length array
  • transform (str, optional) – If adjacency is a connection weight array, specify a transform to map input connection weights to connection lengths. Options include [‘log’, ‘inv’], where ‘log’ is -np.log(adjacency) and ‘inv’ is 1/adjacency. Default: None
Returns:

  • SPL ((N x N) ndarray) – Weighted/unweighted shortest path-length array. If D is a directed graph, then SPL is not symmetric
  • hops ((N x N) ndarray) – Number of edges in the shortest path array. If D is unweighted, SPL and hops are identical.
  • Pmat ((N x N) ndarray) – Element [i,j] of this array indicates the next node in the shortest path between i and j. This array is used as an input argument for function retrieve_shortest_path(), which returns as output the sequence of nodes comprising the shortest path between a given pair of nodes.

Notes

There may be more than one shortest path between any pair of nodes in the network. Non-unique shortest paths are termed shortest path degeneracies and are most likely to occur in unweighted networks. When the shortest-path is degenerate, the elements of Pmat correspond to the first shortest path discovered by the algorithm.

The input array may be either a connection weight or length array. The connection length array is typically obtained with a mapping from weight to length, such that higher weights are mapped to shorter lengths (see argument transform, above).

Originally written in Matlab by Andrea Avena-Koenigsberger (IU, 2012) [1] [2] [3] [4].

References

[1]Floyd, R. W. (1962). Algorithm 97: shortest path. Communications of the ACM, 5(6), 345.
[2]Roy, B. (1959). Transitivite et connexite. Comptes Rendus Hebdomadaires Des Seances De L Academie Des Sciences, 249(2), 216-218.
[3]Warshall, S. (1962). A theorem on boolean matrices. Journal of the ACM (JACM), 9(1), 11-12.
[4]https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm