Resource Allocation

Supported Graph Characteristics

Unweighted edges

Homogeneous vertex types

Heterogeneous vertex types

Algorithm link: Resource Allocation

Resource Allocation is used to compute the closeness of nodes based on their shared neighbors. It is computed by the following formula:

\[{RA(x,y)=\sum _{u\in N(x)\cap N(y)}{\frac {1} {|N(u)|}}}\]

Where \({N(u)}\) is the set of nodes adjacent to u.

Notes

This algorithm ignores edge weights.

Specifications

CREATE QUERY tg_resource_allocation(VERTEX a, VERTEX b, SET<STRING> e_type)

Parameters

Name Description Data type

VERTEX a

The first vertex to compare.

N/A

VERTEX b

The second vertex to compare with the first.

N/A

SET<STRING> e_type

Edge types to traverse.

(A blank set of strings)

Output

Returns a closeness value for two input vertices.

Time complexity

The algorithm has a time complexity of \(O(D1 + D2)\), where \(D1\) and \(D2\) are the degrees of the two vertices.

Example

Suppose we have the following graph:

preferential attachment ex

Dan and Jenny have one shared neighbor Tom, who has two neighbors. Running the algorithm between Dan and Jenny with friendship edges returns a result of 0.5.

  • Query

  • Result

RUN QUERY resource_allocation (("Jenny", "person"), ("Dan", "person"), ["friendship"])
{
  "error": false,
  "message": "",
  "version": {
    "schema": 1,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{
    "@@closeness": 0.5
  }]
}