Metric-Constrained Optimization for Graph Clustering Algorithms

DOI10.1137/18M1217152zbMath1499.05598WikidataQ127752261 ScholiaQ127752261MaRDI QIDQ5025762

James Saunderson, Anthony Wirth, David F. Gleich, Nate Veldt

Publication date: 3 February 2022

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

zbMATH Keywords

projection methodsmodularitymetric learninggraph clusteringsparsest cutcorrelation clustering

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Harmonic analysis invariants for infinite graphs via operators and algorithms, Graph Clustering in All Parameter Regimes, A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis

Uses Software

• SNAP
• SparseMatrix
• GenLouvain

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cost-optimal constrained correlation clustering via weighted partial maximum satisfiability
• Correlation clustering
• Modularity-maximizing graph communities via mathematical programming
• On the convergence of Han's method for convex programming with quadratic objective
• Stronger linear programming relaxations of max-cut
• The adventures of a simple algorithm
• The expected relative error of the polyhedral approximation of the max- cut problem
• The approximation of fixed points of compositions of nonexpansive mappings in Hilbert space
• Hildreth's algorithm with applications to soft constraints for user interface layout
• Clustering with qualitative information
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds
• The university of Florida sparse matrix collection
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems
• An Algorithm for Restricted Least Squares Regression
• The Metric Nearness Problem
• Normal solutions of linear programs
• Fast unfolding of communities in large networks
• Robust Stopping Criteria for Dykstra's Algorithm
• Correlation Clustering and Biclustering With Locally Bounded Errors
• Convex analysis and monotone operator theory in Hilbert spaces
• Algorithms - ESA 2003
• Aggregating inconsistent information
• Expander flows, geometric embeddings and graph partitioning
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques