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

概述

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

算法的相关资料如下：

• P. Boldi, M. Rosa, S. Vigna, HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget (2011)

基本概念

图平均距离

图平均距离（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 = 2^b 个寄存器（Register）的数组，每个寄存器的值被初始化为 -∞。例如，当 b = 3 时，M[0] = M[1] = ... = M[7] = -∞。

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

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

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

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

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

这实际上是对 2^M[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 计数器 C_x(t)。假设 b = 2，则每个计数器有 m = 2^b = 4 个寄存器。
• 然后可根据 i 和 ρ 的值计算 C_x(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)
• 参数：

示例

示例图如下：

直接返回

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

结果：distance

流式返回

algo(hyperANF).params({
  loop_num: 7,
  register_num: 5
}).stream() as distance 
return round(distance.hyperANF_result)

结果：3

统计返回

algo(hyperANF).params({
  loop_num: 7,
  register_num: 10
}).stats() as distance 
return distance

结果：distance