Speaker:

Roger Su(University of Auckland)

Time:

• 10:00-12:00 (Time in Beijing)
• 15:00-17:00 (Time in Auckland)
• October 29, 2021 (Friday)

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.