Optimal partition

The optimal partition for the simple graph we are using in this section is similar to the one obtained with connected components or Label Propagation algorithms: nodes A, B, and C are in their own partition while nodes D to G are in another community.

With m = 9, the modularity in that case is as follows:

Q = 1/18 (
    2  * (A_AB - k_Ak_B / 18 + A_AC - k_Ak_C / 18 + A_BC - k_Bk_C / 18)
   + 2 * (A_DE - k_Dk_E / 18 + A_DG - k_Dk_G / 18 + A_DF - k_Dk_F / 18 + A_EF - k_Ek_F / 18 + A_EG - k_Ek_G / 18 + A_GF - k_Gk_F / 18 )
) + Q_diag
= 1 / 18 * 2 * (
   1 - 2 * 2 / 18 + 1 - 2 * 3 / 18 + 1 - 2 * 3 / 18
   + 1 - 3 * 3  / 18 + 1 - 3 * 3  / 18 + 0 - 3 * 2 / 18 + 1 - 3 * 2 / 18 + 1 - 3 * 3 / 18 + 1 - 3 * 2 / 18
    ) - 0.148   
= 0.364 > 0

Since our graph is undirected, we can afford to double the term corresponding to the relationship between A and B (A - B), instead of summing the terms A -> B  and B ...