Jaccard index

Similarity of asymmetric binary attributes

Given two objects, A and B, each with n binary attributes, the Jaccard index is a useful measure of the overlap that A and B share with their attributes. Each attribute of A and B can either be 0 or 1. The total number of each combination of attributes for both A and B are specified as follows:

${\displaystyle M_{11}}$ represents the total number of attributes where A and B both have a value of 1.

${\displaystyle M_{01}}$ represents the total number of attributes where the attribute of A is 0 and the attribute of B is 1.

${\displaystyle M_{10}}$ represents the total number of attributes where the attribute of A is 1 and the attribute of B is 0.

${\displaystyle M_{00}}$ represents the total number of attributes where A and B both have a value of 0.

Each attribute must fall into one of these four categories, meaning that

${\displaystyle M_{11}+M_{01}+M_{10}+M_{00}=n.}$

The Jaccard similarity index, J, is given as

${\displaystyle J=\frac{M_{11}}{M_{01}+M_{10}+M_{11}}.}$

The Jaccard distance, d_J, is given as

${\displaystyle d_J=\frac{M_{01}+M_{10}}{M_{01}+M_{10}+M_{11}}=1-J.}$

Statistical inference can be made based on the Jaccard similarity index, and consequently related metrics. Given two sample sets A and B with n attributes, a statistical test can be conducted to see if an overlap is statistically significant. The exact solution is available, although computation can be costly as n increases. Estimation methods are available either by approximating a multinomial distribution or by bootstrapping.

Difference with the simple matching index (SMC)

When used for binary attributes, the Jaccard index is very similar to the simple matching coefficient. The main difference is that the SMC has the term ${\displaystyle M_{00}}$ in its numerator and denominator, whereas the Jaccard index does not. Thus, the SMC counts both mutual presences (when an attribute is present in both sets) and mutual absence (when an attribute is absent in both sets) as matches and compares it to the total number of attributes in the universe, whereas the Jaccard index only counts mutual presence as matches and compares it to the number of attributes that have been chosen by at least one of the two sets.

In market basket analysis, for example, the basket of two consumers who we wish to compare might only contain a small fraction of all the available products in the store, so the SMC will usually return very high values of similarities even when the baskets bear very little resemblance. This can be inappropriate in sparse datasets where ${\displaystyle M_{00}}$ is typically large, making the Jaccard index a more appropriate measure of similarity in that context. For example, consider a supermarket with 1000 products and two customers. The basket of the first customer contains salt and pepper and the basket of the second contains salt and sugar. In this scenario, the similarity between the two baskets as measured by the Jaccard index would be 1/3, but the similarity becomes 0.998 using the SMC.

In other contexts, where 0 and 1 carry equivalent information (symmetry), the SMC is a better measure of similarity. For example, vectors of demographic variables stored in dummy variables, such as gender, would be better compared with the SMC than with the Jaccard index since the impact of gender on similarity should be equal, independently of whether male is defined as a 0 and female as a 1 or the other way around. However, when we have symmetric dummy variables, one could replicate the behaviour of the SMC by splitting the dummies into two binary attributes (in this case, male and female), thus transforming them into asymmetric attributes, allowing the use of the Jaccard index without introducing any bias. The SMC remains, however, more computationally efficient in the case of symmetric dummy variables since it does not require adding extra dimensions.

The Jaccard index is commonly used for asymmetric binary or presence–absence data, where the presence of an attribute is considered more informative than its absence. In such data, shared absences are treated as uninformative and are excluded from the calculation. This makes the measure particularly suitable for sparse binary data in which the occurrence of a feature is more meaningful than its non-occurrence. For symmetric binary variables, however, measures such as the simple matching coefficient may be preferred because they count both shared presences and shared absences. The distinction between similarity measures that include or exclude joint absences has been widely discussed in numerical taxonomy and classification literature. The Jaccard index is defined as

