Given a mesh network of N nodes, where each node is connected to C other nodes, what is the probability a node is connected to another directly, or indirectly through a maximum of D bridge nodes?

Please look for the latest attempt within the answers.

Attempt 1 (wrong)

(As pointed by Amaury.)

I have developed a function, but I doubt it is correct for 1) I've never been good at calculating probabilities, and 2) it is easy for this function to yield greater than 1 probabilities. Here it goes anyway:

The probability of a direct connection would be $$P(N,C,0) = \frac{1}{N-1}$$

The probability of an indirect connection should be multiplied by $C$, which yields

$$P(N,C,1) = \frac{1}{N-1} + C \frac{1}{N-1}$$

Abstracting the pattern, we should get

$$P(N,C,2) = \frac{1}{N-1} + C \left(\frac{1}{N-1} + C \left(\frac{1}{N-1}\right)\right)$$

for a depth of 2 bridge nodes. And generalizing the abstraction, I get

$$P(N,C,D) = \frac{1}{N-1} \sum_{n=0}^{D}{C^{D-n}}$$

Now, is this correct? Please point my flaws otherwise.

Attempt 3

(By author.)

This is a totally different approach. The following assumptions were made to develop it:

  • Though node A is connected to a network of nodes with $C^D$ connections, the network doesn't have as much nodes as it does connections. It may consist of as little as $C+1$ nodes, and as much as N nodes.
  • A node directly connected to A is as helpful as a node indirectly connected to A if serves as a bridge node between A and B.

So I figured this time the probability of A being connected to B must have the form $$P = \frac{S}{N-1}$$ where $S$ is the amount of nodes in A's network.

The probability $P_n$ of discovering $C$ new nodes by picking them at random from the network of $N$ nodes in the $n$th try is given by $$P_n = \frac{ _{F_n}C_C }{ _NC_C }$$

Where $F$ is the amount of nodes in the network yet to pick. $$F_n=N-S_n$$ Where $S_n$ grows from $S_0 = 0$ with each iteration, until $C^D$ iterations are reached. In fact, $$S_n = C P_n$$

So $S$ is given by $$S = \sum_{n=1}^{C^D}{C P_n}$$

Then the probability $P$ is fully defined by the parameters $N$, $C$ and $D$. The algorithm found is very prone to taking up long computation times.

Your formulas are wrong, consider the extreme case in which $C=N-1$, then the probability of any node being connected to other one is $0$, however your first formula always yields $\frac{1}{N-1}$. If you keep considering this case, your second, third, and generalized formulas give a number greater than $1$!

Your first formula should be given nodes $a$ and $b$ out of $N$ nodes in which each one is connected to other $C$ nodes:

$$ P(\mbox{a and b are connected})=\frac{C}{N-1} $$

you just have to think about it as: "I have a node, and I will pick up another randomly out of $N-1$ of which $C$ are connected to the one I have". Sadly, I think there is not enough information to generalize this further.

  • That makes sense, but for a direct connection only, am I right? What other parameters do you think are necessary to find the probability function? – Severo Raz Aug 8 '13 at 1:26

Attempt 2 (wrong)

(By author.)

As Amaury pointed out, the probability of a direct connection is $$P = C\frac{1}{N-1} $$

Bayes' Law points that the probability of node A being connected to B is the sum of the probabilities of A being connected to B directly, plus the probability of A being connected to B indirectly given a is not connected to B directly, from which I have abstracted the following generalization: $$P_{AB}(N,C,D) = \frac{1}{N-1} C \left(1 + p_1 \right) $$

where $$ p_n(N,C,D) = (C-1-(D-1)P_{XYd})(1 + p_{n+1})$$ (which is the numerator of the probability of a child node being connected to node B,) and $$p_{D+1} = 0$$

$$ P_{XYd} = \frac{C-1}{N-1}$$ (Probability of a child node being connected to another node which is not its parent. Used to account for possible nodes connected-to that are not connected to B.)

This attempt (too) yields probabilities greater than one, but I've come to think this is bound to happen in a mesh network for there will be more than one probable paths.

For a sufficiently large network, $P_{XYd} \approx 0$, so the formula can be estimated to be $$P_{AB}(N,C,D) = \frac{C}{N-1} \sum_{n=0}^{D}{(C-1)^n}$$

Again, please point the flaws in my developments.

  • Oh well I jumped to conclusions too fast on why the probability would surpass the unit. This should not happen no matter the depth of the network indirect connections. It is possible that all nodes connected to A are only connected to each other and not to node B. – Severo Raz Aug 9 '13 at 3:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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