1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Indeed, the edge must be anonymous for uncertainty to occur. But never mind, I figured it out. $\endgroup$ – marnix May 12 '17 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.