# Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks +
## 2 Methodology
### The Proposed Hybrid Approach  
In this section, we bring forward a successful approach for obtaining accurate communities by optimally optimizing a revised version of the well-known topological community quality metric, _Max-Min Modularity_. What we intend to do is use the already introduced heuristic method to propose a new complementary graph (Definition 5) and then apply our theoretical findings in [15] to derive a sparse integer model for the revised Max-Min Modularity, which we then try to solve optimally using the branch-and-bound technique. **Definition 5** (Complementary graph \(G^{\prime}\)). : _Let \(G=(V,E)\) be a given network with a corresponding set of communities \(\mathbf{C}=\{C_{1},\ldots,C_{l}\}\) identified by the heuristic algorithm. We associate with \(G=(V,E)\) a complementary graph \(G^{\prime}=(V,E^{\prime})\) such that \((i,j)\in E^{\prime}\) if and only if \((i,j)\
ot\in E\wedge\{i,j\}\
ot\in C_{r},r=1,2,\ldots,l\)._  
In essence, two disconnected nodes \(i\) and \(j\) in \(G\) establish an edge in the complementary graph \(G^{\prime}\), provided that \(i\) and \(j\) do not belong to a same community specified by the heuristic algorithm introduced in Section 2.1. It is crucial to emphasize the advantages of incorporating this complementary graph into the Max-Min Modularity metric. Firstly, the high-quality communities already obtained by the heuristic algorithm validate the absence of connections between nodes belonging to different communities. Secondly, this approach allows the simultaneous consideration of two quality metrics. While maximizing the topology-based metric, Modularity, over the main network has been proven in the literature to yield highly accurate communities, minimizing it over a graph consisting of unrelated nodes identified by a connectivity-based metric can significantly enhance the results. Additionally, in terms of time complexity, our theoretical findings regarding the heuristic method, coupled with the ability to confidently adjust the number of iterations in the revision phase of the algorithm or even omit it due to the favorable quality of the initial phase, enable us to achieve results in a shorter timeframe. Having \(G^{\prime}\) defined, we now provide the integer formulation of our _Revised Max-Min Modularity maximization problem_ (IP-RMM):  
\[\max \sum_{(i,j)\in L_{all}}c_{ij}(1-x_{ij})\] (IP-RMM) \[x_{ij}+x_{jk}-x_{ik}\geq 0 \forall\ (i,j),(j,k),(i,k)\in L_{all} \tag{5}\] \[x_{ij}-x_{jk}+x_{ik}\geq 0 \forall\ (i,j),(j,k),(i,k)\in L_{all}\] (6) \[-x_{ij}+x_{jk}+x_{ik}\geq 0 \forall\ (i,j),(j,k),(i,k)\in L_{all}\] (7) \[x_{ij}\in\{0,1\} \forall(i,j)\in L_{all} \tag{8}\]  
where the binary variable \(x_{ij}\) indicates if nodes \(i\) and \(j\) belong to the same community (\(=0\)) or not (\(=1\)). Moreover, \(I_{all}=\{(i,j)\in V^{2}\mid i<j\}\), \(c_{ij}=\frac{q_{ij}}{m}-\frac{q_{ij}^{\prime}}{m^{\prime}}\) with \(q_{ij}=a_{ij}-\frac{d_{i}d_{j}}{2m}\), \(q_{ij}^{\prime}=a_{ij}^{\prime}-\frac{d_{i}^{\prime}d_{j}^{\prime}}{2m^{\prime}}\), \(d_{i}^{\prime}=\sum_{l=1}^{n}a_{il}^{\prime}\), and \(m^{\prime}=\sum_{(i,j)\in L_{all}}a_{ij}^{\prime}\) for each \((i,j)\in L_{all}\). Constraints (5)-(7) satisfy the triangle inequalities and guarantee that \(i\) and \(j\) are in the same community and \(j\) and \(k\) are in the same community, then so are \(i\) and \(k\). The primary consideration is that solving (IP-RMM) falls into the category of _NP-hard_ problems, presenting a challenge for optimal resolution. Consequently, we embarked on an investigation to explore the possibility of simplifying (IP-RMM) while preserving the same set of optimal solutions.