search

sg-dev / pathpy

pathpy is an OpenSource python package for the analysis of time series data on networks using higher-order and multi-order graphical models.
GNU Affero General Public License v3.0
2 stars 0 forks source link

Issue with temporal path calculation based on DAG #76

Closed IngoScholtes closed 6 years ago

IngoScholtes commented 6 years ago

There is an issue with the DAG-based calculation of temporal paths when delta is larger than one.

For the following example

t = pp.TemporalNetwork()
t.add_edge('a', 'b', 1)
t.add_edge('b', 'c', 3)

we get the following result for delta=2:

p = pp.path_extraction.paths_from_temporal_network_dag(t, delta=2)
Paths of length k = 0 0.0 [ 0.0 / 8.0 / 8.0 ]
Paths of length k = 1 1.0 [ 1.0 / 4.0 / 5.0 ]
Paths of length k = 2 2.0 [ 1.0 / 0.0 / 2.0 ]

The reason for that is that in the DAG created from the temporal network there are multiple temporal paths to multiple temporal copies that are leafs in the DAG. In the case above, this means that the path a->b->c is counted twice. Moreover, the link a->b (which should be counted as a sub-path of the longer temporal path) is counted as a longest temporal path (again to a temporal copy of b).

IngoScholtes commented 6 years ago

closed in bf8c9319427703c60d16937f6602b10c6f98f3f6

IngoScholtes commented 6 years ago

I eventually created a totally new implementation for the extraction of causal path in temporal networks for arbitrary delta. Interestingly, this new implementation is also the basis for a new approach to efficiently estimate path statistics in temporal networks for large delta in cases where a full computation is prohibitive. It is based on a sampling of root nodes in the DAG and it is implemented in the new method sample_paths_from_temporal_network_dag.

The new implementation is also a great basis for a parallel path estimation algorithm.