Quasi-Isometric Graph-Simplifications
- Speaker
- Roger Su
- Affiliation
- University of Auckland
- Date
- Time
- – Asia/Shanghai
- Venue
- Qingshuihe Campus
Abstract
Quasi-isometries are a concept originally used to study infinite algebraic objects. Here we apply quasi-isometries to finite graphs, and propose a theoretical framework for simplifying large-scale graphs. This framework consists of several goals, including small quasi-isometric constants, effective compression, and preservation of other properties.
Under this framework, we introduce a method of quasi-isometric graph-simplification based on grouping connected vertices. We then focus on the graph-centre, and introduce the centre-shift as a measure of centre-preservation. Finally we show two specific simplification-methods that respectively preserve the centres and medians of trees.
Schedule
- 10:00-12:00 (Time in Beijing)
- 15:00-17:00 (Time in Auckland)
- October 29, 2021 (Friday)