Re: [igraph] Definition of Modularity

[Tamas Nepusz]

> 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.