Resource Allocation

Overview

The Resource Allocation algorithm assumes that nodes distribute resources to each other through shared neighbors, who act as transmitters. In its basic form, each transmitter is considered to possess a single unit of resource, which is evenly distributed among its neighbors. As a result, the similarity between two nodes is measured by the amount of resource one node is able to transmit to the other through these shared neighbors. 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)|, and then sums these values across all common neighbors.

When calculating the degree for nodes in the graphset:

• Edges connecting the same two nodes are counted only once;
• Self-loops are excluded from the calculation.

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

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 treats all edges as undirected, ignoring their original direction.

Example Graph

GQL
INSERT (A:default {_id: "A"}), (B:default {_id: "B"}),
       (C:default {_id: "C"}), (D:default {_id: "D"}),
       (E:default {_id: "E"}), (F:default {_id: "F"}),
       (G:default {_id: "G"}), (A)-[:default]->(B),
       (B)-[:default]->(E), (C)-[:default]->(B),
       (C)-[:default]->(D), (C)-[:default]->(F),
       (D)-[:default]->(B), (D)-[:default]->(E),
       (F)-[:default]->(D)

Parameters

Run Mode

Returns:

GQL
CALL algo.resourceallocation({
  node1: "C",
  node2: "E"
}) YIELD node1, node2, score

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.resourceallocation.stream({
  node1: "C",
  node2: "E"
}) YIELD node1, node2, score
RETURN node1, node2, score

Result:

Stats Mode

Returns:

GQL
CALL algo.resourceallocation.stats({
  node1: "C",
  node2: "E"
}) YIELD score

Result: