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
- 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 (4)
- Optimization via low-rank approximation for community detection in networks
- Active-Set Identification with Complexity Guarantees of an Almost Cyclic 2-Coordinate Descent Method with Armijo Line Search
- Laplacian-based semi-supervised learning in multilayer hypergraphs by coordinate descent
- 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)
