Total variation based community detection using a nonlinear optimization approach

Abstract

Maximizing the modularity of a network is a successful tool to identify an important community of nodes. However, this combinatorial optimization problem is known to be NP-hard. Inspired by recent nonlinear modularity eigenvector approaches, we introduce the modularity total variation $TV_Q$ and show that its box-constrained global maximum coincides with the maximum of the original discrete modularity function. Thus we describe a new nonlinear optimization approach to solve the equivalent problem leading to a community detection strategy based on $TV_Q$. The proposed approach relies on the use of a fast first-order method that embeds a tailored active-set strategy. We report extensive numerical comparisons with standard matrix-based approaches and the Generalized Ratio DCA approach for nonlinear modularity eigenvectors, showing that our new method compares favourably with state-of-the-art alternatives. Our software is available upon request.

Please cite this work as:

@article{cristofari2020total,
  title={Total variation based community detection using a nonlinear optimization approach},
  author={Cristofari, Andrea and Rinaldi, Francesco and Tudisco, Francesco},
  journal={SIAM Journal on Applied Mathematics},
  volume={80},
  number={3},
  pages={1392--1419},
  year={2020},
  publisher={SIAM}
}

Keywords: community detection graph modularity total variation nonlinear optimization active-set method