Constrained graph partitioning via matrix differential equations

DOI10.1137/17M1160987MaRDI QIDQ4615297zbMATH OpenOpenAlexWikidataFDO

Authors Eleonora Andreotti, Dominik Edelmann, Christian Lubich, Nicola Guglielmi

Publication date 4 February 2019

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/17m1160987

zbMATH Keywords

constrained clusteringconstrained minimum cutgradient flowmatrix differential equationmatrix nearness problem

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Eigenvalues, singular values, and eigenvectors (15A18) Numerical mathematical programming methods (65K05)

Recommendations

• Algorithms for graph partitioning problems by means of eigenspace relaxations
• Constructive Heuristics and Lower Bounds for Graph Partitioning Based on a Principal-Components Approximation
• Graph Partitioning and Continuous Quadratic Programming
• scientific article; zbMATH DE number 736319
• An exact algorithm for graph partitioning

Cites work

• A simple min-cut algorithm
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• ARPACK Users' Guide
• Cardinality constrained minimum cut problems: complexity and algorithms.
• Community structure in social and biological networks
• Constrained Clustering
• Derivatives and Perturbations of Eigenvectors
• Differential equations for roaming pseudospectra: paths to extremal points and boundary tracking
• scientific article; zbMATH DE number 6276186 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Low rank differential equations for Hamiltonian matrix nearness problems
• Matrix Stabilization Using Differential Equations
• Numerical methods for large eigenvalue problems
• On the Nearest Singular Matrix Pencil
• Perturbation theory for linear operators.
• Practical methods of optimization.
• Spectral clustering and its use in bioinformatics

Cited in

(6)

• Measuring the stability of spectral clustering
• Continuous graph partitioning for camera network surveillance
• Graph-Based Representations in Pattern Recognition
• Quantifying the structural stability of simplicial homology
• Structured linear stability problems
• A low-rank ODE for spectral clustering stability

Describes a project that uses

Uses Software

• ARPACK

This page was built for publication: Constrained graph partitioning via matrix differential equations

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