We generate the test graphs according to the following parameters: the number of vertices \(n\) , the number of communities \(c\) , the average internal and external degrees \(d_{in}\)  and \(d_{out}\) . We divide the \(n\)  vertices into \(c\)  equal-sized sets then we draw each possible edge with probabilities \(p_{in}\)  or \(p_{out}\)  chosen according to \(d_{in}\)  and \(d_{out}\) . We evaluate the partition found by comparing them to the original generated partition. To achieve this, we use the Rand index corrected by Hubert and Arabie [1]}, [2]} which evaluates the similarities between two partitions. The Rand index \(I(\mathcal {P}_1,\mathcal {P}_2)\)  is the ratio of pairs of vertices correlated by the partitions \(\mathcal {P}_1\)  and \(\mathcal {P}_2\)  (two vertices are correlated by the partitions \(\mathcal {P}_1\)  and \(\mathcal {P}_2\)  if they are classified in the same community or in different communities in the two partitions). The expected value of \(I\)  for a random partition is not zero. To avoid this, Hubert and Arabie proposed a corrected index that is also more sensitive: \(I^{\prime } = \frac{I - I_{exp}}{I_{max} - I_{exp}}\)  where \(I_{exp}\)  is the expected value of \(I\)  for two random partitions with the same community size as \(\mathcal {P}_1\)  and \(\mathcal {P}_2\) .
<FIGURE>