Improving heuristics for network modularity maximization using an exact algorithm

Sonia Cafieri (1) , Pierre Hansen (2) , Leo Liberti (3)

1 MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien
2 HEC Montréal - HEC Montréal
3 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

Heuristics are widely applied to modularity maximization models for the identification of communities in complex networks. We present an approach to be applied as a post-processing to heuristic methods in order to improve their performances. Starting from a given partition, we test with an exact algorithm for bipartitioning if it is worthwhile to split some communities or to merge two of them. A combination of merge and split actions is also performed. Computational experiments show that the proposed approach is effective in improving heuristic results.

Mots clés: clustering; bipartition; network; graph; community; modularity; heuristic; exact algorithm; matheuristic

Domaines: Mathématiques [math]; Optimisation et contrôle [math.OC]

Sonia Cafieri, Pierre Hansen, Leo Liberti. Improving heuristics for network modularity maximization using an exact algorithm. Discrete Applied Mathematics, 2014, 163 (1), pp 65-72. ⟨10.1016/j.dam.2012.03.030⟩. ⟨hal-00935211⟩