Computational Mathematics and Scientific Computing Seminar

---

Graph Partitioning using Matrix Differential Equations

Speaker: Nicola Guglielmi, Gran Sasso Science Institute, Italy

Location: Warren Weaver Hall 1302

Date: Feb. 23, 2018, 10 a.m.

Synopsis:

Given an undirected weighted graph, we are concerned with two problems associated to partitioning the graph. First of all we discuss the closest disconnected graph (the minimum cut problem), here with respect to the 2-norm. We are interested in the case of constrained minimum cut problems, where constraints include cardinality or membership requirements, which leads to NP-hard combinatorial optimization problems. Furthermore, we are interested in ambiguity issues, that is in the robustness of a clustering algorithm of the graph, which is based on Fiedler spectral partitioning. The  above-mentioned problems are restated as matrix nearness problems for the weight matrix of the graph. A key element in the solution of these matrix nearness problems is the use of a constrained gradient system of matrix differential equations.

This is a joint work with Christian Lubich and Dominik Edelmann (Tuebingen) and Eleonora Andreotti (L'Aquila).