Hi Tamas, Thank you for explaining this for me. But I am still confused about why multiply
m at last using Ki/2m * Kj/2m * 2. Since I do not know much about random graph theory, could you provide me more information in detail on that? Thanks! Isaiah On Wed, Feb 13, 2013 at 7:28 AM, Tamas Nepusz <[email protected]> wrote: > > So my question is that why Ki*Kj/2m is "the probability of an edge > existing > > between vertices i and j if connections > > > > are made at random but respecting vertex degrees". > In the Molloy-Reed model (i.e. a random graph generation model that > "respects the vertex degrees"), edges are drawn as follows. Vertex i > initially has Ki "stubs". Edges are drawn by selecting two stubs from all > the stubs of all the vertices randomly and then connecting them. The total > number of stubs is of course 2m because we are going to have m edges in the > end and each edge connects two stubs. Now, since vertex i has Ki stubs, the > probability of selecting the first stub from vertex i is Ki/2m, and the > probability of selecting the second stub from vertex j is Kj/2m. Thus, the > probability of drawing an edge between vertex i and vertex j in a single > step of the graph generation process is Ki/2m * Kj/2m. However, since we > are > actually drawing m edges, and edges between i and j are the same as edges > between j and i, the probability of drawing an edge between vertex i to > vertex j is Ki/2m * Kj/2m * 2m, so we get Ki*Kj / 2m. > > -- > T. > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help >
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
