# Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks +
## 2 Methodology
### The Proposed Hybrid Approach
The latter parameter is intertwined with the number of the model's constraints involved in the optimization. Note that due to the NP-hard nature of (IPs-MM), a row generation technique is employed. This technique initially solves the problem without considering any constraints and then iteratively adds those that are not satisfied by the obtained solution. Whereas assuming \(k_{2}=\infty\) lets the algorithm terminate whenever it finds the optimal solution, this could prolong execution times for huge networks. To address this, we came to introduce a bounding mechanism, limiting the number of times the algorithm is allowed to add violated constraints. While this bounding introduces some inaccuracy, due to the smart choice of the initial solution, we do not end far from the optimal solution. Furthermore, the promising initial solution reduces the likelihood of encountering cases where the algorithm would reach the optimal solution with all constraints satisfied after \(k_{2}\) iterations. ```
Input: Graph \(G\) and integers \(k_{1}\) and \(k_{2}\). Output: Set of communities \(\mathbf{C}\). 1\(\mathbf{C}\gets\)\(\mathit{lUC}(G,CIS(G),k_{1})\); // Heuristic approach (Algorithms 1 and 2)
2 Iteration \(\leftarrow\) 1;
3 Formulate (IPs-MM) without any constraints;
4 whiletruedo
5 Solve (IPs-MM) using the branch-and-bound method to obtain the optimal solution \(x^{*}\);
6 ifallconstraints of (IPs-MM) are satisfied by \(x^{*}\vee\)(Iteration \(>k_{2}\))then
7 Break;
8
9 else
10 Add the violated constraints to the model;
11 Iteration++;
12
13 Return the set of community \(\mathbf{C}\) associated with the solution \(x^{*}\);
```  
**Algorithm 3** The proposed algorithm for community discovery  
As a complement to the above discussion, one might point out that whereas the golden standard for determining optimal communities is to let both \(k_{1}\) and \(k_{2}\) be sufficiently large, it does not sound logical, especially when dealing with large networks. What is important to note here is the advantage one can take from the trade-off between these two parameters. More specifically, despite the promising quality of the initial communities, the greater the number of \(k_{1}\), the better the communities become, which leads to less concern regarding the optimality of the (IPs-MM). In contrast, the fewer reforms performed due to the small value of \(k_{1}\) seem to require more care with finalizing the communities, which highlights the importance of achieving an optimal solution to (IPs-MM) with as many satisfied constraints as possible, which itself depends on picking a large value of \(k_{2}\). To summarize, one can conclude that picking a large value of \(k_{1}\) can relax a large choice of \(k_{2}\) and vice versa. On the other hand, as already observed in [21], \(k_{1}\) does not need to be large due to the already high-quality initial communities obtained by the first phase of the heuristic algorithm, which has turned out to be efficient also in terms of time execution. This provides us with a final useful hint: choosing generally a relatively small value of \(k_{1}\), especially in the case of dealing with large networks, and presuming \(k_{2}\) to be large enough to make a safe margin about having the majority of constraints of (IPs-MM) satisfied, could lead us to obtain (near) optimal community structures. The experiments in the next section validate this assertion.