Metric-Constrained Optimization for Graph Clustering Algorithms

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

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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The university of Florida sparse matrix collection
• Fast unfolding of communities in large networks
• Clustering with qualitative information
• Aggregating inconsistent information
• Correlation clustering
• Expander flows, geometric embeddings and graph partitioning
• 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
• Algorithms - ESA 2003
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• 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
• 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 (4)

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

Uses Software

• SNAP
• SparseMatrix
• GenLouvain

Recommendations

• Graph clustering with a constraint on cluster sizes 👍 👎
• Clustering for metric graphs using the \(p\)-Laplacian 👍 👎
• Approximate Greedy Clustering and Distance Selection for Graph Metrics 👍 👎
• Density-Constrained Graph Clustering 👍 👎
• Experiments on density-constrained graph clustering 👍 👎
• Title not available (Why is that?) 👍 👎

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)