Surface tension dynamics on networks

Monday, February 12, 2018, 11:00 am - 12:00 pm PDTiCal
11th floor large conference room
This event is open to the public.
AI Seminar - Interview talk
Zach Boyd
Video Recording:
There is an ongoing debate in the network science community regarding which frameworks are most appropriate to understand the structure of networks. Contenders include statistical generative models (e.g. stochastic block models), statistical mechanics (e.g. the Potts model), dynamics-based models (e.g. WalkTrap), and many others. In my talk, I will introduce some new formulations of community detection in networks that relate to tools in nonlinear PDE. These are new in the network science context and seem very effective.
My first example will treat the case where the network has an approximately homogeneous community structure, in which case it is possible to make an analogy between the network structure and geometric concepts such as surface area. Once the analogy is developed, the community detection problem is naturally cast as an analogue of mean curvature flow, and various approximations and theoretical guarantees on the performance then become available. I will show how this can be applied to examples from social networks, machine learning, and image processing, with good run times on networks with millions of edges.
As a second example, I will consider inhomogeneous network topologies, which will force an expansion of our analogy to incorporate inhomogeneous surface tensions. The resulting dynamics are analogous to a problem in crystal growth, which allows us to borrow three state-of-the-art PDE methods and apply them. This approach turns out to work well as long as several adjustments are made to accommodate the special structure of networks, and they raise interesting questions, such as the way to deal with boundary layers in networks, etc. These methods give state-of-the-art results, including exact recovery of community structure in some challenging problems. 
Finally, I will give some indications of future directions this work can go, both in terms of understanding the structure of the dynamics, as well as in terms of new applications.


« Return to Upcoming Events