# Interpretation of Jaccard similarity for binary networks

Given two undirected networks with the same amount of nodes defined by $A_{ij}^1$ and $A_{ij}^2$, we take the unique unordered pairs $(i, j)$. After sorting them, we then have two binary vectors $\vec{A}^1 = (A_{12}^1, A_{13}^1, ...)$ and $\vec{A}^2 = (A_{12}^2, A_{13}^2, ...)$.

For example, if an edge between nodes 1 and 2 is present in both networks, we have that $\vec{A}^1_1 = 1$ and $\vec{A}^2_1 = 1$. In other words, the two ordered vectors code the simultaneous presence $(00, 01, 10, 11)$ of the same edge $(i,j)$ in network 1 and 2.

The Jaccard similarity between $\vec{A}^1$ and $\vec{A}^2$ is then defined as $$J(\vec{A}^1, \vec{A}^2) = \frac{\sum_i \vec{A}^1_i \wedge \vec{A}^2_i}{\sum_i \vec{A}^1_i \vee \vec{A}^2_i}.$$

Question 1: Quoting from Bargigli et al. (2013),

The Jaccard similarity [between $\vec{A}^1$ and $\vec{A}^2$] can be defined as the probability of observing a link in a network conditional on the observation of the same link in the other network.

I don't understand why, given $ij$, $$P(A_{ij}^2 = 1 | A_{ij}^1 = 1) = \frac{P(A_{ij}^1 = 1, A_{ij}^2 = 1)}{P(A_{ij}^1 = 0, A_{ij}^2 = 1) + P(A_{ij}^1 = 1, A_{ij}^2 = 1)}$$ amounts to that. The numerator and denominator hint at the definition of $J$ but I'm unsure. I think $ij$ also needs to be marginalized out and some symmetry exploited, but I'm stuck. Also, do we need to assume independence between the networks? Would any of this change for a directed network, i.e. $A_{ij}^k$ need not be symmetric?

Question 2: The Jaccard distance $d = 1 - J$ is a proper metric. When using it for hierarchical clustering with UPGMA linkage, the distance between two clusters $A$ and $B$ is defined as $$d(A,B) = \frac{1}{|A||B|} \sum_{a \in A, b \in B} d(a, b) ,$$ which, if question 1 is resolved, could be written as $$d(A,B) = \frac{1}{|A||B|} \sum_{a \in A, b \in B} (1 - P(\text{link exists in b given that it exists in a})).$$ Can we deduce some interpretation from this in terms of the probability of observing edges in the networks in clusters $A$ and $B$?

I'd be very grateful for any clue.

Your setup discusses a single network $A$ along with a single network $B$. In this case, the probabilities would be defined over the collection of edges. That is, for a particular edge $(i,j)$, e.g. $(i=1,j=2)$, we either have $A_{ij}=0$ or $A_{ij}=1$. There is no uncertainty here. Non-trivial probabilities can be computed over a varying $i$ and/or $j$, e.g. $p(A_{ij}|i)=\frac{1}{n}\sum_{j\neq{i}}A_{ij}$ would be the probability of an edge connected to node $i$ (assuming $n$ nodes).
On the other hand, your questions seem to be about some hypothetical ensemble of network pairs $(A,B)$. This is the only way to have uncertainty in $p(A_{ij})$, for example. (Otherwise it is just $0$ or $1$.)
For a directed graph, the transform to a "flat binary vector" would differ*, but the calculations would be the same (*i.e. you need to consider ordered $(i,j)$ pairs).