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 v_source VERTEX v_target, SET<STRING> e_type)
gsql

Parameters

Name Description Default value

VERTEX v_source

The first vertex to compare. Provide the vertex ID and type as a tuple: ("id","type")

N/A

VERTEX v_target

The second vertex to compare with the first. Provide the vertex ID and type as a tuple: ("id","type")

N/A

SET<STRING> e_type_set

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:

adamic adar ex

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