Resource Allocation

Supported Graph Characteristics

Unweighted edges

Homogeneous vertex types

Heterogeneous vertex types

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)gsql

Parameters

Name Description Data type

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)

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:

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"])gsql

{
  "error": false,
  "message": "",
  "version": {
    "schema": 1,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{
    "@@closeness": 0.5
  }]
}json