Community detection in networks via nonlinear modularity eigenvectors

Tudisco, F. and Mercado, P. and Hein, M. (2017) Community detection in networks via nonlinear modularity eigenvectors. Preprint / Working Paper. arXiv.org, Ithaca, N.Y..

[thumbnail of Tudisco-etal-ArXiv-2017-Community-detection-in-networks-via-nonlinear]
Preview
 Text. Filename: Tudisco_etal_ArXiv_2017_Community_detection_in_networks_via_nonlinear.pdf
Final Published Version
Download (3MB)| Preview

Abstract

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.

CORE (COnnecting REpositories)