Total variation based community detection using a nonlinear optimization approach
From MaRDI portal
Publication:5113808
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.
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
Cites work
- scientific article; zbMATH DE number 2084315 (Why is no real title available?)
- scientific article; zbMATH DE number 3869077 (Why is no real title available?)
- scientific article; zbMATH DE number 2221955 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A New Active Set Algorithm for Box Constrained Optimization
- A Nonlinear Spectral Method for Core--Periphery Detection in Networks
- A Nonmonotone Line Search Technique for Newton’s Method
- A class on nonmonotone stabilization methods in unconstrained optimization
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A globally convergent primal-dual active-set framework for large-scale convex quadratic optimization
- 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
- A population-based approach for hard global optimization problems based on dissimilarity measures
- A two-stage active-set algorithm for bound-constrained optimization
- Advanced coarsening schemes for graph partitioning
- An active set feasible method for large-scale minimization problems with bound constraints
- An algebraic analysis of the graph modularity
- Communities in Networks
- Community detection and stochastic block models: recent developments
- Community detection in networks via nonlinear modularity eigenvectors
- Complex graphs and networks
- Fast unfolding of communities in large networks
- Generalized modularity matrices
- Global optimization on funneling landscapes
- Graph clustering
- Large-scale active-set box-constrained optimization method with spectral projected gradients
- Learning with submodular functions: a convex optimization perspective
- Networks. An introduction.
- On Finding Graph Clusterings with Maximum Modularity
- Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems
- Second-order negative-curvature methods for box-constrained and general constrained optimization
- Simplified energy landscape for modularity using total variation
- qpOASES: a parametric active-set algorithm for~quadratic programming
Cited in
(14)- Searching graph communities by modularity maximization via convex optimization
- 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
- Laplacian-based semi-supervised learning in multilayer hypergraphs by coordinate descent
- A sparse completely positive relaxation of the modularity maximization for community detection
- Variational community partition with novel network structure centrality prior
- Minimization over the \(\ell_1\)-ball using an active-set non-monotone projected gradient
- Modularity maximization using completely positive programming
- Optimization via low-rank approximation for community detection in networks
- Simplified energy landscape for modularity using total variation
- Active-set identification with complexity guarantees of an almost cyclic 2-coordinate descent method with Armijo line search
- Fast cluster detection in networks by first order optimization
- Revealing network communities with a nonlinear programming method
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)
