Community Detection in Networks via Nonlinear Modularity Eigenvectors

Pittsburgh, USA.

Community identification in networks is a central problem arising in many scientific areas. The modularity function $Q$ is an effective measure of the quality of a community, being defined as a set of nodes having high modularity. Community detection thus boils down to the combinatorial optimization problem of locating sets of nodes maximizing $Q$. This problem is known to be NP-hard thus posing the need of approximation techniques which are typically based on a linear relaxation of $Q$, induced by the spectrum of the modularity matrix $\mathcal M$.

In this work we propose a nonlinear relaxation which is based on the spectrum of a nonlinear modularity operator $\mathcal M$. We show that extremal eigenvalues of $\mathcal M$ satisfy a tight Cheeger-type inequality providing an exact relaxation of the modularity function $Q$,however at a price of being more challenging to be computed than the extremal eigenvalues of the linear counterpart based on $\mathcal M$. We propose a general optimization scheme for the computation of the extremal eigenvalues of $\mathcal M$, named Generalized RatioDCA, and we show monotonic ascent and convergence of the method to a critical value. Finally, we present extensive evaluations on synthetic and real-world datasets showing that our method is competitive to the state of the art.