Probability of a node being connected directly or indirectly to another in a mesh network

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.