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 (www.cs.yale.edu..., 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 (www.simonsfoun....
License: CC BY-NC-SA 4.0
- creativecommon...

[@gpprudhvi]

Awesome explanation!

[@stomerh]

Did you said MANSPLAINING (in 1:35) ???

[@andrewchavarria9227]

LMAOOO she did

[@russp622]

Quite a stupid thing to come out of the mouth of someone of her caliber!

[@smiletolerantly]

@@russp622 Or, you know... It's a deliberate joke.

[@Raven-bi3xn]

Hahaha she is hilarious!

[@Iamfafafel]

lmaoo

[@Wanderschwamm]

I sometimes have the problem, that some of the clusters are not totally interconnected (one node is only accessible over nodes that are in other clusters ). How can I improve the algorithm, that this won't happen anymore? Is there any correlation between the number of clusters (K) and the number of eigenvectors i should use?

[@Raven-bi3xn]

Great talk!

[@hos42]

This helped me a lot

[@mumbaicarnaticmusic2021]

Thanks a lot

[@samirzerrouki9140]

thank you