修改密码

请输入密码
请输入密码 请输入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

v5.0
搜索
    v5.0

      HyperANF

      ✕ 文件回写 ✕ 属性回写 ✓ 直接返回 ✓ 流式返回 ✓ 统计值

      概述

      HyperANF(Hyper-Approximate Neighborhood Function,超近似邻域函数)算法用于估算图平均距离。它在准确性和计算效率之间取得了平衡,适用于大型图,精确计算大型图的平均距离通常不可行或非常耗时。

      算法的相关资料如下:

      基本概念

      图平均距离

      图平均距离(Average Graph Distance)用于衡量图中任意两个节点之间的平均步数或边数。它量化了图中节点的整体连通性或接近程度。

      如上所示,计算图平均图距离通常通过执行图遍历来计算每对节点之间的最短路径距离,然后将距离求和并除以节点对的总数来得到平均值。

      近似邻域函数(ANF)

      对于大型图而言,图遍历通常会消耗大量的计算资源和内存,因此近似邻域函数(Approximate Neighborhood Function, ANF)算法常被用来更高效地估算图平均距离。

      ANF算法旨在估算邻域函数(Neighborhood Function, NF):

      • 图的邻域函数(NF),表示为N(t),返回在t步内(含t)可以相互到达的节点对数量。
      • 图中节点x的单点邻域函数(INF),表示为N(x,t),返回从节点x出发,在t步内(含t)可以到达的节点数量。
      • 在无向图G=(V, E)中,NF和INF之间存在以下关系:

      邻域函数可以揭示图的一些特征,其中包括图平均距离:

      以下是通过邻域函数计算上述示例图的平均距离的过程:

      然而,在大型图上精确计算邻域函数的成本非常高。通过估算邻域函数,ANF算法可以在不遍历整个图的情况下估算出图平均距离。

      HyperLogLog计数器

      HyperLogLog计数器用于近似计算大型集合或元素流中不同元素数量,即基数(Cardinality)。精确计算基数通常需要与基数成比例的内存量,这对于超大数据集来说是不切实际的。HyperLogLog使用的内存则要少得多,其空间复杂度为O(log(log n))(因而得名HyperLogLog)。

      一个HyperLogLog计数器可以看作是一个包含m=2b寄存器(Register)的数组,每个寄存器的值被初始化为 -∞。例如,当b=3时,M[0]=M[1]=...=M[7]=-∞。

      寄存器的数量取决于所需估计的精度。更多的寄存器可以提供更准确的估计,但也需要更多的内存。

      首先,集合中的每个元素x通过一个哈希函数h()映射为一个固定大小的二进制序列。例如,h(x)=0100001110101...。

      然后,更新寄存器。对于集合中的每个元素x:

      • 通过取h(x)最左边b位(记作hb(x))的整数值计算寄存器的索引i。在本例中,i=hb(x)=010=0*22+1*21+0*20=2。
      • 令hb(x)为h(x)的剩余位序列,ρ(hb(x))为hb(x)的最左边1的位置。在本例中,ρ(hb(x))=ρ(0001110101...)=4。
      • 更新寄存器M[i]=max(M[i], ρ(hb(x)))。在本例中,M[2]=max(-∞, 4)=4。

      读取所有元素后,通过HyperLogLog计数器计算基数如下:

      这实际上是对2M[i]的调和平均数进行归一化处理,其中αm是根据m的值计算得出的常数:

      HyperANF

      HyperANF是一种流行的ANF算法,它在速度和可扩展性方面取得了突破性的改进。

      该算法基于以下观察结果:距离节点x在t步以内(含t)的节点集合B(x,t)满足以下条件:

      在下面的示例图中,节点a有三条邻边,分别是(a,b)、(a,c)和(a,d),因此B(a,3) = B(b,2) ∪ B(c,2) ∪ B(d,2)

      对于每个节点x,HyperANF算法使用HyperLogLog计数器简化计算过程。以下使用上面的示例图具体说明:

      • 将每个节点x映射到一个二进制表示h(x),并分配一个HyperLogLog计数器Cx(t)。假设b=2,则每个计数器有m=2b=4个寄存器。
      • 然后可根据i和ρ的值计算Cx(0)。注意:我们使用0代替-∞,结果是一样的。
      • 在第t次迭代中,对于每个节点x,通过合并节点x的所有邻居的计数器来实现B(y,t-1)((x,y)∈E)的并集,即逐个寄存器地将节点x的计数器的值最大化。
      • 经过6次迭代后,所有计数器的值保持不变,实际上是因为图的直径为6。
      • 在每次迭代中,通过带有常量αm=0.53243的基数方程计算|B(x,t)|

      由于B(x,0) = {x},因此|N(x,t)| = |B(x,t)| - 1。在这个例子中,通过算法计算得到的平均图距离是3.2041。这个例子的精确平均图距离是3。

      特殊说明

      • HyperANF算法通常最适用于连通图。对于非连通图,该算法可能无法提供准确的结果。
      • HyperANF算法忽略边的方向,按照无向边进行计算。

      语法

      • 命令:algo(hyperANF)
      • 参数:
      名称
      类型
      规范
      默认
      可选
      描述
      loop_num int ≥1 / 算法的最大迭代轮数
      register_num int [4,30] / 决定HyperLogLog计数器中寄存器数量(m=2b)的b值

      示例

      示例图如下:

      直接返回

      别名序号 类型 描述 列名
      0 KV 估算的图平均距离 hyperANF_result
      algo(hyperANF).params({
        loop_num: 5,
        register_num: 4
      }) as distance 
      return distance
      

      结果:distance

      hyperANF_result
      2.50702004427638

      流式返回

      别名序号 类型 描述 列名
      0 KV 估算的图平均距离 hyperANF_result
      algo(hyperANF).params({
        loop_num: 7,
        register_num: 5
      }).stream() as distance 
      return round(distance.hyperANF_result)
      

      结果:3

      统计返回

      别名序号 类型 描述 列名
      0 KV 估算的图平均距离 hyperANF_result
      algo(hyperANF).params({
        loop_num: 7,
        register_num: 10
      }).stats() as distance 
      return distance
      

      结果:distance

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