# Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks +
###### Abstract
\begin{table}
\begin{tabular}{c c c} \hline \hline  & **Function** & **Definition** \\ \hline \multirow{4}{*}{IC} & Internal density [23] & \(\frac{|E_{\text{C}}^{in}|}{|\text{C}||(|\text{C}|-1)/2}\) \\ \cline{2-3}  & Edge inside [23] & \(|E_{\text{C}}^{in}|\) \\ \cline{2-3}  & Average degree [23] & \(\frac{2|E_{\text{C}}^{in}|}{|\text{C}|}\) \\ \hline \multirow{4}{*}{EC} & Expansion [23] & \(|E_{\text{C}}^{out}|\) \\ \cline{2-3}  & Cut Ratio [24] & \(\frac{|E_{\text{C}}^{out}|}{|\text{C}||(|\text{C}|-|\text{C}|)}\) \\ \hline \multirow{4}{*}{MIE} & Conductance [25] & \(\frac{|E_{\text{C}}^{out}|}{2|E_{\text{C}}^{out}|+|E_{\text{C}}^{out}|}\) \\ \cline{2-3}  & Normalized Cut [25] & \(\frac{|E_{\text{C}}^{out}|}{2|E_{\text{C}}^{out}|+|E_{\text{C}}^{out}|}+\frac{ |E_{\text{C}}^{out}|}{2|(|E_{\text{C}}^{out}|+|E_{\text{C}}^{out}|)}+\frac{|E_{ \text{C}}^{out}|}{2|(|E_{\text{C}}^{out}|+|E_{\text{C}}^{out}|)}\) \\ \cline{2-3}  & Out-Degree Fraction [26] & \(\max\limits_{i\in\text{C}}\frac{|(i,j)\in E:j\
ot\in\text{C}|}{deg(i)}\) \\ \cline{2-3}  & Flake-ODF [26] & \(\frac{|i\in\text{C}|(i,j)\in E:j\in\text{C}|<deg(1)/2}{|\text{C}|}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Several connectivity-based quality functions for measuring the quality of a community \(C\). \(|E_{\text{C}}^{out}|\), \(|E_{\text{C}}^{in}|\), \(|C|\), and \(deg(i)\), respectively, represent the number of external connections of \(C\), number of internal connections of \(C\), the number of vertices belonging to \(C\), and the degree of node \(i\). consisting of edges between unrelated nodes. This adjustment penalizes the Modularity measure when unrelated nodes coexist within a community. This is while, despite its improved accuracy, current Max-Min Modularity approaches--like the one presented by [PERSON] et al. [9]--depend on user-defined relation criteria that introduce potential faultiness into the community detection process. The naive dependency on an oracle for determining the complementary graph, as well as the not-very-successful heuristic hierarchy algorithm used in [9] for maximizing the Max-Min Modularity measure, directed [PERSON] et al. in [15; 16] to provide a more structured way to address the deficiencies. Their focus was on methodically structuring an effective complementary graph that accurately reflects the absence of connections between nodes. They enhanced this graph by applying the optimal solution to the _linear relaxation_ formulation of the Modularity maximization problem. Using this systematically obtained complementary graph, they devised an _integer programming_ representation for the Max-Min Modularity maximization problem and solved it using various methods. In [16], they applied the rational solution of the model's linear relaxation version to a local search rounding technique to obtain integer solutions and identified communities. In contrast, [PERSON]. [15] theoretically developed and solved an equivalent yet sparse integer model, determining the exact solution to the problem. Consequently, whereas [16] succeeded in deriving community structure in a prompt manner due to the heuristic fashion employed, Ref. [15] achieved more precise results by obtaining optimal solutions to the integer model. Both approaches yielded promising results, particularly those presented in [15], as they optimally solve a corresponding integer model. Nevertheless, several potential downsides exist. A primary drawback, not exclusive to these two schemes, is that almost all community detection methodologies take only one quality function into consideration. As a matter of fact, regardless of the optimization technique, each quality function tends to emphasize some distinct aspects of the network's structure. For instance, as mentioned, whereas a connectivity-based measure is geared more toward determining communities with densely connected nodes, topological approaches are capable of also concentrating on grouping related nodes.