Expected number of connections between different colour nodes in a network with variable connectivity

80 Views Asked by At

Background

There is a network of $N$ nodes.

Each node has a colour: Red; Green or Blue (in a more general form they may be additional colours, but there is at least one other colour that Red and Green)

Colours have been randomly assigned to nodes.

Each node has a number of connections (also known as a degree of connectitivity), $k$ to distinct other nodes. Every node has at least 1 connection and no node has more than $n$ connections. (i.e. there are no isolated vertexes. $\Delta\left(G\right)=n$ and $\delta\left(G\right)=1$ to use the notation from this wikipedia page.)

The connectivity number of each node was randomly assigned independently from the colour assignment.

There is no concept of direction of a connection in this network.

Given

We know the distribution function for connectivity number ignoring colours:

$$ N=\sum^{n}_{k=1}N_k $$

We know the number of Red nodes, $N^R$ and the numbers of them as a function of their connectivity:

$$ N^R=\sum^{n}_{k=1}N^R_k $$

Also for Green nodes:

$$ N^G=\sum^{n}_{k=1}N^G_k $$

The distributions for other colours is knowable if necessary for solving the problem, but I believe it is not required.

Problem

Over all possible networks with the specified values of $N_k$, $N^R_k$, $N^G_k$ and $n$ for $1\le k \le n$.

If a Red node of connectivity $k$ is chosen at random, what is the probability that $j$ of those connections are to Green nodes (irrespective of the Green node connectivity)

Alternatively,

What is the expected number of the $N^R_k$ Red nodes with connectivity $k$ that have exactly $j$ connections to Green nodes ($1\le j\le k$)

Attempt 1 (2021-09-10)

NOTE: I will consider an acceptable answer if you can show this attempt to be correct.

NOTE: I believe this attempt to be incorrect!

Because each connection is to a distinct node, from the context of a randomly selected red node of degree $k$, it has selected $k$ other nodes from the remaining $N-1$.

The contingency table should look like this:

connected not connected total
green nodes $j$ $N^G-j$ $N^G$
not green $k-j$ $N-1-N^G-k+j$ $N-1-N^G$
total $k$ $N-1-k$ $N-1$

The probability of having exactly $j$ connections to a green node then comes from the hypergeometric distribution

$$ P(\text{\(j\) green connections}|\text{red node of degree \(k\)})=\frac{{{N^G}\choose{j}} {{N-1-N^G}\choose{k-j}}}{{{N-1}\choose{k}}} $$

We know the probability of a red node with degree $k$:

$$ P(\text{red node of degree \(k\)})=\frac{N^R}{N} $$

So the probability that a node selected at random is a red node of degree $k$ with $j$ connections to green nodes is then:

$$ P(\text{red node of degree \(k\) with \(j\) green connections}) = P(\text{red node of degree \(k\)})P(\text{\(j\) green connections}|\text{red node of degree \(k\)}) = \frac{N^R}{N}\frac{{{N^G}\choose{j}} {{N-1-N^G}\choose{k-j}}}{{{N-1}\choose{k}}} $$

And thus in a network of $N$ nodes the expected number of red nodes of degree $k$ with exactly $j$ connections to green nodes is given by:

$$ {N^R}\frac{{{N^G}\choose{j}} {{N-1-N^G}\choose{k-j}}}{{{N-1}\choose{k}}} $$

Where $1\le j \le k \le n$ and $N^G \ge j$

Attempt 1 is wrong (2021-09-12)

Consider $N=100$, $N^R=N^R_1=1$ and $N^G=N^G_{99}=1$ here the expected number of red balls of degree 1 with 1 connection to a green ball is, by construction, 1, but my attempt gives a number less than 1.

Thus my attempt 1 cannot be correct