Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 $<k>_1$, what is the probability that v0 and v1 share $<k>_1 - 1$ neighbors?



share|cite|improve this question
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. – Alex R. Sep 15 '12 at 16:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.