Common Neighbors

Supported Graph Characteristics

Unweighted edges

Directed edges

Undirected edges

Homogeneous vertex types

Heterogeneous vertex types

Algorithm Link: Common Neighbors

A vertex $A$ that is connected to vertices $B$ and $C$ is considered to be a "common neighbor" of $B$ and $C$ .

The common neighbors algorithm counts the number of common neighbors between two vertices.

Notes

This algorithm ignores edge weights.

Specifications

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

Parameters

Name Description Default value

Name	Description	Default value
`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 the number of common neighbors between two vertices expressed as a closeness value.

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:

Running the algorithm between Dan and Jenny shows that they have 1 common neighbor.

Query
Result

 RUN QUERY common_neighbors (("Jenny", "person"), ("Dan", "person"), ["friendship"])gsql

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