Metric-Constrained Optimization for Graph Clustering Algorithms

DOI10.1137/18M1217152zbMATH Open1499.05598WikidataQ127752261 ScholiaQ127752261MaRDI QIDQ5025762FDOQ5025762

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)

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

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)

Cites Work

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

Cited In (5)

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

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)