The Sorenson index is a local overlap statistic that counts the number of neighbors that two nodes share and normalizes the count by the sum of their node degrees:

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

Sorenson Index

The Salton index is a local overlap statistic that counts the number of neighbors that two nodes share and normalizes the count by the square root of the product of the degrees of nodes $$u$$ and $$v$$: $$S_{Salton}[u,v] = \frac{2|N(u) \cap N(v)|}{\sqrt{d_ud_v}}$$

Salton Index

The Jaccard overlap index is a local overlap statistic that counts the number of neighbors that two nodes share and normalizes this count by the size of the union of the two nodes' neighbor sets: $$S_{Jaccard}[u,v] = \frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|}$$

Jaccard Overlap Index

The simplest neighborhood overlap measure just counts the number of neighbors that two nodes share: $$S[u,v] = |N(u) \cap N(v)|$$

Simple Neighborhood Overlap Measure

The Adamic-Adar (AA) index is a local overlap statistic that considers the importance of common neighbors between two nodes. Similar to the Resource Allocation index, it is calculated by summing the inverse logarithm of the degrees of the common neighbors: $$S_{AA}[v_1,v_2] = \sum_{u \in N(v_1) \cap N(v_2)}{\frac{1}{\log(d_u)}}$$

Adamic-Adar (AA) Index

The Resource Allocation (RA) index is a local overlap statistic that goes beyond simply counting the number of common neighbors by considering their importance. It is calculated by summing the inverse degrees of the common neighbors between two nodes: $$S_{RA}[v_1,v_2] = \sum_{u \in N(v_1) \cap N(v_2)}{\frac{1}{d_u}}$$

Resource Allocation (RA) Index

Local overlap statistics are 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 proportional to $$S[u,v]$$, meaning $$P(A[u,v] = 1) \propto S[u,v]$$. Examples of local overlap statistics include the simple neighborhood overlap measure, the Sorenson index, the Salton index, the Jaccard overlap index, and the Resource Allocation (RA) and Adamic-Adar (AA) indexes.

Carleton College

Google

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

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