# Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks +
## 2 Methodology
### Toward Exactness  
Inevitably, the primary objective of any community detection algorithm is to identify communities as accurately as possible within a reasonable timeframe. For the former, it seems necessary to shift the focus from heuristic methods to exact optimization techniques, even though it would fight against the time complexity. On the other hand, utilizing a mix of quality metrics could also lead to accuracy improvement, as each quality metric can be tailored to suit specific graph structures within a defined range. Accordingly, in this section, to enhance the quality of communities, we first concentrate on _Max-Min Modularity_, which is recognized as one of the most applicable topology-based metrics. Using this metric, we then express the Max-Min Modularity maximization as a mathematical programming problem. Solving this formulation allows us to optimize the measure and, consequently, detect highly accurate communities. For this, let us briefly explain the foundational principles of Modularity. This framework serves as the basis for the introduction of various Max-Min Modularity variants, which we will also discuss subsequently. _Modularity_, as introduced by [PERSON] (2007), is widely acknowledged as a measure in network analysis. For a network \(G\) with \(n\) vertices and \(m\) edges, the Modularity value (\(Q\)) of a given partitioning \(\mathbf{C}\) is mathematically expressed as follows:  
\[Q(\mathbf{C})=\frac{1}{2m}\sum_{i,j\in V}[a_{ij}-\frac{d_{i}d_{j}}{2m}]\sigma( i,j). \tag{3}\]  
Here, \(A=(a_{ij})\) is the adjacency matrix of \(G\), where \(a_{ij}\) is set to one if an edge exists between node \(i\) and node \(j\), and zero otherwise. \(d_{i}\) represents the degree of node \(i\), defined as the sum of all entries in the \(i\)-th row of the adjacency matrix. Additionally, \(\sigma(i,j)\) is one if nodes \(i\) and \(j\) are in the same community and zero otherwise. In simpler terms, Modularity quantifies the number of edges within a community minus the expected number of such edges. Communities with higher Modularity values are considered to be of better quality. Therefore, maximizing Modularity aids in identifying high-quality communities within a network. However, despite the widespread use of Modularity, it has known limitations (refer to ([PERSON] and [PERSON], 2016; [PERSON] and [PERSON], 2016) for details). Notably, Modularity only accounts for existing edges in the network, evaluating the goodness of a community solely based on its fit with observed edges. It overlooks disconnected nodes (absent edges) within the same community, which is a drawback since node disconnection does not necessarily imply an absence of underlying relations between them. To address this limitation, an extension of Modularity called _Max-Min Modularity_([PERSON] and [PERSON], 2016) has been developed, aiming to enhance accuracy by penalizing Modularity when disconnected nodes are present in the same community. The core concept behind Max-Min Modularity involves maximizing the Modularity value within the given network \(G\) while simultaneously minimizing this value across a complementary graph \(G^{\prime}\). The latter has an identical set of nodes as \(G\), and the presence of an edge between nodes \(i\) and \(j\) in \(G^{\prime}\) indicates that, firstly, \(i\) and \(j\) are not connected in \(G\), and secondly, these nodes are relatively unrelated. The rationale behind Max-Min Modularity is quite intuitive: by refining communities to reduce the occurrence of unrelated nodes, nodes not only disconnected but also unrelated within the same communities, the quality of the partitioning is significantly enhanced.