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.

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
insert().into(@default).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}])
insert().into(@default).edges([{_from:"A", _to:"B"}, {_from:"B", _to:"E"}, {_from:"C", _to:"B"}, {_from:"C", _to:"D"}, {_from:"C", _to:"F"}, {_from:"D", _to:"B"}, {_from:"D", _to:"E"}, {_from:"F", _to:"D"}, {_from:"F", _to:"G"}])

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as hdc_tlp:

CALL hdc.graph.create("hdc-server-1", "hdc_tlp", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_tlp", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

Parameters

Algorithm name: topological_link_prediction

File Writeback

CALL algo.topological_link_prediction.write("hdc_tlp", {
  params: {
    ids: ["C"],
    ids2: ["A","E","G"],
    type: "Resource_Allocation",
    return_id_uuid: "id"
  },
  return_params: {
    file: {
      filename: "ra.txt"
    }
  }
})

algo(topological_link_prediction).params({
  projection: "hdc_tlp",
  ids: ["C"],
  ids2: ["A","E","G"],
  type: "Resource_Allocation",
  return_id_uuid: "id"
}).write({
  file: {
    filename: "ra.txt"
  }
})

Result:

_id1,_id2,result
C,A,0.25
C,E,0.5
C,G,0.333333

Full Return

CALL algo.topological_link_prediction("hdc_tlp", {
  params: {
    ids: ["C"],
    ids2: ["A","C","E","G"],
    type: "Resource_Allocation",
    return_id_uuid: "id"
  },
  return_params: {}
}) YIELD ra
RETURN ra

exec{
  algo(topological_link_prediction).params({
    ids: ["C"],
    ids2: ["A","C","E","G"],
    type: "Resource_Allocation",
    return_id_uuid: "id"
  }) as ra
  return ra
} on hdc_tlp

Result:

Stream Return

CALL algo.topological_link_prediction("hdc_tlp", {
  params: {
    ids: ["C"],
    ids2: ["A", "B", "D", "E", "F", "G"],
    type: "Resource_Allocation",
    return_id_uuid: "id"
  },
  return_params: {
    stream: {}
  }
}) YIELD ra
FILTER ra.result >= 0.3
RETURN ra

exec{
  algo(topological_link_prediction).params({
    ids: ["C"],
    ids2: ["A", "B", "D", "E", "F", "G"],
    type: "Resource_Allocation",
    return_id_uuid: "id"
  }).stream() as ra
  where ra.result >= 0.3
  return ra
} on hdc_tlp

Result: