修改密码

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

修改昵称

当前昵称:
提交

搜索
v4.0
    v4.0

    图平均距离

    概述

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

    图平均距离的理论值可通过邻域函数求解。由于邻域函数在大型图上的计算非常耗费资源,于是产生了近似求解算法 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
    
    请完成以下信息后可下载此书
    *
    公司名称不能为空
    *
    公司邮箱必须填写
    *
    你的名字必须填写
    *
    你的电话必须填写
    *
    你的电话必须填写