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

Networkprobability

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.

Best Answer

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.

Related Question