文档首页/ 图引擎服务 GES/ 用户指南/ 算法参考/ 时序路径分析(Temporal Paths)
更新时间:2024-07-19 GMT+08:00
分享

时序路径分析(Temporal Paths)

概述

时序路径分析算法(Temporal Paths)区别于静态图上的路径分析,结合了动态图上信息传播的有序性,路径上后一条边的经过时间要晚于或等于前一条边,呈现时间递增(或非减)性。

  • 时序路径不满足传递性:即从节点i到节点j有一条时序路径,从节点j到节点k有一条时序路径,并不能说明从节点i到节点k有一条时序路径。因此在求解问题上,相较于静态图上的路径求解复杂度升高,计算难度变大,但时序路径分析在实际生活中用途很广,例如计算出行路线,模拟/搜索信息传播路径等。
  • Temporal Paths根据求解目标的差异可分为不同的类型,常见的有:Shortest, Foremost, 以及 Fastest Temporal Paths。
    • Shortest Temporal Paths:表示距离最短的时序路径。
    • Foremost Temporal Paths:表示尽可能早的到达目标节点的时序路径。
    • Fastest Temporal Paths :表示耗费时间最短的时序路径。

适用场景

适用于疫情或疾病传播溯源、信息传播和舆情分析、结合时序的路径规划、资金流通路径等场景。

参数说明

表1 Temporal Paths参数说明

参数

是否必选

说明

类型

取值范围

默认值

source

起点id

String

-

-

targets

终点id集合

String

csv格式,ID之间以英文逗号分隔,例如:“Alice,Nana”,个数不大于100000。

1000

directed

是否考虑边的方向

Boolean

true 或false,布尔型。

false

k

最大深度

Integer

1-100,包括1和100

3

strategy

运行的算法策略

String

取值范围:shortest,foremost,fastest。

(注:fastest暂不支持)

  • shortest:运行shortest temporal paths算法,返回距离最短的时序路径
  • foremost:运行foremost temporal paths算法,返回尽可能早的到达目标节点的时序路径
  • fastest:运行fastest temporal paths算法,返回耗费时间最短的时序路径

shortest

表2 动态时间范围设置(dynamicRange)说明

参数

是否必选

说明

类型

取值范围

默认值

start

动态分析起始时间

Date/ Integer

-

-

end

动态分析终止时间

Date/ Integer

-

-

time_props

动态分析的时间属性定义

Object

-

-

表3 动态分析的时间属性(time_props)说明

参数

是否必选

说明

类型

取值范围

默认值

stime

开始时间属性名称

String

-

-

etime

结束时间属性名称

String

-

-

注意事项

时序路径分析需要在动态图上运行。

示例

需要在图引擎编辑器的算法区内,选定该算法进行操作。具体操作详见使用算法分析图

  1. 设置动态时间范围参数:

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

  2. 设置temporal paths算法参数:

    source="Person00014"

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

    directed="false"

    k="5"

  3. 选择算法搜索策略“shortest”或“foremost”。单击运行按钮,运行temporal paths算法,图引擎会根据选定的算法搜索策略,计算返回时序分析路径,路径随时间轴动态延伸,直至到达目标节点,JSON结果会展示在查询结果区。

相关文档