Logo

PDE and Free Boundary Techniques for Network Problems

Speaker

Yves van Gennip, University of Nottingham, UK

Time

2017.07.13 09:00-10:00

Venue

520 Pao Yue-Kong Library

Abstract

In recent years, ideas from the world of partial di erential equations (PDEs) have found their way into the arena of graph and network problems. In this talk I will discuss how techniques based on nonlinear PDE models and free boundary problems, such as the Allen-Cahn equation and the Merriman-Bence-Osher threshold dynamics scheme can be used to (approximately) detect particular structures in graphs, such as densely connected subgraphs (clustering and classi cation, minimum cuts) and bipartite subgraphs (maximum cuts). Such techniques not only often lead to fast algorithms that can be applied to large networks, but also pose interesting theoretical questions about the relationships between the graph models and their continuum counterparts, and about connections between the di erent graph models.