Community detection in networks via nonlinear modularity eigenvectors

F. Tudisco, P. Mercado, M. Hein

Research output: Working paper

35 Downloads (Pure)


Revealing a community structure in a network or dataset is a central problem arising in many scientific areas. The modularity function Q is an established measure quantifying the quality of a community, being identified as a set of nodes having high modularity. In our terminology, a set of nodes with positive modularity is called a \textit{module} and a set that maximizes Q is thus called \textit{leading module}. Finding a leading module in a network is an important task, however the dimension of real-world problems makes the maximization of Q unfeasible. This poses the need of approximation techniques which are typically based on a linear relaxation of Q, induced by the spectrum of the modularity matrix M. In this work we propose a nonlinear relaxation which is instead based on the spectrum of a nonlinear modularity operator M. We show that extremal eigenvalues of M provide an exact relaxation of the modularity measure Q, however at the price of being more challenging to be computed than those of M. Thus we extend the work made on nonlinear Laplacians, by proposing a computational scheme, named \textit{generalized RatioDCA}, to address such extremal eigenvalues. We show monotonic ascent and convergence of the method. We finally apply the new method to several synthetic and real-world data sets, showing both effectiveness of the model and performance of the method.
Original languageEnglish
Place of PublicationIthaca, N.Y.
Number of pages23
Publication statusPublished - 18 Aug 2017


  • optimisation and control
  • machine learning
  • information networks


Dive into the research topics of 'Community detection in networks via nonlinear modularity eigenvectors'. Together they form a unique fingerprint.

Cite this