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

Carleton College

Google

The Jaccard similarity coefficient is a set-overlap measure introduced by Paul Jaccard (1912). For two finite sets $$A$$ and $$B$$, it is defined as $$J(A,B)=\dfrac{|A\cap B|}{|A\cup B|}$$, with $$J(\emptyset,\emptyset)=1$$ by convention. The score lies in $$[0,1]$$: it equals $$1$$ when the two sets contain exactly the same elements and $$0$$ when they are disjoint. Because it only counts shared versus total distinct elements, $$J$$ ignores element ordering and frequency, making it a pure overlap statistic between sets.

Jaccard Similarity Coefficient

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

Bigram Jaccard similarity applies the Jaccard coefficient to the bigram (2-gram) representations of two texts. Given a text $$T$$, let $$B(T)$$ be the set of distinct ordered token bigrams obtained by sliding a window of length $$2$$ over its tokens; for tokens $$(t_1,\dots,t_n)$$, $$B(T)=\{(t_i,t_{i+1})\mid 1\le i\le n-1\}$$. For two texts $$X$$ and $$Y$$ the bigram Jaccard similarity is $$J_{2}(X,Y)=\dfrac{|B(X)\cap B(Y)|}{|B(X)\cup B(Y)|}$$, taking values in $$[0,1]$$. Compared with unigram (bag-of-words) Jaccard, the bigram variant rewards short-range word-order agreement: two texts must reuse the same adjacent-word pairs, not just the same vocabulary, to score highly. It is reported as a lexical-overlap baseline alongside TF-IDF cosine and ROUGE-L when comparing paired drafts.

Bigram Jaccard Similarity

Jaccard Overlap Index

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

Learn Before

Related