Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let G be a graph which is randomly generated from degree sequence D = (d1, d2, .., dn) and x, y are vertices in G. How to compute the probability that (x, y) is an edge of G?

share|improve this question
2  
Consider this question: If you choose $x$ and $y$ before determining the degree of each vertex, how is that different from choosing the graph first and then choosing $x$ and $y$ at random? –  Andrew D. King Oct 19 '10 at 14:55
    
@Andrew D. King: The approach is good, but very deceptive (or maybe I'm messed somewhere). I take it as you pretend $\frac1{n(n-1)}\sum_{k=1}^n d_n$ to be an answer. But consider this: $D=(2,2,2,2,2,2,2)$. There are two such non-isomorphic graphs: 7-cycle and 4-cycle+triangle. On 7 vertices, there are $6!/2=360$ graphs of the first type and ${7 \choose 3}\times 3 = 84$ of the second. Now $(x,y)$ is an edge in $5!=120$ 7-cycles and in $20+5\times 3=35$ of the 2nd type. So the probability is $155/444\neq 7/21$ (again, correct me if I miscounted). –  zhoraster Oct 19 '10 at 18:53
    
Pardon. Now I see: $7 \choose 3=35$. Still I can't understand fully why it works. –  zhoraster Oct 19 '10 at 19:04
    
${7\choose 3}=35$ –  zhoraster Oct 19 '10 at 19:04
2  
I think the question assumes that the degrees are associated with the vertices. –  Ori Gurel-Gurevich Oct 19 '10 at 19:31

1 Answer 1

I want to show, that your problem can be solved by solving $O(n)$ times more common problem:

Problem 2: What is the number of graphs with degrees $(d_1,\dots,d_n)$?

Let's denote this number by $f(d_1,\dots,d_n)$. It's generating function is equal to $$F=F(z_1,\dots,z_n)=\prod_{i< j}(1+z_iz_j)\tag{1}$$ (assuming that multiple edges and cycle-edges are not allowed). For simplicity I'll assume, that $x$ is a first vertex (with degree $d_1$) and $y$ is the second and $d_1\leq d_2$. Probability, you are interested in, is equal to $$p=1-g(d_1,\dots,d_n)/f(d_1,\dots,d_n)\tag{2},$$ where $g(d_1,\dots,d_n)$ is equal to number of graphs with degrees $(d_1,\dots,d_n)$ which does not contain edge $\{1,2\}$. It's generating function is equal to $$G=G(z_1,\dots,z_n)=\prod_{i< j;\{i,j\}\neq\{1,2\}}(1+z_iz_j),\tag{3}$$ so we have $$F=(1+z_1z_2)G.\tag{4}$$ Therefore $$f(d_1,d_2,d_3,\dots,d_n)=g(d_1,d_2,d_3,\dots,d_n)+g(d_1-1,d_2-1,d_3,\dots,d_n)\tag{5}$$ and $$g(d_1,\dots,d_n)=\sum_{k=0}^{d_1} (-1)^k f(d_1-k,d_2-k,d_3,\dots,d_n).\tag{6}$$ From (2) and (6) we see, that solving problem 2 ($d_1+1$ times) is enough for calculating desired probability.

Of course problem 2 can be solved in time $c(n(n-1)/2)(d_1+1)(d_2+1)\dots (d_n+1)$, but I think you can try to find a better solution. Problem 2 might be a known graph enumeration problem. Probably you already know about this book, but if you don't, take a look.

share|improve this answer
    
Thanks Fiktor. However, in the paper named Analysis of weighted networks, Newman claimed that probability equals to $(d_i\times d_j)/\sum_k d_k$, but I do not understand why –  Tuan Anh Oct 21 '10 at 5:43
    
Assume the graph with 102 vertices with $d_i=101$, $d_j=101$ and $d_k=2$ for $k\neq i$, $k\neq j$. Then the "probability", written in your comment is equal to $10201/402$ (greater than 1). However it is equal to 1, because there is only one graph with a degree sequence, described above. –  Fiktor Oct 21 '10 at 20:54
    
Thanks Fiktor. I asked prof. Newman and he answered that's only a approximation of desired probability. Here are some more information about this model and other similar models benjamingood.wordpress.com/2010/01/18/… Now I know that a nice explicit formula to compute this probability does not exist. One more time, thank you for your help. –  Tuan Anh Oct 22 '10 at 0:12

Your Answer

 
discard

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

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