1. Gain and Pain in Graph Partitioning: Finding Accurate Communities in Complex Networks †.
- Author
-
Ferdowsi, Arman and Dehghan Chenary, Maryam
- Subjects
- *
INTEGER programming , *HEURISTIC algorithms , *ROWING techniques , *MATHEMATICAL programming , *APPROXIMATION algorithms - 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. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF