Community detection in networks via nonlinear modularity eigenvectors

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 $\mathcal{M}$. We show that extremal eigenvalues of $\mathcal{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.

References in corpus (14)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Resolution limit in community detection
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Community Structure in Jazz
• Analysis of the structure of complex networks at different resolution levels
• Narrow scope for resolution-limit-free community detection
• Spectral methods for the detection of network community structure: a comparative analysis
• Spectral tripartitioning of networks
• Multiway spectral community detection in networks
• The Power Mean Laplacian for Multilayer Graph Clustering
• A Method Based on Total Variation for Network Modularity Optimization using the MBO Scheme

Cited by in corpus (4)

• Total variation based community detection using a nonlinear optimization approach
• Stochastic Block Models are a Discrete Surface Tension
• The self-consistent field iteration for p-spectral clustering
• Semi-supervised Learning for Aggregated Multilayer Graphs Using Diffuse Interface Methods and Fast Matrix Vector Products