Special Session 142: Recent developments for PDE constrained shape and topological optimization and their applications
Graph and domain partitioning based upon escape time optimization
Jeremy L Marzuola
University of North Carolina USA
Co-Author(s): Zach Boyd, Nico Fraiman, Peter Mucha, Braxton Osting, Arunima Bhattacharya, Matthias Kurzke, Dan Weser
Abstract:
We provide a rearrangement based algorithm for fast detection of subgraphs of k vertices with long escape times for directed or undirected networks. Complementing other notions of densest subgraphs and graph cuts, our method is based on the mean hitting time required for a random walker to leave a designated set and hit the complement. We provide a new relaxation of this notion of hitting time on a given subgraph and use that relaxation to construct a fast subgraph detection algorithm and a generalization to K-partitioning schemes. Using a modification of the subgraph detector on each component, we propose a graph partitioner that identifies regions where random walks live for comparably large times. Importantly, our method implicitly respects the directed nature of the data for directed graphs while also being applicable to undirected graphs. We apply the partitioning method for community detection to a large class of model and real-world data sets. We also discuss existence and boundary regularity for a related algorithm on domains/manifolds.