Graph Clustering Algorithms (September 28, 2017)

Описание: Tselil Schramm (Simons Institute, UC Berkeley)

One of the greatest advantages of representing data with graphs is access to generic algorithms for analytic tasks, such as clustering. In this talk I will describe some popular graph clustering algorithms, and explain why they are well-motivated from a theoretical perspective.

-------------------
References from the Whiteboard:

Ng, Andrew Y., Michael I. Jordan, and Yair Weiss. "On spectral
clustering: Analysis and an algorithm." Advances in neural information
processing systems. 2002.


Lee, James R., Shayan Oveis Gharan, and Luca Trevisan. "Multiway
spectral partitioning and higher-order cheeger inequalities." Journal
of the ACM (JACM) 61.6 (2014): 37.

-------------------
Additional Resources:

In my explanation of the spectral embedding I roughly follow the exposition from the lectures of Dan Spielman (http://www.cs.yale.edu/homes/spielman..., focusing on the content in lecture 2. Lecture 1 also contains some additional striking examples of graphs and their spectral embeddings.

I also make some imprecise statements about the relationship between the spectral embedding and the minimum-energy configurations of a mass-spring system. The connection is discussed more precisely here (https://www.simonsfoundation.org/2012....

License: CC BY-NC-SA 4.0
https://creativecommons.org/licenses/...