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

Google

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.

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

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

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

Learn Before

Related