3
$\begingroup$

I have a undirected random graph with node degree distribution $P(k)$, I pick a random vertex $v_0$ and I randomly select a neighbor $v_1$ (the selection is made with uniform probability).

What is the probability that v1 has at least $1$ neighbor which is not a neighbor of $v_0$?

Another formulation of the question: if the expected node degree of v1 is $_1$, what is the probability that v0 and v1 share $_1 - 1$ neighbors?

Thanks

Michele

  • 1
    Your formulation seems a bit off. When you say node degree distribution $P(k)$, do you mean the degree distribution of a randomly chosen vertex? Or are you fixing a deterministic sequence of degrees? The issue is once you observe a node degree, all other nodes become conditioned on what you observe, so this question seems difficult.2012-09-15

0 Answers 0