skip to content

Formulations of community detection in terms of total variation and surface tension

Presented by: 
Zachary Boyd
Friday 15th December 2017 - 09:00 to 10:00
INI Seminar Room 1
Network data structures arise in numerous applications, e.g. in image segmentation when graph cut methods are used or in the form of a similarity graph on the pixels in certain clustering methods. Networks also occur as social, biological, technological, and transportation networks, for instance, all of which are receiving a lot of attention right now. "Community detection" is a body of techniques for extracting large- and medium-scale structure from such graphs. Most community detection formalizations turn out to be NP-hard and in practice are horrendously nonconvex. Practitioners from many fields are struggling to find formulations that (1) helpfully summarize the network data and (2) are computationally tractable. Most formulations have neither property. In my talk, I will give two examples of how existing community detection models can be understood in terms of objects familiar in image processing. The first example casts the popular modularity heuristic as a graph total variation problem with a soft area balance constraint. The second views the more flexible stochastic block model as a discrete surface tension minimization problem, which in the two-community case is exactly equivalent to the first example. These equivalences can potentially benefit both the network science community and the image processing community by allowing tools from one domain to be applied to the other. As an example, I show how mean curvature flow, phase field, and threshold dynamics approaches to continuum total variation minimization can be adapted to community detection in graphs, including nonlocal means graphs for hyperspectral images and videos. The positive results hint that the methods commonly used in image processing can be readily applied to much more general problems involving arbitrary graph structures. I will also mention some possible future work in the reverse direction, where I would like to bring methods from the network science literature into image processing. This is joint work with Egil Bae, Andrea Bertozzi, Mason Porter, and Xue-Cheng Tai.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons