# Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks +
## 3 Evaluation of Accuracy
### Experiments
The selection of \(k_{1}\) underscores the algorithm's ability to bypass unnecessary iterations in the community revision step to sufficiently improve the complementary graph. Meanwhile, the small choice of \(k_{2}\) demonstrates the algorithm's rapid convergence toward the optimal solution by satisfying all the constraints of (IPs-MM). In contrast, as the level of noise within the network's structure increases, notably with an elevated value of \(\mu\), especially for \(\mu=0.9\), all competing algorithms encounter difficulties in capturing the optimal community structure. Intriguingly, the proposed method also faces challenges in this scenario when \(k_{1}\) and \(k_{2}\) are not sufficiently large--specifically, for the black curve, wherein \(k_{1}=k_{2}=3\), the proposed algorithm exhibits a complete degradation against other techniques. From a time complexity perspective, as illustrated in Figure 3, our algorithm operates significantly faster compared to other methods. In previous research [15], it was demonstrated that our baseline model (depicted by the black curve in Figure 3) holds an advantage over all competing algorithms except for the one introduced in [16]. The latter solves the LP relaxation version of the model and employs a rounding algorithm to determine the integer solution and, consequently, the community structures (red curve in Figure 3). Notably, our \begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c} \hline \hline  & & & & & & & & & & & & & & & & \\ \cline{2-13}
**Parameter** & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** & **9** & **10** & **11** & **12** & **13** & **14** & **15** \\ \hline \(k_{1}\) & 0 & 0 & 0 & 2 & 2 & 2 & 2 & 3 & 4 & 4 & 4 & 4 & 5 & 5 & 5 \\ \(k_{2}\) & 2 & 2 & 3 & 3 & 3 & 3 & 5 & 6 & 8 & 8 & 11 & 15 & 18 & 25 & 29 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Used values for the algorithm’s input parameters \(k_{1}\) and \(k_{2}\) associated with each of the real-world networks depicted in Table 2.  
augmented method (the blue curve) not only surpasses the baseline model but also closely approaches a fast heuristic but not very accurate approach presented in [16]. We state that, as expected, not only does our proposed augmented method outperform our baseline approach [15] in terms of time complexity (as depicted in Figure 3), it also yields higher quality communities that closely align with the ground truths (as depicted in Figures 1 and 2). This is achieved through a heuristic design for enhancing the Max-Min Modularity complementary graph and expediting solving the sparse yet equivalent integer counterpart we introduced for the problem. As a final note regarding the selection of parameters, as networks increase in size, a smaller value for \(k_{1}\) becomes more reasonable. This is attributed primarily to the high quality of the initial communities obtained in the first phase of the heuristic method and, secondly, to the time efficiency of this phase, as elucidated in Section 2.1. As for \(k_{2}\), although the sparse model (IPs-MM) expedites the solving process, opting for a larger value may not be necessary, especially when dealing with massive graphs. This is particularly evident and plausible given the typically swift  
Figure 3: Execution time associated with each algorithm (from top, [16], our approach, [15], [16], and optimally solving (IP-RMM)) applied to the real-world networks presented in Table 2.  
Figure 2: Comparison between NMI ranks of different algorithms consisting of our method for four different parameter settings and also optimally solving a sparse integer model of M-M Modularity [15] and LP of Max-Min Modularity with local search rounding [16], all applying to the LFR synthetic graphs, generated by considering four different mixing parameters \(\mu\). convergence of the model, wherein all constraints are satisfied by an optimal solution obtained in the early iterations.