3
$\begingroup$

In this period, I am studying some topics on random networks to understand the modularity optimization used in community detection. In particular, I am trying to understand a model called configuration model, which represents a random graph with a given degree sequence.

You can find some descriptions on the topic here:

http://tuvalu.santafe.edu/~aaronc/courses/5352/fall2013/csci5352_2013_L11.pdf http://homepage.cs.uiowa.edu/~sriram/196/spring12/lectureNotes/Lecture11.pdf

Now, my problem is that I don't understand why the probability $p_{ij}$ that exists at least an edge between two vertices $i$ and $j$ is evaluated as $p_{ij} = \frac{k_i k_j}{2m}$. I suppose that they are evaluating the probability as the edges were independent. Am i right? Are really the edges independent or is it supposed that they are in a large graph? I don't understand that very well because I have noticed that in some graphs the given probability is not a value between 0 and 1.

It's confusing the fact that I have read on some articles that they call it as the "expected number of edges between two vertex" and on other ones that they call it as the "probability that exists at least an edge between two vertex", too. Is it the same thing?

Could you help me understand the given probability?

Thank you.

$\endgroup$
0
$\begingroup$

There is no independence here. The model assumes that the $2m$ "edge stubs" from the vertices are matched at random: you pick a pair of unconnected stubs, connect them, and repeat until all are connected. If vertex $i$ has $k_i$ stubs and a different vertex $j$ has $k_j$ stubs, there are $k_i k_j$ pairs of stubs, one for $i$ and one for $j$. The probability that a particular pair $(stub_1, stub_2)$ are connected is $1/(2m-1)$, since any of the $2m-1$ stubs other than $stub_1$ has equal probability of ending up connected to $stub_1$. By linearity of expected value, the expected number of connections between vertices $i$ and $j$ is then $k_i k_j/(2m-1)$. If $m$ is very large, you might approximate this as $k_i k_j/(2m)$.

The probabilty that there is at least one connection is less than the expected number of connections, if it is possible to have more than one connection. Under appropriate conditions, the probability of having more than one connection will be small, in which case you can use $k_i k_j//(2m-1)$ as an approximation to the probability of at least one connection.

$\endgroup$
  • $\begingroup$ Thank you for your answer. Sorry, I don't understand some things. Are the events of adding edges in the configuration model not independent or is the independence not needed to prove that probability? I thought that independence was needed because after having added an edge, then the number of possible stubs is decreased. Also, what do we mean when you say that by linearity of expected value, you evaluate the expected number of connections? I don't understand the connection with the definition of the expected value of a random variable ($E[X]=x_1*p_1 + x_2*p2 + ... + x_k*p_k)$. Thank you. $\endgroup$ – JohnQ Mar 31 '14 at 0:35
  • $\begingroup$ Once an edge is added, those two stubs are not available any more, so the events of adding edges are not independent. Linearity means $E[aX+bY] = a E[X] + b E[Y]$ for random variables $X$ and $Y$ and constants $a$ and $b$. In particular, if $A_1, \ldots, A_n$ are events, and $I_j$ is the indicator random variable of $A_i$ (i.e. $1$ if $A_i$ occurs, $0$ if not), then the expected number of $A_i$ that occur is $$E[\sum_j I_j] = \sum_j E[I_j] = \sum_j P(A_j)$$ $\endgroup$ – Robert Israel Mar 31 '14 at 15:07
  • $\begingroup$ Ok, I had thought that edges were not independent, too. What I find confusing is: if the random graph is built pass by pass, and at every pass 2 stubs are decreased because an edge is created, why do you multiply $k_i k_j$ with $\frac{1}{2m - 1}$? Shouldn't $\frac{k_i k_j}{2m - 1}$ be the probability that an edge is created at the first pass? I know I am wrong, but I don't understand why. Thank you. $\endgroup$ – JohnQ Apr 1 '14 at 0:12
  • $\begingroup$ No, the $1/(2m-1)$ is the probability that a particular stub from $i$ and a particular stub from $j$ are joined; we don't care which pass this occurs in. This is just by symmetry: we know this stub from $i$ will be joined to one of the other $2m-1$ stubs, one of which is this stub from $j$, and the process of construction makes each of those $2m-1$ equally likely. The $k_i k_j$ is, as I said, by linearity, because there are $k_i k_j$ pairs of stubs, one from $i$ and one from $j$. $\endgroup$ – Robert Israel Apr 1 '14 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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