${\displaystyle J(A,B)=\frac{M_{11}}{M_{11}+M_{10}+M_{01}}}$

where ${\displaystyle M_{11}}$ is the number of attributes where both values are 1, ${\displaystyle M_{10}}$ where only A is 1, and ${\displaystyle M_{01}}$ where only B is 1.

Weighted Jaccard similarity and distance

If ${\displaystyle \mathbf{x}=(x_1,x_2,\dots ,x_n)}$ and ${\displaystyle \mathbf{y}=(y_1,y_2,\dots ,y_n)}$ are two vectors with all real ${\displaystyle x_i,y_i\ge 0}$, then their Jaccard similarity index (also known then as Ruzicka similarity) is defined as

${\displaystyle J_{\mathcal{W}}(\mathbf{x},\mathbf{y})=\frac{\sum _{i}min(x_i,y_i)}{\sum _{i}max(x_i,y_i)},}$

and Jaccard distance (also known then as Soergel distance)

${\displaystyle d_{J\mathcal{W}}(\mathbf{x},\mathbf{y})=1-J_{\mathcal{W}}(\mathbf{x},\mathbf{y}).}$

With even more generality, if ${\displaystyle f}$ and ${\displaystyle g}$ are two non-negative measurable functions on a measurable space ${\displaystyle X}$ with measure ${\displaystyle \mu }$, then we can define

${\displaystyle J_{\mathcal{W}}(f,g)=\frac{\int min(f,g)d\mu }{\int max(f,g)d\mu },}$

where ${\displaystyle max}$ and ${\displaystyle min}$ are pointwise operators. Then Jaccard distance is

${\displaystyle d_{J\mathcal{W}}(f,g)=1-J_{\mathcal{W}}(f,g).}$

Then, for example, for two measurable sets ${\displaystyle A,B\subseteq X}$, we have ${\displaystyle J_{\mu }(A,B)=J({\chi }_A,{\chi }_B),}$ where ${\displaystyle {\chi }_A}$ and ${\displaystyle {\chi }_B}$ are the characteristic functions of the corresponding set.

Calculating the weighted Jaccard similarity index for two vectors typically requires a single pass over the data, resulting in a linear computational complexity of ${\displaystyle O(n)}$, where ${\displaystyle n}$ represents the number of dimensions. In data science applications, this is often optimized for sparse vectors by iterating only over non-zero elements, which significantly reduces processing time for high-dimensional datasets. This optimization shifts the complexity to ${\displaystyle O(k)}$, where ${\displaystyle k}$ is the number of non-zero attributes.

