2
$\begingroup$

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?

$\endgroup$
8
  • 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$ Oct 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$
    – zhoraster
    Oct 19, 2010 at 18:53
  • $\begingroup$ Pardon. Now I see: $7 \choose 3=35$. Still I can't understand fully why it works. $\endgroup$
    – zhoraster
    Oct 19, 2010 at 19:04
  • $\begingroup$ ${7\choose 3}=35$ $\endgroup$
    – zhoraster
    Oct 19, 2010 at 19:04
  • 2
    $\begingroup$ I think the question assumes that the degrees are associated with the vertices. $\endgroup$ Oct 19, 2010 at 19:31

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\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 Anh
    Oct 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$
    – Fiktor
    Oct 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 Anh
    Oct 22, 2010 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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