修改密码

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

搜索
    中文

      图平均距离

      概述

      图平均距离是指图中所有节点对之间最短距离的平均值,可用来描述图的紧凑性。该概念早期曾用于评估建筑楼层设计和研究化学分子结构等,后来逐渐应用于计算机系统连通、通信网络的分析与设计中。

      图平均距离的理论值可通过邻域函数求解。由于邻域函数在大型图上的计算非常耗费资源,于是产生了近似求解算法 ANF(Approximating the Neighbourhood Function)以及比 ANF 速度更快、线性可扩展性更好的算法 HyperANF。后者由意大利米兰大学信息科学系的 Paolo Boldi、Marco Rosa 和 Sebastiano Vigna 于 2011 年提出。

      算法的相关资料如下:

      基本概念

      图平均距离

      根据图平均距离的定义,令 ij 为同一连通分量中两个不同的点,d(i,j)ij 之间的距离(最短路径的长度/边数),k 为全图可连通的节点对的数量,则图平均距离可以表示为:

      对上式中的 d(i,j) 按值进行统计,用正整数 t 表示 d(i,j) 的值,用 p(t) 表示图中所有距离为 t 的节点对的数量,便得到了图平均距离的另一种表达方式:

      如下图所示,分别用两种方法计算图平均距离:(1+2+1+1)/4=1.25(1*3+2*1)/4=1.25

      邻域函数

      邻域函数(Neighbourhood Function)也称全图邻域函数,记作 N(t),表示给定某一距离 t 时,图中所有距离小于等于 t 的节点对数量;前文中提到的 p(t) 可以用邻域函数表示为 p(t) = N(t) - N(t-1)

      考虑与某节点 x 的距离小于等于 t 的节点(不同于 x)数量,并将之定义为节点邻域函数(Independent Neighbourhood Function),记作 Nx(t);节点邻域函数和全图邻域函数的关系为 N(t) = 1/2 · ∑ Nx(t)

      通过 Nx(2) 计算 N(2) = (2+3+4+3+2)/2 = 7 和通过 p(2) 计算 N(2) = p(2) + N(1) = 3 + 4 = 7 得到的结果一致。

      至此,可以将图平均距离的求解转化为对 Nx(t) 的计算。

      邻域集

      如果用集合 B(x,t) 表示节点 xt 步内可达的所有点(包含 x),并称之为 xt邻域集,则有 Nx(t) = |B(x,t)| - 1B(x,t) 可以通过自身迭代计算而得到,即 B(x,t) = ∪ B(y,t-1),其中 y 表示 x 的一步邻居。

      考查蓝色节点 x 的邻域,图 A 即为 B(x,3),蓝色节点的一步邻居为绿、红、黄三个点(分别记作 ijk);图 B、C、D 中的绿、红、黄色环内的点分别为 B(i,2)B(j,2)B(k,2),三个环取并集后得到的集合为全图,即 B(x,3) = B(i,2) ∪ B(j,2) ∪ B(k,2)

      根据邻域集的概念可知,Nx(t) 的计算在本质上是先求并集再求集合大小的过程,即将多个集合中的元素写成一个序列,再求该序列的基数。基数(Cardinality)是指一个序列中不重复的元素的个数。例如,已知两个集合 {1,3,4}{4,5,1,7},将它们的元素写成序列 1,3,4,4,5,1,7,该序列的基数为 5,同时也是它们的并集 {1,3,4,5,7} 的元素个数。

      以连通图为例,图平均距离可以用节点邻域集的大小 |B(x,t)| 来表示:

      其中 T 为图中节点间最短距离的最大值,即图的直径;n 为图中节点的数量。

      HyperLogLog

      HyperLogLog 是一种基数估算方法,能在读取元素序列后统计出序列的基数。由于其在计算时所占用内存的大小为近乎线性的双对数 O(n·log(log n)),因此得名。

      HyperLogLog 的工作原理如下:

      1. 准备一个长度为 2b 的数组 M(初始时每个元素都为 -∞)。
      2. 将序列中的每个元素值映射为一个足够长的二进制数列,用数列中的前 b 位所对应的整数值作为与该元素相对应的数组位置下标。
      3. 从元素映射的二进制数列的第 b+1 位开始,观察第一个 1 出现在第几位,将这个位数记作 ρρ 必为正整数),如果 ρ 比元素对应的数组位置上的值更大,则用 ρ 更新该数组位置上的值。
      4. 所有元素读取完毕后,序列的基数通过数组 M 的值进行计算:

      其中 m 为数组 M 的长度 2bαm 的函数:

      例如,当 b 取值 4 时,m 等于 16α 等于 0.6731,如果 M[1,3,1,2,3,3,6,4,3,1,3,2,3,2,1,2],基数为 45.012745

      Ultipa 的图平均距离算法为图中每个节点 x 准备一个数组 M,用于计算该节点邻域集内的节点数 |B(x,t)|,则 n 个节点共需 n 个数组 M;令 C 为这些数组构成的 n × m 维的矩阵:

      t = 1 开始,迭代计算 C(t)C(t) 中的每个 Mx 可根据 C(t-1) 中的多个 My 取同下标中的最大值而得出(yx 的所有一步邻居)。循环迭代直至 C(t) 不再变化,或迭代轮数达到限制。

      特殊处理

      孤点、不连通图

      孤点不与任何节点连通,不参与图平均距离的计算。

      不连通图在其各个连通分量内部构成连通的节点对,所有这些节点对共同计算出图的平均距离。

      自环边

      节点的自环边不构成节点间的最短路径,因此不影响图平均距离的计算。

      有向图

      对于有向边,本算法会忽略边的方向,按照无向边进行计算。

      结果和统计值

      以下面的图为例,运行图平均距离算法,设置算法最大迭代 5 轮,数组 M 长度为 24,即 b = 4:

      算法结果:

      算法统计值:估算的图平均距离 hyperANF_result

      hyperANF_result
      1.8471822653636683

      注:本例图平均距离精确值为 33/18 = 1.833333

      命令和参数配置

      • 命令:algo(hyperANF)
      • params() 参数配置项如下:
      名称
      类型
      默认值
      规范
      描述
      loop_num int / >=1,必填 算法的最大迭代轮数
      register_num int / [4,30],必填 用 HyperLogLog 估算基数时,决定数组 M 长度的幂运算指数 b 的值

      算法执行

      任务回写

      1. 文件回写

      算法不支持文件回写。

      2. 属性回写

      算法不支持属性回写。

      3. 统计回写

      算法不支持统计回写。

      直接返回

      别名序号 类型 描述 列名
      0 KV 图平均距离 hyperANF_result

      示例:计算图平均距离,设置算法最大迭代 5 轮,数组 M 长度为 24,即 b = 4,将算法统计值定义为别名 distance 并返回

      algo(hyperANF).params({
        loop_num: 5,
        register_num: 4
      }) as distance 
      return distance
      

      流式返回

      算法不支持流式返回。

      实时统计

      别名序号 类型 描述 列名
      0 KV 图平均距离 hyperANF_result

      示例:计算图平均距离,设置算法最大迭代 5 轮,数组 M 长度为 24,即 b = 4,将算法统计值定义为别名 distance 并返回

      algo(hyperANF).params({
        loop_num: 5,
        register_num: 4
      }).stats() as distance 
      return distance
      
      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写