# Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks +
###### Abstract  
This paper presents an approach to community detection in complex networks by simultaneously incorporating a connectivity-based metric and Max-Min Modularity. By leveraging the connectivity-based metric and employing a heuristic algorithm, we develop a novel complementary graph for the Max-Min Modularity that enhances its effectiveness. We formulate community detection as an integer programming problem of an equivalent yet more compact counterpart model of the revised Max-Min Modularity maximization problem. Using a row generation technique alongside the heuristic approach, we then provide a hybrid procedure for near-optimally solving the model and discovering high-quality communities. Through a series of experiments, we demonstrate the success of our algorithm, showcasing its efficiency in detecting communities, particularly in extensive networks. ommunity detection; graph partitioning; complex network analysis; mathematical programming; approximation algorithm +
Footnote †: This paper is an extended version of our paper published in the proceedings of the 18 th Conference on Computer Science and Intelligence Systems (FedCSIS), Warsaw, Poland, 17-20 September 2023.  
to as a _quality function_, to assess the excellence of communities; then, the devising of an optimization algorithm to detect communities by optimizing the chosen quality function. Global optimization procedures, such as mathematical programming approaches [15; 16], provide accurate results. However, they face computational challenges when dealing with large networks [17]. Heuristic techniques, on the other hand--like bottom-up (merging communities), top-down (splitting communities), and local search (migrating nodes)--present viable solutions, especially for extensive networks [18], but they come at the cost of losing accuracy. Although various community discovery approaches have surfaced in recent years [19; 20; 21], due to space limitations, our discussion concentrates on methods pertinent to our study. Regarding optimization techniques, a wide variety of quality measures have been proposed, each offering a unique perspective to assess the goodness and accuracy of partitioning. [PERSON] et al. [22] categorize community quality functions into four broad types: _internal-connectivity-based_ metrics (IC), _external-connectivity-based_ metrics (EC), _mixed-internal-external_ metrics (MIE), and metrics based on _network topology_. Table 1 outlines some well-known connectivity-based quality functions. For example, the _Average degree_ function evaluates a community's quality based on both the number of edges with nodes inside the community and the number of nodes within the community. While connectivity-based metrics have achieved widespread recognition [22], their exclusive focus on link structures, such as the number of edges and degrees, limits their ability to consider other significant features of the network, such as potential relationships between nodes. Therefore, topological metrics, among which [PERSON]'s _Modularity_[27] stands out as a widely used and recognized one, have garnered remarkable attention. Modularity assesses the quality of a partition by measuring the disparity between the observed number of edges within communities and the expected number based on a null model. Nevertheless, the traditional Modularity metric has faced criticism for its limitation in exclusively considering existing edges, disregarding the possibility of connections between disconnected nodes within the same community. To overcome this drawback, an extension known as the _Max-Min Modularity_[9] introduces a complementary graph associated with the main network to capture relationships between disconnected nodes. The essential idea of Max-Min Modularity revolves around maximizing the Modularity value within the given network while concurrently minimizing this value across a complementary graph