Updated on 2023-11-13 GMT+08:00

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.

  1. To set the dynamic time range parameters, run the following command:

    start=1646092800, end =1646170716, stime="startTime", etime="endTime"

  2. 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"

  3. 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.