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-complete. Inspired by recent nonlinear modularity eigenvector approaches, we introduce the modularity total variation $T{V}_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 $T{V}_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 RatioDCA approach for nonlinear modularity eigenvectors, showing that our new method compares favourably with state-of-the-art alternatives.

References in corpus (17)

• Fast unfolding of communities in large networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Finding community structure in networks using the eigenvectors of matrices
• Community detection algorithms: a comparative analysis
• Community detection in networks: A user guide
• Community detection in complex networks using Extremal Optimization
• The performance of modularity maximization in practical contexts
• Modularity from Fluctuations in Random Graphs and Complex Networks
• The map equation
• Narrow scope for resolution-limit-free community detection
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Spectral methods for the detection of network community structure: a comparative analysis
• A Two-Stage Active-Set Algorithm for Bound-Constrained Optimization
• Community detection in networks via nonlinear modularity eigenvectors
• An algebraic analysis of the graph modularity