The simplest neighborhood overlap measure just counts the number of neighbors that two nodes share:

$S[u,v] = |N(u) \cap N(v)|$

Carleton College

Local overlap statistics are simply functions of the number of common neighbors two nodes share. Given a neighborhood overlap statistic $S[u,v]$, a common strategy is to assume that the likelihood of an edge (u,v) is simply proportional to $S[u,v]$

-> $P(A[u,v] = 1) \propto S[u,v]$

A few examples of local overlap statistics include:

- simple neighborhood overlap measure
- Sorenson index
- Salton index
- Jaccard overlap
- Resource Allocation (RA) and Adamic-Adar (AA) indexes

Local Overlap Statistics

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

A simple neighborhood overlap measure 

Counts the number of neighbors that two nodes share and normalizes the count by the sum of the node degrees

$S_{Sorenson}[u,v] = \frac{2|N(u) \cap N(v)|}{d_u+d_v}$

Sorenson Index

Counts the number of neighbors that two nodes share and normalizes by the product of the degrees of *u* and *v*

$S_{Salton}[u,v] = \frac{2|N(u) \cap N(v)|}{\sqrt{d_ud_v}}$

Salton Index

Counts the number of neighbors that two nodes share and normalizes by the size of the union of the two nodes' neighbors

$S_{Jaccard}[u,v] = \frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|}$

Jaccard overlap

These measures go beyond simply counting the number of common neighbors and seek to consider the importance of those common neighbors.

The Resource Allocation (RA) index counts the inverse degrees of the common neighbors:

$S_{RA}[v_1,v_2] = \sum_{u \in N(v_1) \cap N(v_2)}{\frac{1}{d_v}}$ 

and the Adamic-Adar (AA) index performs a similar computation using the inverse logarithm of the degrees:

$S_{AA}[v_1,v_2] = \sum_{u \in N(v_1) \cap N(v_2)}{\frac{1}{log(d_v)}}$ 

Learn Before

Related