m since I thought Ki/2m * Kj/2m * 2v was the last result. Thanks!
On Wed, Feb 13, 2013 at 1:46 PM, Tamás Nepusz
<address@hidden> wrote:
> Thank you for explaining this for me. But I am still confused about why multiply
> m at last using Ki/2m * Kj/2m * 2.
Because the graph is undirected, so an edge generated from vertex i to vertex j (which has probability Ki/2m * Kj/2m) is equivalent to an edge generated from vertex j to vertex i (which also has probability Ki/2m * Kj/2m). Therefore, the probability of generating an edge between vertex i and vertex j is Ki/2m*Kj/2m + Kj/2m*Ki/2m, which is Ki/2m * Kj/2m * 2 in the end.