Resource Allocation

Overview

The Resource Allocation algorithm operates under the assumption that nodes transmit resources to each other through their shared neighbors, who act as transmitters. In its basic form, we consider each transmitter possessing a single unit of resource, which is evenly distributed among its neighbors. Consequently, the similarity between two nodes can be gauged by the magnitude of resources that one node transmits to the other. This concept was introduced by Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang in 2009:

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

It is computed using the following formula:

where N(u) is the set of nodes adjacent to u. For each common neighbor u of the two nodes, the Resource Allocation first calculates the reciprocal of its degree |N(u)|, then sums up these reciprocal values for all common neighbors.

When calculating the degree for nodes in the graphset:

• edges connecting two same nodes will be counted only once;
• self-loop will be ignored.

Higher Resource Allocation scores indicate greater similarity between nodes, while a score of 0 indicates no similarity between two nodes.

In this example, 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.

Considerations

• The Resource Allocation algorithm ignores the direction of edges but calculates them as undirected edges.

Syntax

• Command: algo(topological_link_prediction)
• Parameters:

Example

The example graph is as follows:

File Writeback

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

Results: File ra

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

Direct Return

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

Results: ra

Stream Return

UQL
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

Results: ra