概述

资源分配（Resource Allocation）算法基于一个假设，即节点通过它们共同的邻居作为传输者来相互传递资源。在其基本形式中，我们假设每个传输者拥有一个单位的资源，这个资源均匀分布给它的所有邻居。因此，两个节点之间的相似度可以通过一个节点向另一个节点传输的资源量来衡量。这个概念由Tao Zhou、Linyuan Lü和Yi-Cheng Zhang在2009年提出：

• T. Zhou, L. Lü, Y. Zhang, Predicting Missing Links via Local Information (2009)

它的计算公式如下：

其中，N(u)是与节点u相连的节点集合。对于两个节点的每个共同邻居u，资源分配首先计算其度数|N(u)|的倒数，然后将所有共同邻居的这些倒数值相加。

计算图集中节点的度时：

• 如果两点间存在多条边，只计数一次；
• 不计算自环边。

资源分配分值较高表示节点间的相似度较大，分值为0则表示两个节点间没有相似性。

在上图中，N(D) ∩ N(E) = {B, F}，则RA(D,E) = $\frac{1}{\mathrm{|N(B)|}}$ + $\frac{1}{\mathrm{|N(F)|}}$ = $\frac{1}{4}$ + $\frac{1}{3}$ = 0.5833。

特殊说明

• 资源分配算法忽略边的方向，按照无向边进行计算。

语法

• 命令：algo(topological_link_prediction)
• 参数：

示例

示例图如下：

文件回写

algo(topological_link_prediction).params({
  uuids: [3],
  uuids2: [1,5,7],
  type: 'Resource_Allocation'
}).write({
  file:{ 
    filename: 'ra'
  }
})

结果：文件ra

C,A,0.250000
C,E,0.500000
C,G,0.333333

直接返回

algo(topological_link_prediction).params({
  ids: 'C',
  ids2: ['A','C','E','G'],
  type: 'Resource_Allocation'
}) as ra 
return ra 

结果：ra

流式返回

find().nodes() as n
with collect(n._id) as nID
algo(topological_link_prediction).params({
  ids: 'C',
  ids2: nID,
  type: 'Resource_Allocation'
}).stream() as ra
where ra.num >= 0.3
return ra

结果：ra