Constrained Directed Graph Clustering through Differential Equations Open Access
Zhou, Ziyu (Spring 2023)
Published
Abstract
This thesis introduces an algorithmic approach to the problem of clustering a weighted directed graph under constraints such as cardinality or membership requirements. The proposed approach extends a two-level iterative approach for solving weighted undirected graph minimum-cut problems to the minimum-cut and general clustering problems of directed graphs. This two-level method restates the constrained minimum-cut problems as matrix nearness problems, for which the key to numerical solutions is the gradient systems of matrix differential equations for minimizing a functional of an eigenvalue and eigenvectors of the graph Laplacians. In the proposed approach, a directed graph is transformed into an undirected one that preserves information about directionality. Numerical experiments are presented to validate the proposed approach and compare it with existing ones for unconstrained cases. The major contribution of this work is the ability to adapt a versatile technique to directed graphs and further requirements on clustering criteria.
Table of Contents
Chapter 1 Introduction
Chapter 2 Graphs background
Chapter 3 Minimum-cut and clustering methods for directed graphs
Chapter 4 Numerical experiments
Chapter 5 Conclusions
About this Honors Thesis
| School | |
|---|---|
| Department | |
| Degree | |
| Submission | |
| Language |
|
| Research Field | |
| Keyword | |
| Committee Chair / Thesis Advisor | |
| Committee Members |
Primary PDF
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
|
Constrained Directed Graph Clustering through Differential Equations () | 2023-04-13 17:15:17 -0400 |
|
Supplemental Files
| Thumbnail | Title | Date Uploaded | Actions |
|---|