<span id="mwASg"></span><span class="c1" id="mwASk"># Pseudocode for O(k) complexity</span> <span class="n" id="mwASo">function</span> <span class="n" id="mwASs">jaccardIndex</span><span class="p" id="mwASw">(</span><span class="n" id="mwAS0">vector_A</span><span class="p" id="mwAS4">,</span> <span class="n" id="mwAS8">vector_B</span><span class="p" id="mwATA">):</span> <span class="n" id="mwATE">intersection_sum</span> <span class="o" id="mwATI">=</span> <span class="mi" id="mwATM">0</span> <span class="n" id="mwATQ">union_sum</span> <span class="o" id="mwATU">=</span> <span class="mi" id="mwATY">0</span> <span class="c1" id="mwATc"># Get total unique keys</span> <span class="n" id="mwATg">all_keys</span> <span class="o" id="mwATk">=</span> <span class="n" id="mwATo">unique_keys</span><span class="p" id="mwATs">(</span><span class="n" id="mwATw">vector_A</span><span class="o" id="mwAT0">.</span><span class="n" id="mwAT4">keys</span><span class="p" id="mwAT8">()</span> <span class="o" id="mwAUA">+</span> <span class="n" id="mwAUE">vector_B</span><span class="o" id="mwAUI">.</span><span class="n" id="mwAUM">keys</span><span class="p" id="mwAUQ">())</span> <span class="k" id="mwAUU">for</span> <span class="n" id="mwAUY">key</span> <span class="ow" id="mwAUc">in</span> <span class="n" id="mwAUg">all_keys</span><span class="p" id="mwAUk">:</span> <span class="n" id="mwAUo">val_a</span> <span class="o" id="mwAUs">=</span> <span class="n" id="mwAUw">vector_A</span><span class="o" id="mwAU0">.</span><span class="n" id="mwAU4">get</span><span class="p" id="mwAU8">(</span><span class="n" id="mwAVA">key</span><span class="p" id="mwAVE">,</span> <span class="mi" id="mwAVI">0</span><span class="p" id="mwAVM">)</span> <span class="n" id="mwAVQ">val_b</span> <span class="o" id="mwAVU">=</span> <span class="n" id="mwAVY">vector_B</span><span class="o" id="mwAVc">.</span><span class="n" id="mwAVg">get</span><span class="p" id="mwAVk">(</span><span class="n" id="mwAVo">key</span><span class="p" id="mwAVs">,</span> <span class="mi" id="mwAVw">0</span><span class="p" id="mwAV0">)</span> <span class="n" id="mwAV4">intersection_sum</span> <span class="o" id="mwAV8">+=</span> <span class="nb" id="mwAWA">min</span><span class="p" id="mwAWE">(</span><span class="n" id="mwAWI">val_a</span><span class="p" id="mwAWM">,</span> <span class="n" id="mwAWQ">val_b</span><span class="p" id="mwAWU">)</span> <span class="n" id="mwAWY">union_sum</span> <span class="o" id="mwAWc">+=</span> <span class="nb" id="mwAWg">max</span><span class="p" id="mwAWk">(</span><span class="n" id="mwAWo">val_a</span><span class="p" id="mwAWs">,</span> <span class="n" id="mwAWw">val_b</span><span class="p" id="mwAW0">)</span> <span class="k" id="mwAW4">return</span> <span class="n" id="mwAW8">intersection_sum</span> <span class="o" id="mwAXA">/</span> <span class="n" id="mwAXE">union_sum</span>

To further scale processing time, techniques such as MinHashing and locality sensitive hashing are used to approximate the index using compact signatures. These algorithmic enhancements ensure that similarity measures remain scalable and efficient, despite an increase in data volume and dimensionality.

Probability Jaccard similarity and distance

The weighted Jaccard similarity described above generalizes the Jaccard Index to positive vectors, where a set corresponds to a binary vector given by the indicator function, i.e. ${\displaystyle x_i\in \{0,1\}}$. However, it does not generalize the Jaccard Index to probability distributions, where a set corresponds to a uniform probability distribution, i.e.

