# Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks +
## 3 Evaluation of Accuracy
### Experiments  
In our initial series of experiments, our objective is to assess the proposed algorithm in comparison to those presented in [15; 21] using the 15 real-world networks. Figure 1 portrays the computed NMI values for each methodology. To offer a more comprehensive perspective on the advancements introduced by each algorithm, the results from the competitive algorithms utilized in [15; 21] are also depicted in the figure. While the superiority of our proposed algorithm against all other methodologies across various real-world benchmarks is evident, it is crucial to highlight the relatively small values of the parameters \(k_{1}\) and \(k_{2}\) required to achieve these results. Table 3 outlines the used parameter values. Whereas the selection of \(k_{1}\) can be made relatively freely, often contingent on the network size, the utilized values of \(k_{2}\) here represent the minimum number of iterations required to solve the corresponding (IPs-MM) with all constraints satisfied. Figure 1: Comparison between NMI values achieved by our approach, the blue curve, and optimally solving an sparse integer model of M-M Mod. [15], and other understudy algorithms (from the top, second curve to bottom: [15; 16; 55; 9; 35; 56], and [13], using real-world networks presented in Table 2.  
The small values of these parameters affirm, firstly, the existence of high-quality initial communities that necessitate minimal restructuring. Secondly, they substantiate the claim that all constraints of (IPs-MM) are swiftly satisfied in the optimal solution to the model, particularly within the initial iterations of the applied row generation technique. This revelation not only bodes well for achieving refined communities but also ensures a reasonable timeframe for the algorithm. Bring to mind that our baseline methods [15; 16] exhibit limitations in producing results within a reasonable timeframe, particularly when applied to relatively large networks. Specifically, the former experiences complete failure when confronted with networks 13, 14, and 15, while the latter collapses when applied to networks 14 and 15 within a reasonable timeframe. By the same token, this breakthrough can be extrapolated to artificial networks. As mentioned, the generation process of the artificial graphs we take into account relies on what was introduced in [38]. These networks adhere to power-law distributions for both the degree and community size, with user-defined exponents \(\gamma\) and \(\beta\), respectively. Additionally, the mixing parameter \(\mu\) dictates that each vertex in the graph should share a fraction of \(1-\mu\) of its links with other nodes in its community and a fraction of \(\mu\) with other nodes in the network. The parameter \(\mu\) effectively controls the noise, with higher values leading to less-distinct community structures. Thus, a higher \(\mu\) poses challenges for community detection algorithms in identifying optimal communities [31]. In this study, we utilize four different LFR graphs with distinct mixing parameters \(\mu\) (\(\mu=0.1,0.3,0.6\), and \(0.9\)), each comprising 1000 nodes and 5 communities. All other parameters are set to default values, as detailed in [38]. We employ these benchmarks for a dual purpose: to assess the precision of our algorithms in comparison to other competing methods and to investigate the impact of the algorithm's input parameters, namely, \(k_{1}\) and \(k_{2}\). Figure 2 illustrates the resultant NMI values corresponding to each scenario. As can be discerned, in scenarios \(\mu=0.1\) and \(\mu=0.3\), which indicate less-intricate community interconnections in the synthesized networks, all algorithms more or less effortlessly detected structures closely aligned with the ground truths. Particularly noteworthy is the superior performance of the proposed approach, even with relatively small values of \(k_{1}\) and \(k_{2}\) (depicted by the blue curve).