Common Neighbors

Overview

The Common Neighbors algorithm computes the number of common neighbors between two nodes as a measure of their similarity.

The logic behind this algorithm is that if two nodes have a high number of neighbors in common, they are likely to be similar or connected in some meaningful way. It is computed using the following formula:

where N(x) and N(y) are the sets of adjacent nodes to nodes x and y respectively.

More common neighbors indicate greater similarity between nodes, while a number of 0 indicates no similarity between two nodes.

In this example, CN(D,E) = |N(D) ∩ N(E)| = |{B, F}| = 2.

Considerations

• The Common Neighbors algorithm ignores the direction of edges but calculates them as undirected edges.

Syntax

• Command: algo(topological_link_prediction)
• Parameters:

Example

The example graph is as follows:

File Writeback

UQL
algo(topological_link_prediction).params({
  uuids: [3],
  uuids2: [1,5,7],
  type: 'Common_Neighbors'
}).write({
  file:{ 
    filename: 'cn'
  }
})

Results: File cn

File
C,A,1.000000
C,E,2.000000
C,G,1.000000

Direct Return

UQL
algo(topological_link_prediction).params({
  ids: 'C',
  ids2: ['A','C','E','G'],
  type: 'Common_Neighbors'
}) as cn 
return cn 

Results: cn

Stream Return

UQL
find().nodes() as n
with collect(n._id) as nID
algo(topological_link_prediction).params({
  ids: 'C',
  ids2: nID,
  type: 'Common_Neighbors'
}).stream() as cn
where cn.num >= 2
return cn

Results: cn