# Probability of random graph being connected - block model

Let $$n\in \mathbb{N}$$ be given. Let us assume that the set of vertices is $$V=[n]=\mathcal{C}^+ \cup \mathcal{C}^- \cup \mathcal{D}$$, where the sets $$\mathcal{C}^+$$ and $$\mathcal{C}^-$$ stand for the nodes in the graph which can have either only out-going and only in-going links respectively or no links and the set $$\mathcal{D}$$ describes the nodes in the network which can have both, in- and out-going links. Next, let

be the matrix containing all the possible probabilities of having an edge between two vertices. From this matrix $$B$$ we will generate a graph. The produced actual graph then allows us to redefine the sets of node-types to the following sets: \begin{align*} &\mathrm{C}^+ =\{i \in V | k_i>0, j_i =0 \},\\ &\mathrm{C}^- =\{i \in V | k_i=0, j_i >0 \},\\ &\mathrm{D} =\{i \in V | k_i>0, j_i >0 \},\\ &\mathrm{X} =\{i \in V | k_i=0, j_i =0 \}. \end{align*} ($$k_i$$ is the out-degree, $$j_i$$ stands for the in-degree)

Note that the sets from before do not have to coincide with the redefined sets, as we also have for example the possibility, that an initial node in $$\mathcal{D}$$ ends up having only out-going links, so it would be counted as an element of $$\mathrm{C}^+$$. Or since it also possible that a node does not have any link to or from another node, we get the set $$\mathrm{X}$$ of unconnected nodes.

What will be the precise probability that the resulting graph is connected?

@MishaLavrov already made me aware that it is not enough to calculate $$\mathbb{P}(X= \emptyset)$$ as this only means that we won't have any isolated nodes.

So my idea would be to calculate the probabilities for $$i \in \mathcal{C}^+, \mathcal{C}^-, \mathcal{D}$$ having $$k$$ neighbors and then reducing it to the case where we remove the node $$i$$ with its $$k$$ neighbors, so we only have a graph on $$n-k$$ nodes. However I don't know how to proceed from there on and I am not convinced that this is the best approach...

• I would start working from the exact probability for $\mathcal G_{n,p}$. It is also most likely true that the probability of being connected converges to the probability that $X = \varnothing$ in the limit: larger connected components are much less likely to appear. – Misha Lavrov Mar 24 at 16:48