Temporal Paths

Overview

Different from path analysis on static graphs, the Temporal Paths algorithm combines the order of information transmission on dynamic graphs. The passing time of an edge on a path must be later than or the same as that of the previous edge, showing the increment (or non-decrement) of time.

Temporal paths do not meet transitivity: If there is one temporal path from the vertex i to the vertex j, and there is one temporal path from the vertex j to the vertex k, it does not indicate that there is one temporal path from the vertex i to the vertex k. So, in terms of solving a problem, solving a path on a dynamic graph is more complex than on a static graph, and the calculation is much more difficult. However, temporal path analysis is widely used in actual life, for example, calculating a travel route and simulating/searching for an information propagation path.
Temporal Paths can be classified into Shortest, Foremost, and Fastest Temporal Paths based on the problem-solving objective.
- Shortest Temporal Paths: indicates the temporal path with the shortest distance.
- Foremost Temporal Paths: indicates the temporal path that reaches the target node as early as possible.
- Fastest Temporal Paths: indicates the temporal path that takes the shortest time.

Application Scenarios

It is applicable to scenarios such as epidemic or disease transmission source tracing, information transmission and public opinion analysis, time sequence-based path planning, and fund circulation path.

Parameter Description

**Table 1** Temporal Paths parameters
Parameter	Mandatory	Description	Type	Value Range	Default Value
source	Yes	Source vertex ID	String	-	-
targets	Yes	Target vertex ID set	String	The value is in CSV format. IDs are separated by commas (,), for example, Alice,Nana. The number of IDs cannot exceed 100,000.	1000
directed	No	Whether an edge is directed	Boolean	The value can be true or false.	false
k	No	Maximum depth	Integer	1 to 100, including 1 and 100	3
strategy	No	Algorithm policy	String	The value can be shortest, foremost, or fastest. (Note: fastest is not supported currently.) shortest: Runs the shortest temporal paths algorithm to return the temporal path with the shortest distance. foremost: Runs the foremost temporal paths algorithm to return the temporal path that reaches the target node as early as possible. fastest: Runs the fastest temporal paths algorithm to return the temporal path that takes the shortest time.	shortest

**Table 2** dynamicRange description
Parameter	Mandatory	Description	Type	Value Range	Default Value
start	Yes	Start time for dynamic analysis	Date/Integer	-	-
end	Yes	End time for dynamic analysis	Date/Integer	-	-
time_props	Yes	Time properties for dynamic analysis	Object	-	-

**Table 3** time_props description
Parameter	Mandatory	Description	Type	Value Range	Default Value
stime	Yes	Name of the start time property	String	-	-
etime	Yes	Name of the end time property	String	-	-

Precautions

Temporal path analysis needs to be performed on dynamic graphs.

Example

Select the algorithm in the algorithm area of the graph engine editor. For details, see Analyzing Graphs Using Algorithms.

To set the dynamic time range parameters, run the following command:
start=1646092800, end =1646170716, stime="startTime", etime="endTime"
Set the parameters of the temporal paths algorithm.
source="Person00014"

targets="Person00055,Person00058,Person00052,Person00061,Person00060,Place00032,Place00016,Place00026,Place00015,Place00043"

directed="false"

k="5"
Select the algorithm search policy shortest or foremost. Click Run to run the temporal paths algorithm. The graph engine calculates and returns the temporal analysis path based on the selected algorithm search policy. The path dynamically extends with the time axis until it reaches the target node. The JSON results are displayed in the query result area.