Metric-Constrained Optimization for Graph Clustering Algorithms

DOI10.1137/18M1217152MaRDI QIDQ5025762zbMATH OpenWikidataFDO

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

Publication date 3 February 2022

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

zbMATH Keywords

graph clusteringmodularitymetric learningprojection methodssparsest cutcorrelation clustering

Mathematics Subject Classification ID

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

Recommendations

• Graph clustering with a constraint on cluster sizes
• Clustering for metric graphs using the p-Laplacian
• Density-constrained graph clustering
• Approximate greedy clustering and distance selection for graph metrics
• Graphs, \(L_1\)-metrics and clustering

Cites work

• scientific article; zbMATH DE number 437546 (Why is no real title available?)
• Aggregating inconsistent information: ranking and clustering
• Algorithms - ESA 2003
• Alternating projection methods.
• An Algorithm for Restricted Least Squares Regression
• Clustering with qualitative information
• Convex analysis and monotone operator theory in Hilbert spaces
• Correlation Clustering and Biclustering With Locally Bounded Errors
• Correlation clustering
• Correlation clustering with constrained cluster sizes and extended weights bounds
• Correlation clustering with partial information
• Correlation clustering, maximizing agreements via semidefinite programming
• Cost-optimal constrained correlation clustering via weighted partial maximum satisfiability
• Deterministic pivoting algorithms for constrained ranking and clustering problems
• Expander flows, geometric embeddings and graph partitioning
• Fast unfolding of communities in large networks
• Hildreth's algorithm with applications to soft constraints for user interface layout
• Modularity-maximizing graph communities via mathematical programming
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• Normal solutions of linear programs
• On the convergence of Han's method for convex programming with quadratic objective
• Robust Stopping Criteria for Dykstra's Algorithm
• Stronger linear programming relaxations of max-cut
• The Metric Nearness Problem
• The University of Florida sparse matrix collection
• The adventures of a simple algorithm
• The approximation of fixed points of compositions of nonexpansive mappings in Hilbert space
• The expected relative error of the polyhedral approximation of the max- cut problem

Cited in

(5)

• Harmonic analysis invariants for infinite graphs via operators and algorithms
• A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis
• The Metric Nearness Problem
• Graph Clustering in All Parameter Regimes
• Graph clustering with Boltzmann machines

Describes a project that uses

Uses Software

• SNAP
• SparseMatrix
• GenLouvain

This page was built for publication: Metric-Constrained Optimization for Graph Clustering Algorithms

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