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

enter image description here

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...

  • 1
    $\begingroup$ 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. $\endgroup$ – Misha Lavrov Mar 24 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.