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

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

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)}}$ 

Resource Allocation (RA) and Adamic-Adar (AA) indexes

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

Carleton College

Neighborhood overlap metrics between pairs of nodes are useful in helping us quantify the extent to which a pair of nodes are related, which is import in tasks such as predicting the existence of an edge between two nodes.

Neighborhood Overlap Detection

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

Local Overlap Statistics

Global overlap measures are statistics that can measure relationships between two nodes in the same community graph even if these two nodes are not directly connected, while local overlap measures only consider the local relationship between nodes that are in the local node neighborhood. There are several types of global overlap measures:

1)	Katz index

2)	Leicht, Holme, and Newman (LHN) similarity

3)	Random walk methods  


Learn Before

Related

Learn After