3
$\begingroup$

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?

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.