Dynamic Bi-Colored Graph Partitioning

Conference paper (2022)

Authors

Y. He Signal Processing Systems - EEMCS
G.J.T. Leus Signal Processing Systems - EEMCS
Research Group
Signal Processing Systems (EEMCS) (TU Delft)
Copyright: © 2022 Y. He, Mario Coutino, E. Isufi, G.J.T. Leus
Graph partitioning Spectral clustering Generalized eigenvalue problem Dynamic graphs
More Info
expand_more

Published Date

2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Microelectronics

Research Group

Signal Processing Systems

Abstract

In this work, we focus on partitioning dynamic graphs with two types of nodes (bi-colored), though not necessarily bipartite graphs. They commonly appear in communication network applications, e.g., one color being base stations, the other users, and the dynamic process being the varying connection status between base stations and moving users. We introduce a partition cost function that incorporates the coloring of the graph and propose solutions based on the generalized eigenvalue problem (GEVP) for the static two-way partition problem. The static multi-way partition problem is then handled by a heuristic based on the two-way partition problem. Regarding the adaptive partition, an eigenvector update-based method is proposed. Numerical experiments demonstrate the performance of the devised approaches.