修改密码

请输入密码
请输入密码 请输入8-64长度密码 和 email 地址不相同 至少包括数字、大写字母、小写字母、半角符号中的 3 个
请输入密码
提交

修改昵称

当前昵称:
提交

申请证书

证书详情

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

服务器的MAC地址

Please complete this required field.

Please complete this required field.

取消
申请
ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息
关闭
基础信息
  • 用户昵称:
  • 手机号:
  • 公司名称:
  • 公司邮箱:
  • 地区:
  • 语言:
修改密码
申请证书

当前未申请证书.

申请证书
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

No Invoice

搜索
    中文

      全图 K 邻

      概述

      全图 K 邻算法可以为每个节点计算其第 K 步邻居的数量,并返回这些邻居。该算法广泛应用于关系发现、影响力预测、好友推荐等场景。

      全图 K 邻可以看作是 UQL 命令 khop() 的批量执行。尽管 Ultipa 的全图 K 邻算法经过了高并发性能优化,在大图(超过千万顶点及边)或有很多超级节点的图中运行此算法仍会消耗大量系统资源。因此,建议避免进行过深的全图 K 邻居计算。

      在一个 边数量/点数量 = 100 的图中,查询 1 个顶点的 5-hop 邻居,理论上计算量是 100 的 5 次方(100 亿量级的计算复杂度),耗时 100 毫秒;那么,在一个有 1 千万顶点的图中查询完毕,则需要 100 万秒(12 天)。

      基本概念

      BFS

      BFS(Broad-First Search)是宽度优先遍历的缩写,与深度优先遍历(DFS,Depth-First Search)一起构成最基本的两种遍历原则。K 邻查找使用的就是 BFS 原则,具体是指以图中某一节点为起点遍历全图时,先遍历当前节点所有尚未遍历的邻居节点,再依次对这些邻居节点遍历它们尚未遍历的邻居节点。

      以红色节点为起点,按照 BFS 原则进行遍历,会先后找到黄色节点、绿色节点、蓝色节点。这些节点的颜色分类是基于它们与起点之间的距离,即从起点到它们的最短路径的边数。这个距离就是 K 邻查询中 K 的含义,表示起点的第 K 层邻居。

      给定起点后,图中其它节点的 K 值也将随之确定。即,如果一个节点是起点的第 5 层邻居,那么它就不可能在第 4、6 或其它层中出现。

      K 邻方向

      在有向图中进行 K 邻查询时,可以指定邻居所在的边的方向。此时,不是所有节点都会出现在遍历结果中,即有些节点的 K 值不存在。

      在上面左侧的有向图中,从红色节点开始,分别按照出边、入边的方向进行遍历;可以发现两种遍历结果截然不同,并且在沿入边遍历时,紫色节点不属于任何一个层次,其 K 值不存在。

      特殊处理

      孤点、不连通图

      孤点不会出现在 K 邻查询的结果中。

      对于不连通图,只有起点所在的连通分量中的节点会出现在 K 邻查询的结果中,其余的点均不会被遍历到。

      自环边

      K 邻查询中每个节点仅被遍历一次,因此可以认为节点的自环边无效。

      有向边

      在不规定边的方向时进行 K 邻查询,边的方向将被忽略,此时起点所在连通分量中的所有节点都可计算出确定的 K 值。

      结果和统计值

      以下面的银行卡转账图为例,卡的颜色代表其等级,针对所有点运行全图 K 邻算法:

      算法结果:计算每个点的一步邻居,并统计结果中银行卡的最高等级,根据算法执行方式,返回 _idvalue 两列或 _uuidvalue 两列,其中 value 列依次显示聚合统计结果和邻居数

      _uuid _id value
      1 Card1 3, 3
      2 Card2 3, 3
      3 Card3 2, 3
      4 Card4 3, 1
      5 Card5 2, 2
      6 Card6 , 0

      算法统计值:

      命令和参数配置

      • 命令:algo(khop_all)
      • params() 参数配置项如下:
      名称
      类型
      默认值
      规范 描述
      ids 或 uuids []_id 或 []_uuid / / 待计算节点的 ID 或 UUID;忽略表示计算全部点
      k_start int 1 >= 1 寻找 K 邻的最小深度值,算法搜索 K 邻的范围是 [k_start, k_end],k_endk_start
      k_end int 1 >= 1 寻找 K 邻的最大深度值,算法搜索 K 邻的范围是 [k_start, k_end],k_endk_start
      src_include int 0 0 或 1 是否将起点包含在结果中,1 代表包含,0 或忽略代表不包含
      direction string / in/out,大小写均可 路径中边的方向;忽略表示忽略方向
      node_property []@<schema>?.<property> / 数值类的点属性,需LTE 要进行聚合统计的点属性,带不带 schema 均可,必须与 aggregate_opt 一起使用,如果填多个属性,aggregate_opt 也需对应填写多种聚合统计方式;无该属性的结果不参与聚合统计
      aggregate_opt []string / max 或 min 或 mean 或 sum 或 var 或 dev,大小写不敏感 结果的每个指定属性的聚合统计方式,必须与 node_property 参数一起使用且一一对应;max 表示最大值,min 表示最小值, mean 表示平均值, sum 表示总和,var 表示方差,dev 表示标准差
      limit int -1 >=-1 需要返回的结果条数,-1 或忽略表示返回所有结果

      示例:计算所有点出方向两步邻居的数量

      algo(khop_all).params({ 
        k_start: 2,
        k_end: 2,
        direction: "out"
      }) as k2
      return k2
      

      示例:计算点 UUID = 3,4,5 的两步和三步邻居并统计结果中 @card.level 属性的最大值和 @card.balance 属性的总和,同时在每个节点的结果中包含起点(UUID = 3,4,5)

      algo(khop_all).params({ 
        uuids: [3,4,5],
        k_start: 2,
        k_end: 3,
        src_include: 1,
        node_property: [@card.level, @card.balance],
        aggregate_opt: ["max", "sum"]
      }) as k2
      return k2
      

      算法执行

      任务回写

      1. 文件回写

      配置项
      各列数据 备注
      filename_ids _id,_id 每个结果占一行,每行第一个 _id 是计算的点,第二个 _id 为该点邻居
      filename _id,aggregate_result1,...,aggregate_resultN,count _id 代表计算的点,接着是一个或多个聚合统计结果(aggregate_result1 ~ aggregate_resultN),最后的 count 是邻居总数

      示例:计算所有点的三步邻居并统计结果中 @card.level 属性的最大值和 @card.balance 属性的总和,将每个点和其邻居的 ID 回写至名为 neighbors 的文件,将每个点的聚合统计结果和邻居数量回写至名为 counts 的文件

      algo(khop_all).params({ 
        k_start: 3,
        k_end: 3,
        node_property: [@card.level, @card.balance],
        aggregate_opt: ["max", "sum"]
      }).write({
        file:{
          filename_ids: "neighbors",
          filename: "counts"
        }
      })
      

      2. 属性回写

      配置项 回写内容 类型 数据类型
      property 邻居数 点属性 double

      示例:计算所有点的两步邻居,将邻居数回写至名为 khop2 的点属性

      algo(khop_all).params({ 
        k_start: 2,
        k_end: 2
      }).write({
        db:{ 
          property: "khop2"
        }
      })
      

      3. 统计回写

      算法无统计值。

      直接返回

      别名序号
      类型
      描述
      列名
      0 []perNode 点及其聚合统计结果和邻居数 _uuid, value

      示例:计算所有点的三步邻居并统计结果中 @card.level 属性的最大值和 @card.balance 属性的总和,将算法结果定义为别名 nei 并返回

      algo(khop_all).params({ 
        k_start: 3,
        k_end: 3,
        node_property: [@card.level, @card.balance],
        aggregate_opt: ["max", "sum"]
      }) as nei
      return nei
      

      流式返回

      别名序号
      类型
      描述
      列名
      0 []perNode 点及其聚合统计结果和邻居数 _uuid, value

      示例:计算点 UUID = 3 的一步到三步邻居并统计结果中 @card.level 属性的最大值,仅返回聚合统计结果和邻居数量

      algo(khop_all).params({
         uuids: [3],
         k_start: 1,
         k_end: 3,
         node_property: @card.level,
         aggregate_opt: max
      }).stream() as results 
      return results.value
      

      实时统计

      算法无统计值。

      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写