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?
-
2$\begingroup$ 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? $\endgroup$– Andrew D. KingOct 19, 2010 at 14:55
-
$\begingroup$ @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). $\endgroup$– zhorasterOct 19, 2010 at 18:53
-
$\begingroup$ Pardon. Now I see: $7 \choose 3=35$. Still I can't understand fully why it works. $\endgroup$– zhorasterOct 19, 2010 at 19:04
-
$\begingroup$ ${7\choose 3}=35$ $\endgroup$– zhorasterOct 19, 2010 at 19:04
-
2$\begingroup$ I think the question assumes that the degrees are associated with the vertices. $\endgroup$– Ori Gurel-GurevichOct 19, 2010 at 19:31
1 Answer
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.
-
$\begingroup$ 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 $\endgroup$– Tuan AnhOct 21, 2010 at 5:43
-
$\begingroup$ 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. $\endgroup$– FiktorOct 21, 2010 at 20:54
-
$\begingroup$ 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. $\endgroup$– Tuan AnhOct 22, 2010 at 0:12