# Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks +
## 3 Evaluation of Accuracy  
In this section, we delve into verifying the efficiency of our algorithm throughout various experiments. Due to our method having been built upon the heuristic and the exact method introduced in [15; 21], we came to, first of all, compare outcomes with the one determined by those two approaches.  
It is worth noting that [21] succeeded in surpassing various state-of-the-art heuristic community detection algorithms, like Distributed Louvain (DLouvain) [35], Variable Neighborhood Search (VNS) [36], Simulated Annealing (SA) [37], and FastGreedy [13] algorithms, both in terms of execution time and communities quality. In addition, Ref. [15] managed to detect communities superior to the ones obtained by [9; 16], where in the former, the optimal solution to the linear relaxation model of ordinary Max-Min Modularity was fed into a local search manner rounding procedure for obtaining the communities. In the latter, communities were discovered by using the user-defined complementary graph introduced in [9] and also applying its proposed hierarchical heuristic algorithm for maximizing the Max-Min Modularity.  
With this in mind, if our algorithm can outperform all the above approaches, it would substantiate its efficiency. For this reason, we take all the network benchmarks used in [15; 21] and compare the results of all algorithms with each other. Furthermore, we also generate and use six _Lancichinetti Fortunato Radicchi_ (LFR) artificial benchmarks [38], which closely resemble real-world complex networks by incorporating a pre-defined community structure. Generating these artificial graphs, which will be explained later, is based on the user-defined parameters fully elucidated in [38]. What makes the comparison fair is that all the under-study graphs, including the real-world networks presented in Table 2 and the artificial ones, are among the recognized and commonly utilized networks in this context. More importantly, each possesses the corresponding ground truth, representing the optimal community structures. This allows us to evaluate the effectiveness of a community detection algorithm by measuring the similarities between the algorithmically derived communities and the optimal structures. For this evaluation, we employ the widely acknowledged performance metric, _Normalized Mutual Information_ (NMI), which we explain in Section 3.1.  
Subsequently, we focus exclusively on the proposed algorithm, delving into the role of its input parameters, namely, \(k_{1}\) and \(k_{2}\), delineated in Algorithm 3, in improving community establishments.  
It is worth mentioning that all the experiments are conducted on a computer system with an Intel(R) Core i9-12900 KF processor @ 3.2 GHz, 16.6 Core(s) and 128 GB of RAM. Algorithms are implemented with C++, and CPLEX optimizer 12.9 is used for solving linear programming.  
\begin{table}
\begin{tabular}{l c c} \hline \hline
**ID** & **Network** & \(n\) & \(m\) \\ \hline
1 & [PERSON]’s karate club [39] & 34 & 78 \\
2 & Mexican Politicians [40] & 35 & 117 \\
3 & Dolphin network [41] & 62 & 159 \\
4 & Les Miserables [41] & 77 & 254 \\
5 & p53 protein [42] & 104 & 226 \\
6 & Books about U.S. politics [43] & 105 & 441 \\
7 & American college football [8] & 115 & 613 \\
8 & Citation graph drawing [44] & 311 & 640 \\
9 & USAir97 [45] & 332 & 2126 \\
10 & C. Elegans [46] & 453 & 2025 \\
11 & Erdos collaboration [47] & 472 & 1314 \\
12 & Electronic circuit [48] & 512 & 819 \\
13 & Email-Eu-core [49] & 986 & 16,064 \\
14 & Amazon network [50; 51] & 334,863 & 925,872 \\
15 & LiveJournal social network [51; 52] & 3,997,962 & 34,681,189 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Networks under-study.