Modularity in a graph - definition of the random component

Question

This question concerns the definition of modularity in a graph. Consider a simple, undirected, unweighted graph $G$ with vertices in set $V$ and edges in set $E$ . Between any two vertices there is at most one edge.

For a given assignment $\mathcal P : V \mapsto \{1, 2, \dots, k\}$ of the vertices of a graph $G=(V, E)$ into groups (or communities), let $f(G, \mathcal P)$ be the fraction of edges in $G$ which are within the same community, $\displaystyle f(G, \mathcal P) = \frac{|\{(v, w) \in E \| \mathcal P(v) = \mathcal P(w) \} |}{|E|} $.

Finally, the modularity of a graph $G$ and a community assignment $\mathcal P$ is defined as $\displaystyle M(G, \mathcal P) = f(G, \mathcal P) - E(G, \mathcal P)$, where $E(G, \mathcal P)$ is the expected number of edges in a graph with edges placed at random.

My questions are the following:

1. What is the process constructing the "graph with edges placed at random" ?

I think that the following is accurate:

For every edge of $G$, take its vertices and add them to a list. The resulting list will have $2 \cdot |E|$ elements (with each vertex $v$ appearing $\deg(v)$ times). Then randomly pair up these $2 \cdot |E|$ elements into $E$ pairs, and construct a graph with edges defined as these new pairs. We allow edges between a vertex and itself, as well as multiple edges between the same two vertices. This is your new graph with edges placed at random.

Is this true?

2. The modularity of a graph $G = (V, E)$ with a partition $\mathcal P$ is defined mathematically as $$\displaystyle \frac{1}{2\cdot |E|} \sum_{u,v \in V}\left(e(u, v) - \frac{\deg(u)\cdot \deg(v)}{2\cdot|E|} \right) \cdot \delta(\mathcal P(u), \mathcal P(v)) ,$$ where $e(u, v)$ is the number of edges between $u, v$ and $\delta(x, y) =1$ if $ x=y$, and $0$ otherwise.

However, following the definition of modularity from above, we obtain actually $\displaystyle \frac{1}{2\cdot |E|} \sum_{u,v \in V}\left(e(u, v) - \frac{\deg(u)\cdot \deg(v)}{2\cdot|E| - 1} \right) \cdot \delta(\mathcal P(u), \mathcal P(v)) $.

The reasoning is simple :

Modularity = $\displaystyle \frac{1}{2\cdot |E|} \sum_{u,v \in V}\left(e(u, v) - \mathbb E[e(u,v) ] \right) \cdot \delta(\mathcal P(u), \mathcal P(v)) $, where $\mathbb E[e(u,v) ]$ is the expected value of $e(u, v)$ is a random graph constructed from $G$. And we can show that according to the definition of a "random graph" from above, $\displaystyle \mathbb E[e(u,v) ] = \frac{\deg(u)\cdot \deg(v)}{2\cdot |E|-1}$.

Could you please let me know if my interpretation of the random graph constructed from $G$ is correct, and if my formula for modularity under this definition is correct?

Thank you!

References:

[1] Newman, 2006 http://www.pnas.org/content/103/23/8577.full.pdf

Answer 1

I realize this is a very old question, but you are correct in saying the actual probability of vertices u and v being connected is $$\frac{deg(u) * deg(v)}{2m - 1}$$ For large m, however, $2m - 1 \approx 2m$. Such reasoning can be found here.