Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thanks

Michele

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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.