${\displaystyle x_i=\{\begin{array}{ll}\frac{1}{|X|}& i\in X\\ 0& \text{otherwise}\end{array}}$

It is always less if the sets differ in size. If ${\displaystyle |X|>|Y|}$, and ${\displaystyle x_i={\mathbf{1}}_X(i)/|X|,y_i={\mathbf{1}}_Y(i)/|Y|}$ then

${\displaystyle J_{\mathcal{W}}(x,y)=\frac{|X\cap Y|}{|X\setminus Y|+|X|}<J(X,Y).}$

Instead, a generalization that is continuous between probability distributions and their corresponding support sets is

${\displaystyle J_{\mathcal{P}}(x,y)=\sum _{x_i\ne 0,y_i\ne 0}\frac{1}{\sum _{j}max\left(\frac{x_j}{x_i},\frac{y_j}{y_i}\right)}}$

which is called the "Probability" Jaccard. It has the following bounds against the Weighted Jaccard on probability vectors.

${\displaystyle J_{\mathcal{W}}(x,y)\le J_{\mathcal{P}}(x,y)\le \frac{2J_{\mathcal{W}}(x,y)}{1+J_{\mathcal{W}}(x,y)}}$

Here the upper bound is the (weighted) Sørensen–Dice coefficient. The corresponding distance, ${\displaystyle 1-J_{\mathcal{P}}(x,y)}$, is a metric over probability distributions, and a pseudo-metric over non-negative vectors.

The Probability Jaccard Index has a geometric interpretation as the area of an intersection of simplices. Every point on a unit ${\displaystyle k}$-simplex corresponds to a probability distribution on ${\displaystyle k+1}$ elements, because the unit ${\displaystyle k}$-simplex is the set of points in ${\displaystyle k+1}$ dimensions that sum to 1. To derive the Probability Jaccard Index geometrically, represent a probability distribution as the unit simplex divided into sub simplices according to the mass of each item. If you overlay two distributions represented in this way on top of each other, and intersect the simplices corresponding to each item, the area that remains is equal to the Probability Jaccard Index of the distributions.

Optimality of the Probability Jaccard Index

Consider the problem of constructing random variables such that they collide with each other as much as possible. That is, if ${\displaystyle X\sim x}$ and ${\displaystyle Y\sim y}$, we would like to construct ${\displaystyle X}$ and ${\displaystyle Y}$ to maximize ${\displaystyle Pr[X=Y]}$. If we look at just two distributions ${\displaystyle x,y}$ in isolation, the highest ${\displaystyle Pr[X=Y]}$ we can achieve is given by ${\displaystyle 1-\text{TV}(x,y)}$ where ${\displaystyle \text{TV}}$ is the Total Variation distance. However, suppose we weren't just concerned with maximizing that particular pair, suppose we would like to maximize the collision probability of any arbitrary pair. One could construct an infinite number of random variables one for each distribution ${\displaystyle x}$, and seek to maximize ${\displaystyle Pr[X=Y]}$ for all pairs ${\displaystyle x,y}$. In a fairly strong sense described below, the Probability Jaccard Index is an optimal way to align these random variables.

For any sampling method ${\displaystyle G}$ and discrete distributions ${\displaystyle x,y}$, if ${\displaystyle Pr[G(x)=G(y)]>J_{\mathcal{P}}(x,y)}$ then for some ${\displaystyle z}$ where ${\displaystyle J_{\mathcal{P}}(x,z)>J_{\mathcal{P}}(x,y)}$ and ${\displaystyle J_{\mathcal{P}}(y,z)>J_{\mathcal{P}}(x,y)}$, either ${\displaystyle Pr[G(x)=G(z)]<J_{\mathcal{P}}(x,z)}$ or ${\displaystyle Pr[G(y)=G(z)]<J_{\mathcal{P}}(y,z)}$.

That is, no sampling method can achieve more collisions than ${\displaystyle J_{\mathcal{P}}}$ on one pair without achieving fewer collisions than ${\displaystyle J_{\mathcal{P}}}$ on another pair, where the reduced pair is more similar under ${\displaystyle J_{\mathcal{P}}}$ than the increased pair. This theorem is true for the Jaccard Index of sets (if interpreted as uniform distributions) and the probability Jaccard, but not of the weighted Jaccard. (The theorem uses the word "sampling method" to describe a joint distribution over all distributions on a space, because it derives from the use of weighted minhashing algorithms that achieve this as their collision probability.)

This theorem has a visual proof on three element distributions using the simplex representation.

Tanimoto similarity and distance

Various forms of functions described as Tanimoto similarity and Tanimoto distance occur in the literature and on the Internet. Most of these are synonyms for Jaccard similarity and Jaccard distance, but some are mathematically different. Many sources cite an IBM Technical Report as the seminal reference.

In "A Computer Program for Classifying Plants", published in October 1960, a method of classification based on a similarity ratio, and a derived distance function, is given. It seems that this is the most authoritative source for the meaning of the terms "Tanimoto similarity" and "Tanimoto Distance". The similarity ratio is equivalent to Jaccard similarity, but the distance function is not the same as Jaccard distance.

Tanimoto's definitions of similarity and distance

In that paper, a "similarity ratio" is given over bitmaps, where each bit of a fixed-size array represents the presence or absence of a characteristic in the plant being modelled. The definition of the ratio is the number of common bits, divided by the number of bits set (i.e. nonzero) in either sample.

Presented in mathematical terms, if samples X and Y are bitmaps, ${\displaystyle X_i}$ is the ith bit of X, and ${\displaystyle \wedge ,\vee }$ are bitwise and, or operators respectively, then the similarity ratio ${\displaystyle T_s}$ is

${\displaystyle T_s(X,Y)=\frac{\sum _i(X_i\wedge Y_i)}{\sum _i(X_i\vee Y_i)}}$

If each sample is modelled instead as a set of attributes, this value is equal to the Jaccard index of the two sets. Jaccard is not cited in the paper, and it seems likely that the authors were not aware of it.

Tanimoto goes on to define a "distance" based on this ratio, defined for bitmaps with non-zero similarity:

${\displaystyle T_d(X,Y)=-{\log }_2(T_s(X,Y))}$

This coefficient is, deliberately, not a distance metric. It is chosen to allow the possibility of two specimens, which are quite different from each other, to both be similar to a third. It is easy to construct an example which disproves the property of triangle inequality.

Other definitions of Tanimoto distance

Tanimoto distance is often referred to as a synonym for Jaccard distance ${\displaystyle 1-T_s}$. This function is a proper distance metric. In application, Tanimoto distance can be harmfully confused with Jaccard distance as a proper distance metric.

If Jaccard or Tanimoto similarity is expressed over a bit vector, then it can be written as

${\displaystyle f(A,B)=\frac{A\cdot B}{\Vert A{\Vert }^2+\Vert B{\Vert }^2-A\cdot B}}$

where the same calculation is expressed in terms of vector scalar product and magnitude. This representation relies on the fact that, for a bit vector (where the value of each dimension is either 0 or 1) then

${\displaystyle A\cdot B=\sum _i{A}_i{B}_i=\sum _i(A_i\wedge B_i)}$

and

${\displaystyle \Vert A{\Vert }^2=\sum _i{A}_i^2=\sum _i{A}_i.}$

This is a potentially confusing representation, because the function as expressed over vectors is more general, unless its domain is explicitly restricted. Properties of ${\displaystyle T_s}$ do not necessarily extend to ${\displaystyle f}$. In particular, the difference function ${\displaystyle 1-f}$ does not preserve triangle inequality, and is not therefore a proper distance metric, whereas ${\displaystyle 1-T_s}$ is.

There is a real danger that the combination of "Tanimoto Distance" being defined using this formula, along with the statement "Tanimoto Distance is a proper distance metric" will lead to the false conclusion that the function ${\displaystyle 1-f}$ is in fact a distance metric over vectors or multisets in general, whereas its use in similarity search or clustering algorithms may fail to produce correct results.

Lipkus uses a definition of Tanimoto similarity which is equivalent to ${\displaystyle f}$, and refers to Tanimoto distance as the function ${\displaystyle 1-f}$. It is, however, made clear within the paper that the context is restricted by the use of a (positive) weighting vector ${\displaystyle W}$ such that, for any vector A being considered, ${\displaystyle A_i\in \{0,W_i\}.}$ Under these circumstances, the function is a proper distance metric, and so a set of vectors governed by such a weighting vector forms a metric space under this function.

Jaccard index in binary classification confusion matrices

In confusion matrices employed for binary classification, the Jaccard index can be framed in the following formula:

${\displaystyle \text{Jaccard index}=\frac{TP}{TP+FP+FN}}$

where TP are the true positives, FP the false positives and FN the false negatives.

The binary classification formula of the Jaccard Index measures how the predicted positive results match with the actual positive results. It shows how much overlap of what a model predicts are true positive cases to real positive cases. When the Jaccard index is higher it means that the prediction is closer to the actual result.

The Jaccard index is an overlap metric that can be defined with the elements in a confusion matrix. The true positives represent the cases that are predicted positive and are actually positive, creating an overlap of the two groups. The false positives are cases that were predicted positive but are actually not. Similarly, false negatives are cases that were predicted negative but in reality are actually positive. The Jaccard index compares the true positives to the set of relevant information.

Jaccard index is useful when trying to compare predicted results against actual results. Using binary classification alongside with Jaccard index helps explain how reliable a prediction model is. It is used in many fields, and commonly used in medicine for lab testing.

Application to computer science and graph theory

In computer science, the Jaccard Index can be used to measure similarity between vertices in a graph by comparing their adjacency sets. Given two vertices, their similarity is calculated by taking the size of the intersection of their neighborhoods divided by the size of their union. This measure is widely applied in Link prediction, community detection, and graph classification, where it serves as a guide to estimate the likelihood of an edge forming between two nodes in networks.

The computation of the Jaccard similarity between two vertices can be expressed using their adjacency sets, as shown below.

<span id="mwAks"></span><span class="c1" id="mwAkw">// Javascript Code:</span> <span class="kd" id="mwAk0">function</span><span class="w" id="mwAk4"> </span><span class="nx" id="mwAk8">jaccardSimilarity</span><span class="p" id="mwAlA">(</span><span class="nx" id="mwAlE">graph1</span><span class="p" id="mwAlI">,</span><span class="w" id="mwAlM"> </span><span class="nx" id="mwAlQ">graph2</span><span class="p" id="mwAlU">){</span> <span class="w" id="mwAlY"> </span><span class="kd" id="mwAlc">const</span><span class="w" id="mwAlg"> </span><span class="nx" id="mwAlk">numNodes1</span><span class="w" id="mwAlo"> </span><span class="o" id="mwAls">=</span><span class="w" id="mwAlw"> </span><span class="nx" id="mwAl0">graph1</span><span class="p" id="mwAl4">.</span><span class="nx" id="mwAl8">length</span><span class="p" id="mwAmA">;</span> <span class="w" id="mwAmE"> </span><span class="kd" id="mwAmI">const</span><span class="w" id="mwAmM"> </span><span class="nx" id="mwAmQ">numNodes2</span><span class="w" id="mwAmU"> </span><span class="o" id="mwAmY">=</span><span class="w" id="mwAmc"> </span><span class="nx" id="mwAmg">graph2</span><span class="p" id="mwAmk">.</span><span class="nx" id="mwAmo">length</span><span class="p" id="mwAms">;</span> <span class="w" id="mwAmw"> </span><span class="kd" id="mwAm0">let</span><span class="w" id="mwAm4"> </span><span class="nx" id="mwAm8">similarity</span><span class="w" id="mwAnA"> </span><span class="o" id="mwAnE">=</span><span class="w" id="mwAnI"> </span><span class="mf" id="mwAnM">0</span><span class="p" id="mwAnQ">;</span> <span class="w" id="mwAnU"> </span> <span class="w" id="mwAnY"> </span><span class="c1" id="mwAnc">// Iterate over all pairs of nodes in both graphs</span> <span class="w" id="mwAng"> </span><span class="k" id="mwAnk">for</span><span class="p" id="mwAno">(</span><span class="kd" id="mwAns">let</span><span class="w" id="mwAnw"> </span><span class="nx" id="mwAn0">i</span><span class="w" id="mwAn4"> </span><span class="o" id="mwAn8">=</span><span class="w" id="mwAoA"> </span><span class="mf" id="mwAoE">0</span><span class="p" id="mwAoI">;</span><span class="w" id="mwAoM"> </span><span class="nx" id="mwAoQ">i</span><span class="w" id="mwAoU"> </span><span class="o" id="mwAoY"><</span><span class="w" id="mwAoc"> </span><span class="nx" id="mwAog">numNodes1</span><span class="p" id="mwAok">;</span><span class="w" id="mwAoo"> </span><span class="nx" id="mwAos">i</span><span class="o" id="mwAow">++</span><span class="p" id="mwAo0">){</span> <span class="w" id="mwAo4"> </span><span class="k" id="mwAo8">for</span><span class="p" id="mwApA">(</span><span class="kd" id="mwApE">let</span><span class="w" id="mwApI"> </span><span class="nx" id="mwApM">j</span><span class="w" id="mwApQ"> </span><span class="o" id="mwApU">=</span><span class="w" id="mwApY"> </span><span class="mf" id="mwApc">0</span><span class="p" id="mwApg">;</span><span class="w" id="mwApk"> </span><span class="nx" id="mwApo">j</span><span class="w" id="mwAps"> </span><span class="o" id="mwApw"><</span><span class="w" id="mwAp0"> </span><span class="nx" id="mwAp4">numNodes2</span><span class="p" id="mwAp8">;</span><span class="w" id="mwAqA"> </span><span class="nx" id="mwAqE">j</span><span class="o" id="mwAqI">++</span><span class="p" id="mwAqM">){</span> <span class="w" id="mwAqQ"> </span><span class="c1" id="mwAqU">// Calculate the size of the intersection and union of the neighbor sets</span> <span class="w" id="mwAqY"> </span><span class="kd" id="mwAqc">const</span><span class="w" id="mwAqg"> </span><span class="nx" id="mwAqk">intersectionSize</span><span class="w" id="mwAqo"> </span><span class="o" id="mwAqs">=</span><span class="w" id="mwAqw"> </span><span class="nx" id="mwAq0">intersection</span><span class="p" id="mwAq4">(</span><span class="nx" id="mwAq8">graph1</span><span class="p" id="mwArA">[</span><span class="nx" id="mwArE">i</span><span class="p" id="mwArI">],</span><span class="nx" id="mwArM">graph2</span><span class="p" id="mwArQ">[</span><span class="nx" id="mwArU">j</span><span class="p" id="mwArY">]).</span><span class="nx" id="mwArc">length</span><span class="p" id="mwArg">;</span> <span class="w" id="mwArk"> </span><span class="kd" id="mwAro">const</span><span class="w" id="mwArs"> </span><span class="nx" id="mwArw">unionSize</span><span class="w" id="mwAr0"> </span><span class="o" id="mwAr4">=</span><span class="w" id="mwAr8"> </span><span class="nx" id="mwAsA">union</span><span class="p" id="mwAsE">(</span><span class="nx" id="mwAsI">graph1</span><span class="p" id="mwAsM">[</span><span class="nx" id="mwAsQ">i</span><span class="p" id="mwAsU">],</span><span class="nx" id="mwAsY">graph2</span><span class="p" id="mwAsc">[</span><span class="nx" id="mwAsg">j</span><span class="p" id="mwAsk">]).</span><span class="nx" id="mwAso">length</span><span class="p" id="mwAss">;</span> <span class="w" id="mwAsw"> </span> <span class="w" id="mwAs0"> </span><span class="c1" id="mwAs4">// Calculate the Jaccard similarity and add it to the total</span> <span class="w" id="mwAs8"> </span><span class="nx" id="mwAtA">similarity</span><span class="w" id="mwAtE"> </span><span class="o" id="mwAtI">+=</span><span class="w" id="mwAtM"> </span><span class="nx" id="mwAtQ">intersectionSize</span><span class="w" id="mwAtU"> </span><span class="o" id="mwAtY">/</span><span class="w" id="mwAtc"> </span><span class="nx" id="mwAtg">unionSize</span><span class="p" id="mwAtk">;</span> <span class="w" id="mwAto"> </span><span class="p" id="mwAts">}</span> <span class="w" id="mwAtw"> </span><span class="p" id="mwAt0">}</span> <span class="w" id="mwAt4"> </span> <span class="w" id="mwAt8"> </span><span class="c1" id="mwAuA">// Divide the total similarity by the number of node pairs to get the average</span> <span class="w" id="mwAuE"> </span><span class="k" id="mwAuI">return</span><span class="w" id="mwAuM"> </span><span class="nx" id="mwAuQ">similarity</span><span class="w" id="mwAuU"> </span><span class="o" id="mwAuY">/</span><span class="w" id="mwAuc"> </span><span class="p" id="mwAug">(</span><span class="nx" id="mwAuk">numNodes1</span><span class="w" id="mwAuo"> </span><span class="o" id="mwAus">*</span><span class="w" id="mwAuw"> </span><span class="nx" id="mwAu0">numNodes2</span><span class="p" id="mwAu4">);</span> <span class="p" id="mwAu8">}</span> <span class="c1" id="mwAvA">// Helper function to compute the intersection of two arrays</span> <span class="kd" id="mwAvE">function</span><span class="w" id="mwAvI"> </span><span class="nx" id="mwAvM">intersection</span><span class="p" id="mwAvQ">(</span><span class="nx" id="mwAvU">a</span><span class="p" id="mwAvY">,</span><span class="w" id="mwAvc"> </span><span class="nx" id="mwAvg">b</span><span class="p" id="mwAvk">)</span><span class="w" id="mwAvo"> </span><span class="p" id="mwAvs">{</span> <span class="w" id="mwAvw"> </span><span class="k" id="mwAv0">return</span><span class="w" id="mwAv4"> </span><span class="nx" id="mwAv8">a</span><span class="p" id="mwAwA">.</span><span class="nx" id="mwAwE">filter</span><span class="p" id="mwAwI">(</span><span class="nx" id="mwAwM">value</span><span class="w" id="mwAwQ"> </span><span class="p" id="mwAwU">=></span><span class="w" id="mwAwY"> </span><span class="nx" id="mwAwc">b</span><span class="p" id="mwAwg">.</span><span class="nx" id="mwAwk">includes</span><span class="p" id="mwAwo">(</span><span class="nx" id="mwAws">value</span><span class="p" id="mwAww">));</span> <span class="p" id="mwAw0">}</span> <span class="c1" id="mwAw4">// Helper function to compute the union of two arrays</span> <span class="kd" id="mwAw8">function</span><span class="w" id="mwAxA"> </span><span class="nx" id="mwAxE">union</span><span class="p" id="mwAxI">(</span><span class="nx" id="mwAxM">a</span><span class="p" id="mwAxQ">,</span><span class="w" id="mwAxU"> </span><span class="nx" id="mwAxY">b</span><span class="p" id="mwAxc">){</span> <span class="w" id="mwAxg"> </span><span class="k" id="mwAxk">return</span><span class="w" id="mwAxo"> </span><span class="p" id="mwAxs">[...</span><span class="ow" id="mwAxw">new</span><span class="w" id="mwAx0"> </span><span class="nb" id="mwAx4">Set</span><span class="p" id="mwAx8">([...</span><span class="nx" id="mwAyA">a</span><span class="p" id="mwAyE">,</span><span class="w" id="mwAyI"> </span><span class="p" id="mwAyM">...</span><span class="nx" id="mwAyQ">b</span><span class="p" id="mwAyU">])];</span> <span class="p" id="mwAyY">}</span>

Above shows an implementation based on set operations over adjacency lists. In practice, graph representations like adjacency lists are used to improve the efficiency of intersection and union math. For large graphs, computing similarity across all pairs of vertices may be computationally expensive. Programmers may use approximations to avoid taking on the entire cost of this computation.