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

Add to your list(s) Download to your calendar using vCal

• Zachary Boyd (University of California, Los Angeles)
• Friday 15 December 2017, 09:00-10:00
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact INI IT.

VMVW03 - Flows, mappings and shapes

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.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.