Maximizing the discrete modularity function allows to locate relevant communities in networks. This combinatorial optimization problem is known to be NP-hard. We introduce a continuous function $f$ and we show that its global maximum on the $\ell^\infty$-sphere coincides with the maximum of the original discrete modularity function. Thus we propose a community detection strategy based on $f$ and we show extensive numerical comparisons with standard matrix-based approaches.
This presentation is part of Minisymposium “MS13 - Optimization for Imaging and Big Data (2 parts)”
organized by: Margherita Porcelli (University of Firenze) , Francesco Rinaldi (University of Padova) .