I've got a directed, probabilistic graph (network). See the picture below for a super-simple example:

enter image description here

The adjacency matrix $\mathbf{A}$ has values between zero and one, and it isn't a symmetric matrix.

For each node, I want to calculate some statistic $f_o(\mathbf{A})$, where $o$ is the order -- first-order, second-order, etc. So for example, the mean among neighbors and neighbor's neighbors, etc.

For the first-order network, this is just the weighted average. So for node (a), $\frac{30 \times .8 + 20 \times 0 + 40\times .7}{.8+.7} = 34.67$

But for a second-order network, I'd have to account both for the probability that a given node is linked, and then the probability that it is linked to another link. So, (a) goes to (d) with probability .3 -- in that case it is a first-order link. As a second-order link however, (a) could go to (d) though (c) with probability .2, or through (b) with probability .3.

I suppose that the probability that it is linked at all up to order $o$ could be calculated though basic probability rules using unions and intersections and such. Hence my first question:

Is there some quick, vectorized way of calculating a probabilistic second-order adjacency matrix from a first-order adjacency matrix?

In other words, $\mathbf{A}_1$ contains the probabilities that $i$ is linked to $j$ directly. I want $\mathbf{A}_2$, which would contain the probabilities that $i$ is linked to $j$ through no more than 1 intermediary node.

My harder (I think) question is the following:

Given a probabilistic graph ($\mathbf{A}_1$), how can I calculate $f_1(\mathbf{A}), f_2(\mathbf{A}) ... f_o(\mathbf{A})$, where each $o$ is only $o$th order links?

This seems hard because one can't have simultaneous set membership. In other words, if there is a high probability that you are a first-order link, there has to be a correspondingly lower probability that you are a second-order link, even if it is highly likely that there is a path through an intermediary.

I suppose that this could be done by first calculating $\mathbf{A_1}$, and then a different version of $\mathbf{A_2}, ... \mathbf{A_o}$, such that they reflect the probabilities that $i$ is connected to $j$ only thorough $o-1$ intermediary nodes. The answer for $\mathbf{A}_2$ would then be elementwise $\mathbf{A_2}|(1-\mathbf{A_1})$. But how would I compute this other variety of $\mathbf{A}_{2:o}$?


Your Answer

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

Browse other questions tagged or ask your own question.