Total variation based community detection using a nonlinear optimization approach
From MaRDI portal
Publication:5113808
DOI10.1137/19M1270446zbMATH Open1444.91175arXiv1907.08048OpenAlexW3101735029MaRDI QIDQ5113808FDOQ5113808
Authors: Andrea Cristofari, F. Rinaldi, Francesco Tudisco 
Publication date: 17 June 2020
Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)
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 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 . 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.
Full work available at URL: https://arxiv.org/abs/1907.08048
Recommendations
- Revealing network communities with a nonlinear programming method
- Community detection via an efficient nonconvex optimization approach based on modularity
- A method based on total variation for network modularity optimization using the MBO scheme
- Community detection in networks via nonlinear modularity eigenvectors
- Simplified energy landscape for modularity using total variation
Numerical optimization and variational techniques (65K10) Clustering in the social and behavioral sciences (91C20) Social networks; opinion dynamics (91D30)
Cites Work
- Title not available (Why is that?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- qpOASES: a parametric active-set algorithm for~quadratic programming
- Community detection and stochastic block models: recent developments
- Graph clustering
- Fast unfolding of communities in large networks
- Networks. An introduction.
- A first-order primal-dual algorithm for convex problems with applications to imaging
- Second-order negative-curvature methods for box-constrained and general constrained optimization
- A Nonmonotone Line Search Technique for Newton’s Method
- Complex graphs and networks
- Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems
- A New Active Set Algorithm for Box Constrained Optimization
- Generalized modularity matrices
- An algebraic analysis of the graph modularity
- A globally convergent primal-dual active-set framework for large-scale convex quadratic optimization
- A class on nonmonotone stabilization methods in unconstrained optimization
- Advanced coarsening schemes for graph partitioning
- Large-scale active-set box-constrained optimization method with spectral projected gradients
- On Finding Graph Clusterings with Maximum Modularity
- A population-based approach for hard global optimization problems based on dissimilarity measures
- Communities in Networks
- Global optimization on funneling landscapes
- Title not available (Why is that?)
- An active set feasible method for large-scale minimization problems with bound constraints
- Community detection in networks via nonlinear modularity eigenvectors
- Learning with submodular functions: a convex optimization perspective
- A two-stage active-set algorithm for bound-constrained optimization
- Title not available (Why is that?)
- A method based on total variation for network modularity optimization using the MBO scheme
- A nodal domain theorem and a higher-order Cheeger inequality for the graph \(p\)-Laplacian
- Simplified energy landscape for modularity using total variation
- A Nonlinear Spectral Method for Core--Periphery Detection in Networks
Cited In (14)
- Variational community partition with novel network structure centrality prior
- Active-set identification with complexity guarantees of an almost cyclic 2-coordinate descent method with Armijo line search
- Optimization via low-rank approximation for community detection in networks
- Community detection via an efficient nonconvex optimization approach based on modularity
- Modularity maximization using completely positive programming
- Simplified energy landscape for modularity using total variation
- A sparse completely positive relaxation of the modularity maximization for community detection
- Community detection in networks via nonlinear modularity eigenvectors
- Revealing network communities with a nonlinear programming method
- A method based on total variation for network modularity optimization using the MBO scheme
- Laplacian-based semi-supervised learning in multilayer hypergraphs by coordinate descent
- Fast cluster detection in networks by first order optimization
- Searching graph communities by modularity maximization via convex optimization
- Minimization over the \(\ell_1\)-ball using an active-set non-monotone projected gradient
Uses Software
This page was built for publication: Total variation based community detection using a nonlinear optimization approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113808)
