1
$\begingroup$

I am considering Bollobas' directed random configuration graph of size $N$, constructed by the following random algorithm:

  1. Draw a sequence of $N$ node-degree pairs $(j_1,k_1),...,(j_N,k_N)$ independently from the degree distribution $P$. Accept the draw only if it is feasible, i.e. only if $\sum_{n \in [N]}(j_n-k_n)=0$.

  2. For every node $n$, create $j_n$ in-stubs and $k_n$ out-stubs, where in-/out-stubs are open ended half-edges with an in-/out-arrow.

  3. For any unpaired out-stub, select iteratively uniformly at random an unpaired in-stub and connect them.

Each such resulting pair of stubs forms a directed edge of the graph.

I am interested in the probabilities of an edge. My suggestion is:

Under this random matching approach, the probability that there is an edge from a node $i$ to a node $l$ is, with $m$ being the number of all edges: $$p_{il}=\frac{k_i \cdot j_l}{(2m-1)},$$ as node $i$ has $k_i$ out-stubs and $j_l$ in-stubs out of $2m-1$ (excluding of node $i$) attached to $l$ to which it could connect.

And similarly the probability that there is an edge from a node $l$ to $i$ is:$$p_{il}=\frac{j_i \cdot k_l}{(2m-1)}$$

Is this correct, or am I missing something?

$\endgroup$
2
$\begingroup$

We can choose a uniformly random matching in any order. So let's choose the $k_i$ edges out of node $i$ one at a time and see the probability none of them go to node $l$.

The first edge we choose has probability $\frac{j_l}{m}$ of going to $l$. If it doesn't, then the second edge has probability $\frac{j_l}{m-1}$. If that also doesn't happen, then the third edge has probability $\frac{j_l}{m-2}$, and so on. So the overall probability that none of the edges go to node $l$ is $$ 1-p_{il} = \left(1 - \frac{j_l}{m}\right)\left(1 - \frac{j_l}{m-1}\right) \dotsb \left(1 - \frac{j_l}{m-k_i+1}\right) $$ and the probability you want is the complement of this one.

Asymptotically, however, assuming $k_i$ and $j_l$ are small relative to $m$, the answer is in fact close to $\frac{k_i \cdot j_l}{m}$ which is what you have, except that $m$ and not $2m-1$ is the number of options for the first edge. (Unlike the undirected configuration model, here there are $m$ out-stubs and $m$ in-stubs, which we distinguish.)

Additionally, because there are $k_i$ edges with probability $\frac{j_l}{m}$ of going to $l$, then $\frac{k_i j_l}{m}$ edges is the expected number of edges from $i$ to $l$.

$\endgroup$
  • $\begingroup$ So I guess there is no "neat" form for the probability as in the undirected one, where it is of the form $p_{ij} =\frac{ k_i k_j} {2m−1}$. ? (Only for the large limits as you stated $p_{il} =\frac{ k_i j_l} {m}$) $\endgroup$ – Alisat Jan 6 at 18:35
  • 1
    $\begingroup$ The "neat" form is not the probability but the expected number of edges from $i$ to $l$. $\endgroup$ – Misha Lavrov Jan 6 at 20:10
  • $\begingroup$ And for the undirected case, the formula you give is also the expectation, not the probability. $\endgroup$ – Misha Lavrov Jan 6 at 20:15
  • 1
    $\begingroup$ The paper does not use the configuration mode. Instead, they define $p_{ij} = \frac{k_i k_j}{2m}$ then add an edge $ij$ with that probability. As they mention on p. 3 (second paragraph) the actual degree of vertex $i$ is not guaranteed to be $k_i$ in this model. $\endgroup$ – Misha Lavrov Jan 6 at 21:19
  • 1
    $\begingroup$ Upon further reading, the paper does seem to claim that $\frac{k_i k_j}{2m-1}$ is the exact edge probability in the random matching model, which is incorrect. $\endgroup$ – Misha Lavrov Jan 6 at 21:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.