# Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks +
## 2 Methodology
### The Proposed Hybrid Approach
To attain this objective, we derived the following conceptual insights from the notion of row generation, all borrowed from [15]: the subsequent lemma illustrates that the optimal solution remains unaffected when concentrating solely on variables \(x_{ij}\) with \(c_{ij}>0\), and the subsequent theorem establishes that the optimal solution to (IP-RMM), without constraints involving \(x_{ij}\) where \(c_{ij}\leq 0\), is equivalent to the optimal solution to (IP-RMM). Theorem 4.2: _Excluding variables \(x_{ij}\) and the corresponding constraints with \(c_{ij}\leq 0\) from the integer programming problem (IP-RMM) does not change the optimality--that is, the optimal solution of the modified problem remains the same as the one for (IP-RMM)._  
Proof: Suppose we have a binary variable \(x_{ij}\) that satisfies constraints (5)-(7). We show that if \(c_{ij}\leq 0\), then the variable \(x_{ij}\) will not contribute to maximizing the objective function (IP-RMM). Consider the term \(c_{ij}(1-x_{ij})\) in the objective function (IP-RMM). If \(c_{ij}\leq 0\), irrespective of the value of \(x_{ij}\) (0 or 1), the term \(c_{ij}(1-x_{ij})\) will be non-positive. Consequently, incorporating \(x_{ij}\) in the objective function with \(c_{ij}\leq 0\) does not play any role in maximizing the objective. Conversely, if \(c_{ij}>0\), including \(x_{ij}\) in the objective function can potentially enhance the objective value by setting \(x_{ij}\) to 0 (i.e., nodes \(i\) and \(j\) belong to the same community) since \(c_{ij}(1-0)=c_{ij}\). Therefore, it suffices to consider only the variables \(x_{ij}\) for which \(c_{ij}>0\) in the objective function (IP-RMM). In addition, constraints (5)-(7) ensure that the variables \(x_{ij}\) adhere to the triangle inequalities, maintaining consistency in community assignments. Removing constraints involving \(x_{ij}\) with \(c_{ij}\leq 0\) does not change the feasible region of the problem because these constraints do not affect the feasibility of the solution. Thus, excluding variables \(x_{ij}\) and corresponding constraints where \(c_{ij}\leq 0\) does not change the optimal solution. Taking into account the above theorem, we can simplify the original model (IP-RMM) by focusing only on the variables \(x_{ij}\), where \(c_{ij}>0\). Letting \(I_{pos}=\{(i,j)\in I_{all}\mid c_{ij}>0\}\), the revised integer programming model can be formulated as follows:  
\[\max \sum_{(i,j)\in I_{pos}}c_{ij}(1-x_{ij})\] (IPs-MM) \[x_{ij}+x_{jk}-x_{ik}\geq 0 \forall\ (i,j),(j,k),(i,k)\in I_{pos} \tag{9}\] \[x_{ij}-x_{jk}+x_{ik}\geq 0 \forall\ (i,j),(j,k),(i,k)\in I_{pos}\] (10) \[-x_{ij}+x_{jk}+x_{ik}\geq 0 \forall\ (i,j),(j,k),(i,k)\in I_{pos}\] (11) \[x_{ij}\in\{0,1\} \forall(i,j)\in I_{pos} \tag{12}\]  
An encouraging observation is that (IPs-MM) exhibits significantly fewer constraints and variables in comparison to the original (IP-RMM) model while maintaining an equivalent set of optimal solutions. Nevertheless, obtaining the optimal solution for average to large-scale networks might still pose challenges. Undoubtedly, a viable approach to expedite the branch-and-bound technique, especially when utilizing the CPLEX (CPLEX is a powerful optimization software package developed by IBM that employs advanced algorithms to solve linear, mixed-integer, and quadratic programming problems efficiently.) solver, is to provide it with a sufficiently good initial solution. Commencing with a judicious selection from the feasible solution space has proven to significantly enhance performance. In this context, we once again leverage the proposed heuristic algorithm. Specifically, we employ the communities generated by the heuristic approach as an initial solution for solving (IPs-MM). With all elements considered, Algorithm 3 frames our method for (near) optimally identifying communities. It is essential to note the integer inputs \(k_{1}\) and \(k_{2}\) of the algorithm, which control the number of iterations in the second phase of the heuristic algorithm and the number of repetitions considered for solving (IPs-MM), respectively.