2
$\begingroup$

I am trying to implement the Louvain algorithm in PySpark.

An important part of the algorithm involves calculating the modularity gain of taking node $i$ out of its current community $C_0$ and placing it in a neighboring community $C_1$.

On page four of the original paper, the authors describe the modularity gain as a two-step process:

  1. Calculating the modularity gain of removing $i$ from its current community; and
  2. Calculating the modularity gain of placing isolated node $i$ to the new community.

The second step is described in equation 2 (page 4), but the first step is only addressed as:

A similar expression is used in order to evaluate the change of modularity when i is removed from its community.

I have been unable to find the expression for the first step.

Does anyone know how to compute the modularity gain of removing node $i$ from its current community? Could you please share where you found it?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

I contacted the author (Renaud Lambiotte) and he shared the answer with me.

The change in modularity of removing node $x$ from its community $C_x$ is: $$\triangle Q_{remove} = - \frac{1}{m} \sum_{i \in C_x \setminus \{x\}} \Big[ A_{ix} - \frac{k_i k_x}{2m} \Big] $$

The change in modularity of inserting node $x$, which is now alone in its community, into $C_1$ is:

$$ \triangle Q_{insert} = \frac{1}{m} \sum_{i \in C_1} \big[ A_{ix} - \frac{k_i k_x}{2m} \Big]$$

Where $A_{ix}$ is the weight of the edge between vertices $i$ and $x$, $m = \sum_{i,j} A_{ij}$, and $k_i$ and $k_x$ are the degrees of vertices $i$ and $x$ respectively.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.