Path enumeration sampling

connectome.pes.strong_path_enumeration_sampling.pes(arr, int max_length, probabilities=None, repeat=1, ratio_paths_to_nodes=1)

Sample strong edge paths uniformly using the path enumeration sampling algorithm 1.

Parameters

  • arr (2d array) – Directed adjacency matrix.

  • max_length (int) – Sample paths up to length max_length.

  • probabilities (1d array of length max_length) – Probabilities[n] is the probability of exploring a path of length n further.

  • repeat (int) – Repeat the builder procedure repeat times and sum up the so obtained paths/cycles.

  • ratio_paths_to_nodes (float) – Try to sample ratio_paths_to_nodes * nr_nodes paths of length max_length.

Returns

  • paths (list) –

    List of nr of paths of given length:

    • paths[0] = Nr of nodes

    • paths[1] = Nr of paths with 1 edge

    • paths[2] = Nr of paths consisting of 2 edges

    • etc. ….

  • cycles (list) – List of nr of cycles of given length.

Note

The algorithm is rather unstable for paths of length larger than about 50; in these cases the number of returned paths can both exponentially increase or decay (i.e. no path is sampled). For shorter paths (length shorter than about 20), this algorithm is stable. Importantly, in this algorithm the paths are sampled uniformly, unlike in random-walk based sampling algorithms which do not yield uniform samples.

1

Wernicke, Sebastian. “Efficient Detection of Network Motifs.” IEEE/ACM Trans. Comput. Biol. Bioinformatics 3, no. 4 (October 2006): 347–359. doi:10.1109/TCBB.2006.51.

connectome.pes.weak_path_enumeration_sampling.weak_edge_pes(arr, max_length_py=None, probabilities_py=None, repeat=1, ratio_paths_to_nodes=1)

Sample weak edge paths uniformly.

Parameters

  • arr (2d array) – Directed adjacency matrix.

  • max_length (int) – Sample paths up to length max_length.

  • probabilities_py (1d array) – Probabilities[k] is the probability with which to extend a path of length k further.

  • repeat (int) – Number of times to repeat the building process.

Returns

result_list – List of counts of how many paths, balanced/unbalanced cycles of each length were found,

  • result_list[k,0] : no cycles

  • result_list[k,1] : balanced cycles

  • result_list[k,2] : unbalanced cycles

Here, k is the number of edges in the path. Note that for k=0 all entries are always 0.

Return type

array