Fast cluster detection in networks by first order optimization

DOI10.1137/21M1408658zbMATH Open1487.90615arXiv2103.15907OpenAlexW3141230086MaRDI QIDQ5065475FDOQ5065475

Authors: Immanuel M. Bomze, F. Rinaldi, Damiano Zeffiro 

Publication date: 21 March 2022

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

Abstract: Cluster detection plays a fundamental role in the analysis of data. In this paper, we focus on the use of s-defective clique models for network-based cluster detection and propose a nonlinear optimization approach that efficiently handles those models in practice. In particular, we introduce an equivalent continuous formulation for the problem under analysis, and we analyze some tailored variants of the Frank-Wolfe algorithm that enable us to quickly find maximal s-defective cliques. The good practical behavior of those algorithmic tools, which is closely connected to their support identification properties, makes them very appealing in practical applications. The reported numerical results clearly show the effectiveness of the proposed approach.

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

Recommendations

• Continuous cubic formulations for cluster detection problems in networks
• Total variation based community detection using a nonlinear optimization approach
• A fast and efficient algorithm to identify clusters in networks
• Revealing network communities with a nonlinear programming method
• Optimization via low-rank approximation for community detection in networks

zbMATH Keywords

clique relaxationsFrank-Wolfe methodsupport identificationmaximum \(s\)-defective clique

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• On clique relaxation models in network analysis
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Evolution towards the maximum clique
• A review on algorithms for maximum clique problems
• Proofs from THE BOOK
• On copositive programming and standard quadratic optimization problems
• The largest eigenvalue of a graph: A survey
• On standard quadratic optimization problems
• Regularity versus Degeneracy in Dynamics, Games, and Optimization: A Unified Approach to Different Aspects
• Title not available (Why is that?)
• Some comments on Wolfe's ‘away step’
• Genetic engineering via negative fitness: Evolutionary dynamics for global optimization
• A complementary pivoting approach to the maximum weight clique problem
• Nonlinear programming
• An extended Frank-Wolfe method with ``in-face directions, and its application to low-rank matrix completion
• First-order methods almost always avoid strict saddle points
• Computing maximum \(k\)-defective cliques in massive graphs
• 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
• A general regularized continuous formulation for the maximum clique problem
• Continuous cubic formulations for cluster detection problems in networks

Cited In (4)

• Continuous cubic formulations for cluster detection problems in networks
• A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem
• Finite convergence of sum-of-squares hierarchies for the stability number of a graph
• Title not available (Why is that?)

Uses Software

• DIMACS

This page was built for publication: Fast cluster detection in networks by first order optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5065475)