Dynamic Bi-Colored Graph Partitioning

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

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.

Original languageEnglish
Title of host publication30th European Signal Processing Conference, EUSIPCO 2022 - Proceedings
PublisherEuropean Signal Processing Conference, EUSIPCO
Pages692-696
Number of pages5
ISBN (Electronic)978-908279709-1
Publication statusPublished - 2022
Event30th European Signal Processing Conference, EUSIPCO 2022 - Belgrade, Serbia
Duration: 29 Aug 20222 Sep 2022

Publication series

NameEuropean Signal Processing Conference
Volume2022-August
ISSN (Print)2219-5491

Conference

Conference30th European Signal Processing Conference, EUSIPCO 2022
Country/TerritorySerbia
CityBelgrade
Period29/08/222/09/22

Bibliographical note

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.

Keywords

  • dynamic graphs
  • generalized eigenvalue problem
  • graph partitioning
  • spectral clustering

Fingerprint

Dive into the research topics of 'Dynamic Bi-Colored Graph Partitioning'. Together they form a unique fingerprint.

Cite this