Fast Cluster Detection in Networks by First Order Optimization

DOI10.1137/21M1408658zbMath1487.90615arXiv2103.15907OpenAlexW3141230086MaRDI QIDQ5065475

Francesco Rinaldi, Damiano Zeffiro, Immanuel M. Bomze

Publication date: 21 March 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.15907

zbMATH Keywords

Frank-Wolfe methodclique relaxationssupport identificationmaximum \(s\)-defective clique

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Nonlinear programming (90C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (2)

Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph ⋮ A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• On standard quadratic optimization problems
• Evolution towards the maximum clique
• Genetic engineering via negative fitness: Evolutionary dynamics for global optimization
• Computing maximum \(k\)-defective cliques in massive graphs
• Continuous cubic formulations for cluster detection problems in networks
• On clique relaxation models in network analysis
• First-order methods almost always avoid strict saddle points
• A review on algorithms for maximum clique problems
• A Complementary Pivoting Approach to the Maximum Weight Clique Problem
• An Extended Frank--Wolfe Method with “In-Face” Directions, and Its Application to Low-Rank Matrix Completion
• Regularity versus Degeneracy in Dynamics, Games, and Optimization: A Unified Approach to Different Aspects
• Some comments on Wolfe's ‘away step’
• The largest eigenvalue of a graph: A survey
• A General Regularized Continuous Formulation for the Maximum Clique Problem
• Active Set Complexity of the Away-Step Frank--Wolfe Algorithm
• First-order Methods for the Impatient: Support Identification in Finite Time with Convergent Frank--Wolfe Variants
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Proofs from THE BOOK
• On copositive programming and standard quadratic optimization problems

This page was built for publication: Fast Cluster Detection in Networks by First Order Optimization