Spectral Theory of Unsigned and Signed Graphs. Applications to Graph Clustering: a Survey

Understand

This is a survey of the method of graph cuts and its applications to graph clustering of weighted unsigned and signed graphs.

• I provide a fairly thorough treatment of the method of normalized graph cuts, a deeply original method due to Shi and Malik, including complete proofs.
• The main thrust of this paper is the method of normalized cuts.
• I give a detailed account for K = 2 clusters, and also for K > 2 clusters, based on the work of Yu and Shi.