Dynamic Bi-Colored Graph Partitioning

Dynamic Bi-Colored Graph Partitioning

He, Y. (TU Delft Signal Processing Systems)
Coutino, Mario (TNO)
Isufi, E. (TU Delft Multimedia Computing)
Leus, G.J.T. (TU Delft Signal Processing Systems)

2022

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.

dynamic graphs
generalized eigenvalue problem
graph partitioning
spectral clustering

http://resolver.tudelft.nl/uuid:43002202-ce76-4329-aaaa-c0e74aeb68cf

European Signal Processing Conference, EUSIPCO

2023-04-24

978-908279709-1

30th European Signal Processing Conference, EUSIPCO 2022 - Proceedings

30th European Signal Processing Conference, EUSIPCO 2022, 2022-08-29 → 2022-09-02, Belgrade, Serbia

European Signal Processing Conference, 2219-5491, 2022-August

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Institutional Repository

conference paper

© 2022 Y. He, Mario Coutino, E. Isufi, G.J.T. Leus